二叉树的四种遍历算法实现

二叉树的遍历

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

二叉树结构

  • 树节点的定义:
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

原文发布于微信公众号 - 轮子工厂(Programmer-ing)

原文发表时间:2018-03-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 等价二叉树题目分析代码

检查两棵二叉树是否等价。等价的意思是说,首先两棵二叉树必须拥有相同的结构,并且每个对应位置上的节点上的数都相等。

884
来自专栏desperate633

LintCode 最近公共祖先题目代码

852
来自专栏计算机视觉与深度学习基础

Leetcode 103 Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' valu...

21110
来自专栏计算机视觉与深度学习基础

Leetcode 101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric arou...

17810
来自专栏desperate633

LintCode 二叉树的最小深度题目代码

620
来自专栏计算机视觉与深度学习基础

Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree. Not...

1976
来自专栏desperate633

LintCode 前序遍历和中序遍历树构造二叉树题目代码

802
来自专栏聊聊技术

原 数据结构-二叉搜索树(Binary S

3157
来自专栏计算机视觉与深度学习基础

Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is de...

2179
来自专栏desperate633

LintCode 把排序数组转换为高度最小的二叉搜索树题目分析代码

显然这个问题可以用递归解决。 中间的节点总是在根节点,所以我们不停的找到中间节点即可,然后分别递归处理左子树和右子树即可

1473

扫码关注云+社区

领取腾讯云代金券