图片对话中二叉树的前序，中阶，后序，层次遍历方法

示例图片

有很多遍历树的方法. 其中，树的前遍历，中间遍历和后遍历遍历方法在原理和代码实现上都非常相似，因此将它们汇总在一起. 前序，中序和后序三种遍历方法的区别在于根节点的遍历顺序不同.

预遍历: 首先输出根节点，然后依次遍历左右子树.

有序遍历: 左子树的第一个有序遍历，在输出根节点处二叉排序树中序遍历，最后是子树的有序遍历

后序遍历: 依次遍历左侧子树，然后依次遍历右侧子树，最后输出根节点

对于图3-1中所示的二叉树，三个遍历的结果如下:

遍历顺序: 1、2、4、5、3、6、7；

序列遍历: 4、2、5、1、3、7、6

后遍历: 4、5、2、7、6、3、1

三种遍历方法的递归实现代码如下:

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

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

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

从以上代码可以看出，用于递归二叉树实现的遍历代码相当简短. 三种遍历方法之间的区别在于节点值的输出时序.

图4-1

树的分层遍历是一种从上到下以及从左到右的遍历方法. 对于图4-1中所示的树结构，遍历层次结构的顺序如下: 4-5-6-7.

树遍历的实现方法不同于树的前遍，中阶和后遍的方法. 树级遍历是使用队列实现的，而其他三种遍历方法是使用堆栈和递归代码实现的. 下面通过图描述遍历下一层的过程，同时给出了Java代码的实现.

将根节点放入队列中，队列情况如下

图片

确定队列是否为空. 如果不为空，则队列的第一个元素（非空，如果为空，则继续出队直到它不为空），然后进行打印，如图所示

图片

将出队元素的左右节点放入队列中，如图所示

图片

重复步骤2-3，直到队列2为空并且循环结束.

对于图4-1中所示的二叉树，层次遍历的其余过程如下:

图片

通过以上流程图，遍历二叉树级别的过程非常清楚. 在这个过程中，可能会有一个疑问: 在上面的过程中，我们还为null元素输入了队列操作. 为什么此操作不省略，仅排队非空节点？如果仅需要根据层次结构遍历的结果从上至下，从左至右打印二叉树的元素，则使非空元素入队是理想的操作，但是节点的级别信息将是丢失. 例如二叉排序树中序遍历，要首先请求以下格式的二叉树层次结构遍历结果的输出，必须排队非空元素以保留节点层次结构信息.

[[1],[2,3],[4,5,6],[7]]

public voidprintLevel(TreeNode root){
           inti=1; //每层应该有多少节点
           intj=0;//每层的空节点数
           Queue<Integer>queue= new LinkedList<Integer>();
           queue.add(root);
           List<List<Integer>> result = new ArrayList<List<Integer>>();
           List<Integer>list = new ArrayList<Integer>();
           while(queue.isEmpty()){
                 TreeNodenode =queue.remove();
                      j++;
                      continue;
                   }
           list.add(node.val);
           queue.add(node.left);
           queue.add(node.right);
          //如果非空节点数+空节点数=该层节点数，则存储层信息
          if( i==(list.size()+j) &&list.size()>0 ){
              List<Integer> temp =new ArrayList<Integer>();
             //复制链接操作，自己实现
             copy(temp,list);
             result.add(temp);
             list.clear();
             i=i*2;//节点总数每层倍增
             j=j*2;//空节点数每层倍增
         }
   }
     System.out.println(result);
}

参考:

[1]数据结构和算法Java语言描述版本

[2]原始博客链接

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-204944-1.html