Anwen——立志成为斜杠青年:IT极客/健身/旅行/国菜大厨/中国军人

别人的看法都是狗屁,你是谁只有自己说了算。若命运不公,就和他斗到底。
——《哪吒之魔童降世》

目录
二叉树前中后序遍历(非递归)
/  

二叉树前中后序遍历(非递归)

伪代码:

先序遍历(先根)
	将根节点入栈;
	当栈不空的时候:
		弹出栈顶节点;
		访问该节点;
		如果其右子节点不可则入栈其右子节点;
		如果其左子节点不空则入栈其左子节点;

中序遍历(先左)
	将指针p指向根节点;
	当p指向不为null时:
		将p指向的节点入栈;
		p向左子节点移动;
		当p指向null时:
			如果栈不空:
				弹出栈顶节点并访问;
				p指向该节点的右子节点;
			如果栈为空
				跳出内层循环(由于p指向null,间接地会跳出外层循环,终止遍历)

后续遍历(最后考虑根节点)
	将根节点入栈;
	指针lastAccess记录上次访问的节点,初始为null;
	当栈不空时:
		瞥一眼栈顶节点;
		若该节点是叶子节点或该节点是上次访问节点的父节点(注意上次访问节点为空的情况):
			访问该节点;
			lastAccess指向该节点;
		否则:
			将非空的该节点的右子节点入栈;
			将非空的该节点的左子节点入栈;

代码实现:

class Node<E> {
    E       element;
    Node<E> left;
    Node<E> right;

    Node(E element) {
        this.element = element;
    }

    @Override
    public String toString() {
        return "Node{" +
                "element=" + element +
                '}';
    }
}

private static void emptyTreeCheck(Node root) {  
 if (root == null) {  
   throw new IllegalArgumentException("empty tree");  
 }  
}

public static void preOrderUnRecur(Node root) {
    emptyTreeCheck(root);
    Stack<Node> stack = new Stack<>();
    StringBuilder stringBuilder = new StringBuilder();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        stringBuilder.append(node.element).append(" ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    System.out.println(stringBuilder.toString());
}

public static void inOrderUnRecur(Node root) {
    emptyTreeCheck(root);
    StringBuilder sb = new StringBuilder();
    Stack<Node> stack = new Stack<>();
    while (root != null) {
        stack.push(root);
        root = root.left;
        while (root == null) {
            if (stack.isEmpty()) {
                break;
            } else {
                Node node = stack.pop();
                sb.append(node.element).append(" ");
                root = node.right;
            }
        }
    }
    System.out.println(sb.toString());
}

private static boolean oneIsChildOfAnother(Node one, Node another) {  
 return one != null && (one == another.left || one == another.right);  
}  
  
private static boolean isLeaf(Node node) {  
 return node.left == null && node.right == null;  
}

private static void postOrderUnRecur(Node root) {
    emptyTreeCheck(root);
    StringBuilder stringBuilder = new StringBuilder();
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    Node lastAccess = null;
    while (!stack.isEmpty()) {
        Node node = stack.peek();
        // 当来到的节点node是叶子节点或上次访问的节点是其子节点时,需要进行访问
        if (isLeaf(node) || oneIsChildOfAnother(lastAccess, node)) {
            stack.pop();
            stringBuilder.append(node.element).append(" ");
            lastAccess = node;
        } else {
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
    System.out.println(stringBuilder.toString());
}

public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(8);
    root.left.right.left = new Node(9);

//        preOrderUnRecur(root);
//        inOrderUnRecur(root);
    postOrderUnRecur(root);
}

标题:二叉树前中后序遍历(非递归)
作者:zanwen
地址:http://www.zhenganwen.top/articles/2019/11/18/1574041146405.html

评论