算法：二叉树遍历-理论

营琪

发布于 2019-11-04 16:35:49

4450

发布于 2019-11-04 16:35:49

文章被收录于专栏：营琪的小记录

本文链接：https://blog.csdn.net/weixin_43126117/article/details/98937218

前中后序遍历在平时用的不多，实际上用到更多是深度优先和广度优先算法，那为什么要遍历二叉树呢！好像也就仅仅输出数据而已，但是对于二叉搜索树，中序遍历，就可以输出一个有序的结果了。

什么是前中后序遍历

1. 前序(Pre-order)：根-左-右
2. 中序(In-order)：左-根-右
3. 后序(Post-order)：左-右-根

注意根节点的位置，根节点在前那就是前序遍历，根节点在后，那就是后序遍历!

下面给出遍历的代码，需要注意的是，树的结构代码（不含父节点引用）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

前序遍历

方法一：递归

public void preorder(TreeNode node) {
        System.out.print(node.val);
        if (node.left != null) preorder(node.left);
        if (node.right !=null) preorder(node.right);
    }

方法二：迭代

思路：因为当前节点并未保存父亲节点的引用，迭代的时候，只能改变一个只进行迭代，那么另外一个（左右）节点就丢失了，那么我们需要借助另外的数据结构存储一下。

public void preorder2(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        if (node != null) {
            stack.push(node);
        }
        while (!stack.isEmpty()) {                        //先出左节点，再出相邻右节点
            TreeNode pop = stack.pop();
            System.out.print(pop.val);
            if (pop.right != null) stack.push(pop.right); //每次都把左右节点存进去
            if (pop.left != null) stack.push(pop.left);
        }
    }

中序遍历

方法一：递归

public void inorder(TreeNode node) {
        if (node.left != null) inorder(node.left);
        System.out.print(node.val);
        if (node.right !=null) inorder(node.right);
    }

方法二：迭代

    public void inorder2(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        while (node != null||!stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;            //先把左边全部存入
            }
            node = stack.pop();              //取得最左边
            System.out.print(node.val);
            node = node.right;                //检查最左边的右节点
        }
    }

后序遍历

方法一：递归

public void postorder(TreeNode node) {
        if (node.left != null) postorder(node.left);
        if (node.right !=null) postorder(node.right);
        System.out.print(node.val);
    }

方法二：迭代1

思路：这个比较有技巧，前序遍历是 “根》左》右” ，把前序遍历的左右调换 “根》右》左” ，再把这个结果反转“左》右》根”

public void postorder3(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> reverse = new Stack<>();         ////建立多个栈，作为反转，先入后出
        if (node != null) {
            stack.push(node);
        }
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            reverse.add(pop.val);                        //建立多个栈，作为反转
            if (pop.left != null) stack.push(pop.left);       //先存入左边，  那么就先出右边  根》 右 》左
            if (pop.right != null) stack.push(pop.right);
        }
        while (!reverse.isEmpty()) {                    //直接输出就可以了
            System.out.print(reverse.pop());
        }
    }

方法二：迭代2

思路：这个借鉴了中序遍历“左根右”，先获取所有左节点，再次证明当前节点是左节点就行。

即：当前节点存在右节点，则证明是根节点。

假如是根节点，则把根节点的右节点再次重复（先获取所有左节点，再次证明当前节点是左节点）

这里需要保存上一个节点，防止一直重复右节点。（例如：获取栈->存在右节点->右节点重复->再获取栈->存在右节点,其实就是一直未出栈，导致重复了。获取栈->上一节点->存在右节点）

public void postorder2(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode last = null;
        while (node != null || !stack.isEmpty()) {      
            while (node != null) {                  //获取全部左节点
                stack.push(node);
                node = node.left;
            }
            node = stack.peek();                    //没有出栈，只是赋值，  这个节点可能根节点 或者左节点
            if (node.right == null || node.right == last) {        //证明是左节点，last的作用 防止多次重复。
                System.out.print(node.val);
                stack.pop();                        //出栈
                last = node;                    
                node = null;
            } else {                                               //否则就是根节点，再次重复上面过程。
                node = node.right;
            }
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/08/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度