数据结构——非递归中序遍历树-白红宇

数据结构——非递归中序遍历树

阅读量：4099 次

发布时间：2019-05-25

本文共 2985 字，大约阅读时间需要 9 分钟。

原文地址：

不用递归遍历树，那么很显然就是用栈了。下面是用栈遍历二叉树的算法。逐步执行这个算法请看。

1) 建立一个空栈S。2) 初始化当前的节点作为根节点3) 将当前节点push到S中并设置current = current->left直到current为NULL4) 如果current为NULL并且stack不为空，那么     a) 将顶部的项从栈中pop出来。     b) 打印pop出来的项，设置current = popped_item->right      c) 返回第3步。5) 如果current为NULL并且栈为空，那么活就干完了。

我们将下面的树作为例子考虑一下：

1          /   \        2      3      /  \    4     5Step 1 建立一个空栈：S = NULLStep 2 设current为根的地址：current -> 1Step 3 push当前的节点，并设current = current->left直到current为NULL     current -> 1     push 1: Stack S -> 1     current -> 2     push 2: Stack S -> 2, 1     current -> 4     push 4: Stack S -> 4, 2, 1     current = NULLStep 4 S做pop操作     a) Pop 4: Stack S -> 2, 1     b) print "4"     c) current = NULL /*right of 4 */ and go to step 3因为current为NULL，step 3 啥也不做。Step 4 再做pop操作.     a) Pop 2: Stack S -> 1     b) 打印"2"     c) current -> 5/*right of 2 */ and go to step 3Step 3 push 5进栈使current为NULL     Stack S -> 5, 1     current = NULLStep 4 S做pop操作     a) Pop 5: Stack S -> 1     b) 打印"5"     c) current = NULL /*right of 5 */ 并跳到step 3因为current为NULL，step 3啥也不干。Step 4 再次做pop操作     a) Pop 1: Stack S -> NULL     b) 打印"1"     c) current -> 3 /*right of 5 */  Step 3 push 3到栈，使current为NULL     Stack S -> 3     current = NULLStep 4 S做pop操作     a) Pop 3: Stack S -> NULL     b) print "3"     c) current = NULL /*right of 3 */  遍历这时候就完成了，因为栈S空了，current为NULL。

实现：

// non-recursive java program for inorder traversal/* importing the necessary class */import java.util.Stack;/* Class containing left and right child of current  node and key value*/class Node {    int data;    Node left, right;    public Node(int item) {        data = item;        left = right = null;    }}/* Class to print the inorder traversal */class BinaryTree {    Node root;    void inorder() {        if (root == null) {            return;        }        //keep the nodes in the path that are waiting to be visited        Stack
   
     stack = new Stack
    
     ();        Node node = root;        //first node to be visited will be the left one        while (node != null) {            stack.push(node);            node = node.left;        }        // traverse the tree        while (stack.size() > 0) {            // visit the top node            node = stack.pop();            System.out.print(node.data + " ");            if (node.right != null) {                node = node.right;                // the next node to be visited is the leftmost                while (node != null) {                    stack.push(node);                    node = node.left;                }            }        }    }    public static void main(String args[]) {        /* creating a binary tree and entering          the nodes */        BinaryTree tree = new BinaryTree();        tree.root = new Node(1);        tree.root.left = new Node(2);        tree.root.right = new Node(3);        tree.root.left.left = new Node(4);        tree.root.left.right = new Node(5);        tree.inorder();    }}

时间复杂度：O(n)

输出：