⼆叉树的遍历（前中后序遍历、层序遍历及相关选择题详解）以及⼆叉树的基本
操作【数据结构】
⽂章⽬录
前⾔：简单创建⼀棵⼆叉树
在学习⼆叉树的基本操作前，需要先创建⼀棵⼆叉树，由于现在我们还是初学者，理解还不够深⼊，这⾥⼿动快速的创建⼀颗简单的⼆叉树，等之后⼆叉树的结构了解的差不多时，我们还会研究其真正的创建⽅式。
public class BinaryTree {
public static class BTNode{
BTNode left;
BTNode right;
先序中序后序遍历二叉树int value;
BTNode(int value){
this.value=value;
}
}
private BTNode root;
public void createBinaryTree(){
BTNode node1=new BTNode(1);
BTNode node2=new BTNode(2);
BTNode node3=new BTNode(3);
BTNode node4=new BTNode(4);
BTNode node5=new BTNode(5);
BTNode node6=new BTNode(6);
root=node1;
node1.left=node2;
node2.left=node3;
node1.right=node4;
node4.left=node5;
node4.right=node6;
}
}
创建的树如下图所⽰：
⼀、⼆叉树的遍历
1.前中后序遍历
遍历是指沿着某条搜索路线，依次对树中每个结点均做⼀次且仅做⼀次访问。
访问结点所做的操作依赖于具体的应⽤问题（⽐如：打印结点内容、结点内容加1）。
在遍历⼆叉树时，如果没有进⾏某种约定，每个⼈按照⾃⼰的⽅式进⾏遍历，遍历的结果就会⽐较混乱，这时候就需要指定某种规则，使得每⼀个⼈的遍历结果是相同的。
事先声明，由于刚刚了解，这⾥的代码都采⽤递归⽅式来实现，后续有更优化的⽅法。⾯试过程中加⼊
⾯试官让写千万不能写递归根据遍历根节点的先后次序有以下遍历⽅式：
1.前序遍历（也称先序遍历）： 访问根结点—>根的左⼦树—>根的右⼦树
图解：
代码实现：
//前序遍历
public void preOrder(BTNode treeRoot){
if(treeRoot!=null){
//1.先遍历根结点
System.out.print(treeRoot.value+" ");
//2.再遍历根结点的左⼦树---注意：根结点的左⼦树也是⼆叉树，遍历根结点的左⼦树与遍历原树的规则相同
preOrder(treeRoot.left);
//3.再遍历根结点的右⼦树---注意：根结点的右⼦树也是⼆叉树，遍历根结点的右⼦树与遍历原树的规则相同
preOrder(treeRoot.right);
}
}
打印结果：
2.中序遍历： 根的左⼦树—>根结点—>根的右⼦树
图解：
代码实现：
//中序遍历
public void inOrder(BTNode treeRoot){
if(treeRoot!=null){
//1.先遍历根结点的左⼦树---注意：根结点的左⼦树也是⼆叉树，遍历根结点的左⼦树与遍历原树的规则相同
inOrder(treeRoot.left);
//1.再遍历根结点
System.out.println(treeRoot.value+" ");
//3.再遍历根结点的右⼦树---注意：根结点的右⼦树也是⼆叉树，遍历根结点的右⼦树与遍历原树的规则相同
inOrder(treeRoot.right);
}
}
打印结果：
3.后序遍历： 根的左⼦树—>根的右⼦树—>根结点
图解：
代码实现：
//后序遍历
public void postOrder(BTNode treeRoot){
if(treeRoot!=null){
//1.先遍历根结点的左⼦树---注意：根结点的左⼦树也是⼆叉树，遍历根结点的左⼦树与遍历原树的规则相同
postOrder(treeRoot.left);
//3.再遍历根结点的右⼦树---注意：根结点的右⼦树也是⼆叉树，遍历根结点的右⼦树与遍历原树的规则相同
postOrder(treeRoot.right);
//1.再遍历根结点
System.out.print(treeRoot.value+" ");
}
}
打印结果：
注意：
前⾯这三个遍历，在我们测试的时候，都需要传⼊树的根结点：
bt.);
本来bt已经是⼆叉树了，每⼀次还要传⼊参数就显得多此⼀举，能否在遍历期间不传⼊参数但也使⽤递归的⽅法呢？
⼀般情况下函数能不给参数就不给参数，可以给⼀个尽量不要给两个
因为参数越多，⽤户在使⽤时的成本就越⼤，⽤户就需要搞清楚这个参数到底是什么意思，当帮助⽂档写的不是很详细，⽤户可能会搞错，出错的风险就很⼤
//将上述递归⽅式再包装⼀层
public void preOrder(){
preOrder(root);
}
public void inOrder(){
inOrder(root);
}
public void postOrder(){
postOrder(root);
}
同时我们把上边写的递归代码访问权限改为private，让⽤户不去调⽤它，后⾯在主函数中直接调⽤我们重新写的即可。
2.层序遍历
除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。
3.选择题
1.某完全⼆叉树按层次输出（同⼀层从左到右）的序列为ABCDEFGH，该完全⼆叉树的前序序列为（）
A：ABDHECFG    B：ABCDEFGH    C：HDBEAFCG  D：HDEBFGCA
因为是完全⼆叉树，完全⼆叉树是满⼆叉树的⼀部分，我们先把它画出来：
前序序列：根结点—左⼦树—右⼦树：ABDHECFG
2.⼆叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG，则⼆叉树的根结点为（）
A：E    B：F    C：G  D：H
先序遍历是先打印根结点，所以根结点为E
3.设⼀棵⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为（）
A：abdce    B：decab    C：debac  D：abcde
根据后序遍历的性质得：后序遍历是最后打印根结点，倒数第⼆个打印右⼦树的根结点
所以由后序遍历可得：c是右⼦树的根结点，a为根结点
根据中序遍历的性质以及a为根结点可得：
以a为分界线，左边是左⼦树，右边为右⼦树：b为左⼦树，dce为右⼦树，同时c⼜是右⼦树的根结点。
分析⾄此，图可以画出来：
前序遍历：根结点—左⼦树—右⼦树：abcde
4.某⼆叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同⼀层从左到右）的序列为（）A：FEDCBA    B：CBAFED    C：DEFCBA  D：ABCDEF
中序遍历：左⼦树—根结点—右⼦树
后序遍历：左⼦树—右⼦树—根结点
⼆者序列相同只有⼀种情况，就是⽆右⼦树，只有左⼦树—根结点
同时有后序遍历最后⼀个为F确定，F为根结点，出来结果就类似⼀条链表：
⼆、⼆叉树的基本操作
1.获取树中结点的个数
//获取⼆叉树中结点的个数
private int size(BTNode treeRoot){
if(treeRoot==null){
return0;
}
return1+size(treeRoot.left)+size(treeRoot.right);
}
2.获取叶⼦结点的个数：
//获取⼆叉树中结点的个数
private int size(BTNode treeRoot){
if(treeRoot==null){
return0;
}
return1+size(treeRoot.left)+size(treeRoot.right);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。