二叉树的遍历总结

概述

这次首先总结二叉树的前序、中序、后序、层次遍历的递归与非递归实现。

下次总结二叉树的查找、求二叉树的深度、统计节点个数与节点比较的递归实现。

二叉树的结构定义为：

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

前序遍历

前序遍历的递归实现，中序遍历、后序遍历的递归实现同理：

public void preOrder(TreeNode t) {
    if (t != null){
        System.out.println(t.val);
        preOrder(t.left);
        preOrder(t.right);
    }
}

前序遍历的非递归实现：

public void preOrder(TreeNode t) {
    Stack<TreeNode> nodeStack = new Stack<>();//初始化栈
    TreeNode root = t;//保存当前节点
    //当前节点与栈不同时为空，则进行循环
    while (root != null || !nodeStack.isEmpty()) {
        //找到最左端节点
        while (root != null) {
            System.out.println(root.val);//输出当前节点
            nodeStack.push(root);//当前节点入栈
            root = root.left;//访问左子树
        }
        //左子树遍历后，出栈访问右子树
        if (!nodeStack.isEmpty()) {
            root = nodeStack.pop();
            root = root.right;
        }
    }
}

中序遍历

中序遍历的递归实现，同理：

public void medOrder(TreeNode t) {
    if (t != null){
        preOrder(t.left);
        System.out.println();
        preOrder(t.right);
    }
}

中序遍历的非递归实现，与前序遍历不同的就是在找最左端节点时不输出当前节点：

public void medOrder(TreeNode t) {
    Stack<TreeNode> nodeStack = new Stack<>();//初始化栈
    TreeNode root = t;//保存当前节点
    //同样，当前节点与栈不同时为空，则循环
    while (root != null || !nodeStack.isEmpty()) {
        //寻找最左节点
        while (root != null) {
            nodeStack.push(root);//当前节点入栈
            root = root.left;
        }
        if (!nodeStack.isEmpty()) {
            root = nodeStack.pop();
            System.out.println(root.val);//输出当前节点
            root = root.right;//进入右子树
        }
    }
}

后序遍历

后序遍历的递归实现，同理：

public void postOrder(TreeNode t) {
    if (t != null){
        preOrder(t.left);
        preOrder(t.right);
        System.out.println();
    }
}

后序遍历的非递归实现，需要注意的是得先访问父节点的两个子节点之后才能访问父节点，需要使用一个last节点来记录上一次访问的节点，判断是否是当前节点的右子节点，若是，则说明当前左右子树均已访问，则输出当前节点，否则访问其右子树：

public static void postOrder(TreeNode root) {
    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
    TreeNode node = root;//记录当前节点
    TreeNode lastVisit = root;//记录当前节点的右子树
    while (node != null || !treeNodeStack.isEmpty()) {
        //找到最左边的节点
        while (node != null) {
            treeNodeStack.push(node);
            node = node.left;
        }
        //查看当前栈顶元素
        node = treeNodeStack.peek();
        //如果其右子树也为空，或者右子树已经访问
        //则可以直接输出当前节点的值
        if (node.right == null || node.right == lastVisit) {
            System.out.print(node.val + " ");
            treeNodeStack.pop();
            lastVisit = node;
            node = null;
        } else {
            //否则，继续遍历右子树
            node = node.right;
        }
    }
}