普通二叉树的遍历与还原
二叉树是一种很重要的数据结构,一般的操作就是遍历和还原.
有着很多重要的应用,比如红黑树,二叉排序树(也叫二叉搜索树)查找性能很高, jdk8 hashmap是 基于红黑树实现的,如果对二叉树不了解,那么对二叉树的变形(搜索树,平衡树,堆排序)无从入手.
二叉树定义:(递归定义,这也意味着很多操作时递归进行的)
二叉树或为空树,或是由一个节根节点加上两棵分别称为左子树和右子树的,互不相交的二叉树组成
特点:
- 每个节点最多只有两棵子树,即节点度不大于2
- 子树有左右之分,不能颠倒
二叉树节点定义:BTreeNode.java
package top.forethought.trees;
import lombok.Data;
import java.util.Queue;
/**
* @author wangwei
* @date 2019/2/7 14:23
* @classDescription 二叉树节点
*
*/
@Data
public class BTreeNode <T> {
private T data;
private BTreeNode lChild;
private BTreeNode rChild;
public BTreeNode(T data) {
this.data = data;
lChild=null;
rChild=null;
}
二叉树的生成代码:
/**
* @author wangwei
* @date 2019/2/7 14:42
* @methodDescription 生成二叉树
* A
* /\
* B C
* / /\
* D E F
*/
public BTreeNode buildBinTree(){
BTreeNode node=new BTreeNode('A');
BTreeNode nodeB=new BTreeNode('B');
BTreeNode nodeC=new BTreeNode('C');
BTreeNode nodeD=new BTreeNode('D');
BTreeNode nodeE=new BTreeNode('E');
BTreeNode nodeF=new BTreeNode('F');
nodeB.setLChild(nodeD);
node.setLChild(nodeB);
node.setRChild(nodeC);
nodeC.setLChild(nodeE);
nodeC.setRChild(nodeF);
return node;
}
二叉树的层序遍历
层序遍历:就是对二叉树的每层从左到右依次输出
需要借助队列实现:
思路:将根节点入队
递归:
出队,打印出队节点的值,然候将出队节点的孩子节点入队
直到队列为空,层序遍历结束
代码实现:
/**
* 二叉树的层序遍历:利用队列先进先出的特点实现
* @param queue
*/
public static void visitBinTreeByHierarchy(Queue<BTreeNode> queue){
if(queue.isEmpty()){
return;
}
BTreeNode head= queue.remove();
System.out.println(" 节点 data:"+head.getData());
if(head.getLChild()!=null){
queue.add(head.getLChild());
}
if(head.getRChild()!=null){
queue.add(head.getRChild());
}
visitBinTreeByHierarchy(queue);
}
测试代码:
/**
* @author wangwei
* @date 2019/2/7 14:37
* @methodDescription 测试层序遍历:
* 每层将节点入队,出队时,孩子入队
*
*/
@Test
public void testVisitByHierarchy(){
BTreeNode tree=buildBinTree();
Queue<BTreeNode> queue=new ArrayDeque();
queue.add(tree);
BTreeNode.visitBinTreeByHierarchy(queue);
}
测试结果:
# 二叉树的先序,中序,后序遍历
先序:根,左,右 (先,中,后都是针对根节点的遍历位置)
中序:左,根,右
后序:左,右,根
1.先序遍历实现
/**
* @author wangwei
* @date 2019/2/7 15:21
* @methodDescription 先序遍历
* 使用队列记录遍历结果(后序的二叉树还原时需要用到)
*/
public static void preorderVisit(BTreeNode tree, Queue queue){
if(null==tree){
return ;
}
System.out.println(tree.getData());
queue.add(tree.getData());
preorderVisit(tree.getLChild(),queue);
preorderVisit(tree.getRChild(),queue);
}
测试代码:
@Test
/**
* @author wangwei
* @date 2019/2/7 15:29
* @classDescription 测试先序遍历
*
*/
public void testPreVisit(){
BTreeNode tree=buildBinTree();
Queue queue=new ArrayDeque();
BTreeNode.preorderVisit(tree,queue);
}
测试输出:
A B D C E F
2. 中序遍历实现
/**
* @author wangwei
* @date 2019/2/7 15:31
* @classDescription 中序遍历 左,根,右
*
*/
public static void inorderVisit(BTreeNode tree,Queue queue){
if(null== tree){
return;
}
inorderVisit(tree.getLChild(),queue);
System.out.println(tree.getData());
queue.add(tree.getData());
inorderVisit(tree.getRChild(),queue);
}
测试代码
public void testInorderVisit(){
BTreeNode tree=buildBinTree();
Queue queue=new ArrayDeque();
BTreeNode.inorderVisit(tree,queue);
}
测试输出
D B A E C F
3. 后序遍历实现
/**
* @author wangwei
* @date 2019/2/7 15:48
* @methodDescription 后序遍历: 左,右,根
*
*/
public static void postorderVisit(BTreeNode tree,Queue queue){
if(null==tree){
return;
}
postorderVisit(tree.getLChild(),queue);
postorderVisit(tree.getRChild(),queue);
System.out.println(tree.getData());
queue.add(tree.getData());
}
测试代码:
@Test
public void testPostorderVisit(){
BTreeNode tree=buildBinTree();
Queue queue=new ArrayDeque();
BTreeNode.postorderVisit(tree,queue);
System.out.println("队列:"+queue.toString());
}
测试输出:
D B E F C A
二叉树的还原
二叉树的还原是面试题中常考的,大多以选择题为主(我也发现有时是编程题的,编程还是比较麻烦的)
核心思想是:
- 先根据先序(或者后序) 确定根节点
- 中序序列中找到根节点位置,根节点将其分割成两棵子树的中序序列
- 对这两棵子树在先序(或者后序)中分别找到子树的根节点(如此递归下去),最终能够确定出一棵二叉树
能够确定一棵二叉树的序列是:
- 先序+中序
- 后序+中序(只能是这两个组合,一个确定根,一个划分子树)
还原代码实现:
1.先序+中序 二叉树还原
/**
* @author wangwei
* @date 2019/2/7 17:26
* @methodDescription 已知 先序,中序 还原二叉树
* 通过先序获取 根节点
* 先序: A B D C E F
* 中序: D B A E C F
*/
//rootIndex start-end 树中根节点在先序遍历序列中的位置
//start ,end 为此次所需要探测的子树(中序遍历序列的一个连续区间)
public static BTreeNode restoreBTreePreInorder(Object []preorderList, int rootIndex, Object []inorderList, int start, int end) {
if (null == preorderList || null == inorderList) {
return null;
}
if (preorderList.length != inorderList.length) {
throw new RuntimeException(" 先序遍历与中序遍历节点个数应该相等");
}
if(start>end){
return null;
}
//定位 当前start-end 这棵树的根节点在中序遍历中的位置
int targetIndex=0;
while (inorderList[targetIndex]!=preorderList[rootIndex]){
targetIndex++;
}
//左右子树根节点在中序遍历中的位置
//左子树的根节点位置 =rootIndex+1
int lChildRootIndex=rootIndex+1;
//右子树根节点位置=左子树根节点位置+左子树节点数
// 左子树节点数=targetIndex-start
int rChildRootIndex=lChildRootIndex+(targetIndex-start);
BTreeNode lChild= restoreBTreePreInorder(preorderList,lChildRootIndex,inorderList,start,targetIndex-1);
BTreeNode rChild= restoreBTreePreInorder(preorderList,rChildRootIndex,inorderList,targetIndex+1,end);
BTreeNode rootNode=new BTreeNode(preorderList[rootIndex]);
rootNode.setLChild(lChild);
rootNode.setRChild(rChild);
return rootNode;
}
测试代码:
/**
* @author wangwei
* @date 2019/2/7 16:50
* @methodDescription 测试二叉树还原
* 先序+中序 还原二叉树
*/
@Test
public void restoreBTree2(){
BTreeNode originTree=buildBinTree();
Queue preQueue=new ArrayDeque();
Queue inQueue=new ArrayDeque();
BTreeNode.preorderVisit(originTree,preQueue);
BTreeNode.inorderVisit(originTree,inQueue);
System.out.println("先序结果:"+preQueue.toString());
System.out.println("中序结果:"+inQueue.toString());
Object []preorderList=preQueue.parallelStream().toArray();
Object []inorderList=inQueue.parallelStream().toArray();
BTreeNode restoreTree=BTreeNode.restoreBTreePreInorder(preorderList,0,inorderList,0,inorderList.length-1);
System.out.println(restoreTree);
System.out.println("-------- 分割线--------- 还原后的遍历输出");
Queue preQueue2=new ArrayDeque();
Queue inQueue2=new ArrayDeque();
BTreeNode.preorderVisit(restoreTree,preQueue2);
BTreeNode.inorderVisit(restoreTree,inQueue2);
System.out.println("先序结果:"+preQueue2.toString());
System.out.println("中序结果:"+inQueue2.toString());
}
测试输出:
2.后序+中序 二叉树还原
/**
* 思路:先根据后序遍历得到 根节点 A
* 再检查中序遍历 A 的左右两侧,可以得出 左子树是 D B 右子树是 E C F
* 后序遍历序列中删除 节点A ,得到 C, 说明子树 ECF 中 C 为根节点,E,F 分别为左右孩子
* 后序序列中弹出 E,F,得到B,说明 子树DB 中 B 为根节点,
* 再检查中序遍历,得出D 为B的左孩子
*
*/
// start end 表示当前处理的中序遍历区间 start-end 为一棵树
// rootIndex 表示该趟 start-end 这棵树的根节点在后序遍历中的位置
public static BTreeNode restoreBTreePostInorder(Object []postorderList, int rootIndex, Object []inorderList, int start, int end) {
if (null == postorderList || null == inorderList) {
return null;
}
if (postorderList.length != inorderList.length) {
throw new RuntimeException(" 后序遍历与中序遍历节点个数应该相等");
}
if(start>end){
return null;
}
//定位 当前start-end 这棵树的根节点在中序遍历中的位置,然后对左右子树进行相似的递归处理
int targetIndex=0;
while (inorderList[targetIndex]!=postorderList[rootIndex]){
targetIndex++;
}
//左右子树根节点在后序遍历中的位置
//左子树的根节点位置 =rootIndex-右子树节点个数-1 (这里的1表示根节点占一个位置,这是在后序遍历中的计算,结果是左子树在 后序遍历中的位置)
//右子树节点个数 = end-targetIndex (这是在中序遍历中的计算,)
//右子树根节点位置=rootIndex-1
int rChildRootIndex=rootIndex-1;
//左子树节点位置=右子树根节点-右子树节点个数
int lChildRootIndex=rChildRootIndex-(end-targetIndex);
BTreeNode lChild= restoreBTreePostInorder(postorderList,lChildRootIndex,inorderList,start,targetIndex-1);
BTreeNode rChild= restoreBTreePostInorder(postorderList,rChildRootIndex,inorderList,targetIndex+1,end);
BTreeNode rootNode=new BTreeNode(postorderList[rootIndex]);
rootNode.setLChild(lChild);
rootNode.setRChild(rChild);
return rootNode;
}
测试代码:
@Test
public void restoreBTree(){
BTreeNode originTree=buildBinTree();
Queue postQueue=new ArrayDeque();
Queue inQueue=new ArrayDeque();
BTreeNode.postorderVisit(originTree,postQueue);
BTreeNode.inorderVisit(originTree,inQueue);
System.out.println("后序结果:"+postQueue.toString());
System.out.println("中序结果:"+inQueue.toString());
Object []postorderList=postQueue.parallelStream().toArray();
Object []inorderList=inQueue.parallelStream().toArray();
BTreeNode restoreTree=BTreeNode.restoreBTreePostInorder(postorderList,postorderList.length-1,inorderList,0,inorderList.length-1);
System.out.println(restoreTree);
System.out.println("-------- 分割线--------- 还原后的遍历输出");
Queue postQueue2=new ArrayDeque();
Queue inQueue2=new ArrayDeque();
BTreeNode.postorderVisit(restoreTree,postQueue2);
BTreeNode.inorderVisit(restoreTree,inQueue2);
System.out.println("后序结果:"+postQueue2.toString());
System.out.println("中序结果:"+inQueue2.toString());
}
测试输出:
总结:
- 二叉树的遍历通常使用递归,便于理解
- 二叉树的还原关键是先确定根节点,然候在中序遍历序列中根据确定的根节点去分隔成为两棵子树,然后确定两棵子树的根节点,递归执行