二叉树的先中后遍历

佚名 6年前 (2019-06-25) 算法 1663人围观抢沙发百度已收录

二叉树示意图

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

节点的数据结构：

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

递归版：

先来看这一段代码：

public static void Recur(Node head) {
        if (head == null) {
            return;
        }
        preOrderRecur(head.left);
        preOrderRecur(head.right);
}

这一段代码执行过程中经历节点的情况如下图：

由此可见，因为系统栈的原因，每一个节点都访问了3次。

先序遍历的顺序是中左右，中序遍历的顺序使左中右，后序遍历的顺序是左右中。

其中先序遍历就是每个节点第一次出现的时候，答案就是1，2，4，5，3，6，7

其中中序遍历就是每个节点第二次出现的时候，答案就是4，2，5，1，6，3，7

其中后序序遍历就是每个节点第三次出现的时候，答案就是4，5，2，6，7，3，1

代码如下：

先序遍历

public static void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

中序遍历

public static void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.value + " ");
        inOrderRecur(head.right);
    }

后序遍历

public static void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value + " ");
    }

非递归版：

先序遍历

使用一个辅助栈，用于压入节点，压入的规则是：

1.如果当前节点不存在，则不进行任何操作。

2.先压入二叉树的右节点，在压入二叉树的左节点，这样弹出的时候就会先弹出左节点，在弹出右节点。

public static void preOrderUnRecur(Node head) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
}

中序遍历

使用一个辅助栈，用于压入节点，压入的规则是：

1.如果当前节点不为空，则压入栈，当前节点指向左节点。

2.如果当前节点为空，则从栈中弹出节点并打印，弹出节点变为当前节点，当前节点指向的右节点。

public static void inOrderUnRecur(Node head) {
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }

}

后序遍历

后序遍历的顺序是左右中，先序遍历的顺序是中左右，如果我们把先序遍历的顺序改为中右左，中右左反过来就是左右中，也就是后序遍历。

使用一个辅助栈，用于压入节点，压入的规则是：

1.如果当前节点为空，不进行任何操作。

2.先压入二叉树的左节点，在压入二叉树的右节点。

public static void posOrderUnRecur1(Node head) {
        if (head != null) {
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
    }