廖雪峰历时3个月打磨出价值1980的数据分析教程,终终终于免费啦!

文章目录
  1. 1. 二叉树的遍历
    1. 1.1. 中序遍历
    2. 1.2. 后序遍历
    3. 1.3. 先序遍历
    4. 1.4. 层序遍历

二叉树的遍历

  • 我用下图的树为例,做树的遍历:

    二叉树结构

  • 树节点的定义:

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
        public TreeNode(int val, TreeNode left, TreeNode right) {
            super();
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    
  • 树的结构的代码实现:

    public static void main(String[] args) {
           TreeNode e = new TreeNode(1);
           TreeNode g = new TreeNode(2);
           TreeNode h = new TreeNode(3);
           TreeNode i = new TreeNode(4);
           TreeNode d = new TreeNode(5,null,g);
           TreeNode f = new TreeNode(6,h,i); 
           TreeNode b = new TreeNode(7,d,e);
           TreeNode c = new TreeNode(8,f,null);
           TreeNode root = new TreeNode(9,b,c);
    }
    

中序遍历

  • 先处理左子树,然后处理当前节点,再处理右子树。
  • 对于一颗二叉查找树,所有的信息都是有序排列的,中序遍历可以是信息有序输出,且运行时间为O(n)。
  • 递归实现中序遍历:

    public static void printTree(TreeNode t){
           if(t!=null){
               printTree(t.left);
               System.out.print(t.val+" ");
               printTree(t.right);
           }
       }
    
  • 输出结果:

    5 2 7 1 9 3 6 4 8 
    

后序遍历

  • 先处理左右子树,然后再处理当前节点,运行时间为O(n)。
  • 递归实现后序遍历:

    public static void printTree(TreeNode t){
            if(t!=null){
                printTree(t.left);
                printTree(t.right);
                System.out.print(t.val+" ");
            }
        }
    
  • 输出结果:

    2 5 1 7 3 4 6 8 9 
    

先序遍历

  • 先处理当前节点,在处理左右子树。
  • 递归实现先序遍历:

    public static void printTree(TreeNode t){
            if(t!=null){
                System.out.print(t.val+" ");
                printTree(t.left);
                printTree(t.right);
            }
        }
    
  • 输出结果:

    9 7 5 2 1 8 6 3 4 
    
  • 有没有觉得树的先序,中序,后序遍历都非常简单,递归三行代码就搞定了。好吧,下边厉害的要来了

层序遍历

  • 层序遍历:所有深度为D的节点要在深度为D+1的节点之前进行处理,层序遍历与其他类型的遍历不同的地方在于它不是递归地执行的,它用到队列,而不使用递归所默示的栈。
  • 算法思想:
    1. 定义节点 TreeNode lastNode指向当前行最有节点,TreeNode nlastNode指向下一行最右节点。
    2. 利用队列,首先将根节点入队,再循环里出队,并将其子节点入队,定义TreeNode tmpNode节点指向当前出队列的节点,当tmpNode==lastNode时,代表当前行遍历结束,输出换行,再令lastNode=nlastNode,nlastNode在子节点入队列时指向下一行最右节点。循环直到对列为空就行。
  • 层序遍历代码:

    package Tree;
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    /*
     * 层序遍历
     * 
     */
    public class TreePrinter1 {
         public static int[][] printTree(TreeNode root) {
             List< List<Integer> > list = new ArrayList< List<Integer> >();
             list.add(new ArrayList<Integer>());
             Queue<TreeNode> queue = new LinkedList<TreeNode>();
                queue.add(root);
                TreeNode lastNode = root;    // 当前行最右节点
                TreeNode nlastNode = root;    // 下一行最右节点
                TreeNode tmpNode = null; 
                int hight = 0;                // 树的高度
                while(!queue.isEmpty()){
                    tmpNode = queue.poll();
                    if(tmpNode!=null){
                        list.get(hight).add(tmpNode.val);
                    }
                    if(tmpNode.left!=null){
                        queue.add(tmpNode.left);
                        nlastNode = tmpNode.left;
                    }
                    if(tmpNode.right!=null){
                        queue.add(tmpNode.right);
                        nlastNode = tmpNode.right;
                    }
                    if(tmpNode == lastNode){
                        lastNode = nlastNode;
                        hight++;
                        list.add(new ArrayList<Integer>());
                    }
                }
                int[][] data = new int[list.size()][];
                for(int i=0;i<list.size();i++){
                    for(int j=0;j<list.get(i).size();j++){
                        data[i][j] = list.get(i).get(j);
                    }
                }
    
            return data;
         }
         public static void main(String[] args) {
               TreeNode e = new TreeNode(1);
               TreeNode g = new TreeNode(2);
               TreeNode h = new TreeNode(3);
               TreeNode i = new TreeNode(4);
               TreeNode d = new TreeNode(5,null,g);
               TreeNode f = new TreeNode(6,h,i);
               TreeNode b = new TreeNode(7,d,e);
               TreeNode c = new TreeNode(8,f,null);
               TreeNode root = new TreeNode(9,b,c);
               int[][] data  =TreePrinter.printTree(root);
               for(int s=0;s<data.length;s++){
                   for(int j=0;j<data[s].length;j++){
                       System.out.print(data[s][j]+" ");
                   }
                   System.out.println();
               }
        }
    }
    
  • 输出结果:

    9 
    7 8 
    5 1 6 
    2 3 4 
    

科学上网(翻墙)教程!

更多精彩内容,请扫描二维码关注公众号:轮子工厂,公众号内回复:

1.回复【图书】:获取15本新手自学编程,零基础入门经典学习教材;
2.回复【我要造轮子】:获取100多本计算机类经典书籍;
3.回复【开发工具】:获取几大主流编程语言的开发工具~
4.回复【内推】:可帮你内推到大厂工作。
文章目录
  1. 1. 二叉树的遍历
    1. 1.1. 中序遍历
    2. 1.2. 后序遍历
    3. 1.3. 先序遍历
    4. 1.4. 层序遍历