二叉树的各种遍历方法总结|Java刷题打卡

前序遍历二叉树

前，中，后序遍历都是以根节点为参考，前序遍历就是先根节点再左右子树

先访问根节点，再访问左子树，再访问右子树

前序遍历结果为F, B, A, D, C, E, G, I, H

递归法

// 二叉树的存储结构
public class TreeNode {
    char val;

    //左子树
    TreeNode left;
    //右子树
   TreeNode right;

    //构造方法
    TreeNode(char x) {
        val = x;
    }
}
复制代码

public static void preOrderTraversal(TreeNode root) {
        System.out.println(root.val);
        if (root.left != null) {
            preOrderTraversal(root.left);
        }
        if (root.right != null) {
            preOrderTraversal(root.right);
        }
    }
复制代码

非递归法

如上图，前序遍历A的下一个节点是D，只有通过A的父节点B才能找到D，我们要从A往回找，可以通过栈来实现。

我们从根节点开始向左孩子遍历，每遍历一个节点就把它放到栈里边，如果左孩子为空，则要弹出栈顶元素，找它的右孩子。

比如上图，我们遍历到A，打印了F，B，A，栈中元素是F，B，A，A没有左孩子，把A弹出来，找A的右孩子，A没有右孩子，就再弹出B，找B的右孩子D，打印D，把D进栈，D有左孩子C，打印C，把C进栈，C没有左孩子，就把C弹出来，找C的右孩子。。。。

public static void preOrderTraversal2(TreeNode root) {
        Stack<TreeNode> treeNodeStack = new Stack<>();
        while (root != null || !treeNodeStack.isEmpty()) {
            if (root != null) {
                System.out.print(root.val + "\t");
                treeNodeStack.push(root);
                root = root.left;
            }
            if (root == null && !treeNodeStack.isEmpty()) {
                root = treeNodeStack.pop();
                root = root.right;
            }
        }
    }
复制代码

中序遍历二叉树

根节点在左右子树之间，先访问左子树，再访问根节点，再访问右子树

中序遍历结果A, B, C, D, E, F, G, H, I

递归法

public static void inOrderTraversal(TreeNode root) {
        if (root.left != null) {
            inOrderTraversal(root.left);
        }
        System.out.print(root.val + "\t");
        if (root.right != null) {
            inOrderTraversal(root.right);
        }
    }
复制代码

非递归法

中序遍历依然要访问父节点，所以也可以用栈来实现。过程其实跟先序遍历一样，不一样的是打印节点的时机。先序遍历是要进栈时打印元素，中序遍历是元素要出栈时打印

从根节点开始访问左子树，并把它们加入到栈中，访问到A时，栈中元素是F，B，A，A没有左子树，A出栈并打印，A的右子树为空，那么B出栈并打印，出栈后都访问这个元素的右节点，B有右孩子D，D进栈，进栈后都访问左孩子，C进栈。。。

public static void inOrderTraversal2(TreeNode root) {
        Stack<TreeNode> treeNodeStack = new Stack<>();
        while (root != null || !treeNodeStack.isEmpty()) {
            if (root != null) {
                treeNodeStack.push(root);
                root = root.left;
            }
            if (root == null && !treeNodeStack.isEmpty()) {
                root = treeNodeStack.pop();
                System.out.print(root.val + "\t");
                root = root.right;
            }
        }
    }
复制代码

后序遍历

后序遍历就是先左右子树，最后根节点。先访问左子树，再访问右子树，最后访问根节点

后序遍历结果 A, C, E, D, B, H, I, G, F.

递归法

递归方法都很简单，很容易写出来

 public static void postOrderTraversal(TreeNode root) {
        if (root.left != null) {
            postOrderTraversal(root.left);
        }
        if (root.right != null) {
            postOrderTraversal(root.right);
        }
        System.out.print(root.val+ "\t");
    }
复制代码

非递归

由上图的遍历顺序可以看出来，如果当前节点左右孩子都为空或者当前节点左右孩子都被打印过，那么这个节点现在也要打印

依然用栈实现，比如访问到A时，栈中节点是F，B，A，当前节点A的左右孩子都为空，打印并弹出A。获得栈顶元素B，B有右孩子D，D进栈，D有左孩子C，C进栈，C没有左右孩子，打印并弹出C。获得栈顶元素D，D的右孩子E进栈，打印并弹出E。获得栈顶元素D，D的右孩子被访问过，打印并弹出D。获得栈顶元素B，B的右孩子被访问过，打印并弹出B。。。

public static void postOrderTraversal2(TreeNode root) {
        Stack<TreeNode> treeNodeStack = new Stack<>();
        TreeNode visited = root;
        TreeNode curNode = root;
        while (root != null || !treeNodeStack.isEmpty()) {
            // 左孩子都入栈
            while (root != null) {
                treeNodeStack.push(root);
                root = root.left;
            }
            // curNode节点的左孩子为空（或被访问过）
            curNode = treeNodeStack.peek();
            // curNode的右孩子也为空或被访问过就要打印
            if(curNode.right == null || curNode.right == visited){
                root = treeNodeStack.pop();
                System.out.print(root.val + "\t");
                visited = root;
                root = null;
            }else{
                root = curNode.right;
            }
        }
    }
复制代码

层次遍历

从树的根节点开始，一层一层向下遍历

层次遍历结果F, B, G, A, D, I, C, E, H

可以用队列来实现，先将根节点F入队，根节点出队并打印，有左孩子B就将左孩子入队，有右孩子G就将右孩子入队，队列头节点B出队并打印，左孩子A右孩子D入队，队列头节点G出队并打印，右孩子I入队，现在队列是A，D，I，队列头节点A出队并打印

public static void levelraversal(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while (queue.size() != 0) {
            TreeNode curNode = queue.poll();
            System.out.print(curNode.val + "\t");
            if (curNode.left != null)
                queue.add(curNode.left);
            if (curNode.right != null)
                queue.add(curNode.right);
        }
    }
复制代码