二叉树遍历(先序、中序、后序)的实现

dxxbjl

二叉树1、二叉树是什么

二叉树是由n个结点构成的有限集合，n=0时为空树，n>0时为非空树。


非空树：

• 有且仅有一个根结点；
• 除根结点外的其余结点又可分为两个不相交的子集Left 和Right ,分别称为此二叉树的左子树和右子树，且Left 和Right 本身又都是二叉树
  

2、二叉树的遍历

• 先序遍历  --  根左右
• 中序遍历  --  左根右
• 后序遍历  --  左右根
  

3、代码实现

[Java] 纯文本查看 复制代码

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}

public class Solution {
    /**
     * 
     * [url=home.php?mod=space&uid=952169]@Param[/url] root TreeNode类 the root of binary tree
     * [url=home.php?mod=space&uid=155549]@Return[/url] int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        //创建三个集合，分别用来存放先序、中序、后序
        List<Integer> front =new ArrayList<>();
        List<Integer> middle =new ArrayList<>();
        List<Integer> back = new ArrayList<>();

        preOrder (root,front);
        inOrder  (root,middle);
        postOrder(root,back);
        System.out.println(front);
        System.out.println(middle);
        System.out.println(back);

        //使用二维数组来接收
        int [][] res =new int [3][front.size()];
        for(int i = 0; i<front.size();i++){
            res[0][i] = front.get(i);
            res[1][i] = middle.get(i);
            res[2][i] = back.get(i);
        }
        //结果返回二维数组形式
        return res;

    }

    //先序遍历 -- 根 左 右
    public void preOrder(TreeNode root ,List<Integer> list){
        if(root == null){
            return ;
        }
        //先放根节点
        list.add(root.val);
        //递归把左节点的值放入list
        preOrder(root.left,list);
        //递归把右节点的值放入list
        preOrder(root.right,list);
    }

    //中序遍历 -- 左 根 右
    public void inOrder(TreeNode root ,List<Integer> list){
        if(root ==null){
            return;
        }
        //先放左节点
        inOrder(root.left,list);
        //根节点
        list.add(root.val);
        //右节点
        inOrder(root.right,list);
    }
    //后序遍历 -- 左 右 根
    public void postOrder(TreeNode root ,List<Integer> list){
        if(root ==null){
            return;
        }
        //先放左节点
        postOrder(root.left,list);
        //右节点
        postOrder(root.right,list);
        //根节点
        list.add(root.val);
        
    }

}

shodow123

后序遍历是左右根吧。。。

gngn39

lz后序遍历写错了

gngn39

先左后右的顺序不变，根节点在遍历顺序中的位置是区分遍历方式的关键。先根后左右叫做先序遍历；根在左右中间遍历叫做中序遍历；根在最后遍历叫做后序遍历。

侃遍天下无二人

shodow123 发表于 2023-3-30 21:39
后序遍历是左右根吧。。。

都一样，重点是根在最后

repaircat

昨天刚学的二叉树,理论是懂了,代码不懂

seawaycao

学习了，感谢分享

yypisco

二叉树的遍历每次都是当时懂下次忘

starkcccc

再来一个非递归遍历，统一一个模板就好了

cxp

请问这是C语言吗？感觉和学校里学的不太一样，我似乎也没看见主函数,可能是我学的太菜了