大家好，欢迎来到IT知识分享网。
今天是端午节，祝大家端午节快乐，端午安康！~
二叉树顾名思义是一个只有两个结点的树，分为left结点和right结点。今天我们就来对二叉树的遍历方式进行一个总结回顾。
二叉树是由一个个结点构成的，那么每个结点长什么样呢？我们先定义一下看看结点长什么样：
树的结点：
class Node{
private int no;
private String name;
private Node left;
private Node right;
//还有下面的这些方法，就不写出来l
//构造器
//toString方法
//get
//set
}
从上面可以看出，每个结点都分为左结点和右节点；这些就构成了树的左子树和右子树。
二叉树的遍历
主要分为前序遍历、中序遍历、后序遍历。他们之间的区别在于根节点(root)结点遍历的顺序。
前序遍历就是先遍历根结点，再遍历左子树，最后遍历右子树；
中序遍历就是先遍历左子树，再遍历root结点，最后遍历右子树；
后序遍历就是先遍历左子树，再遍历右子树，最后遍历根结点。
我们以上面这个图为例：前序遍历的结果是：ABCDEF。中序遍历的结果是：CBDAEF。后序遍历的结果是：CDBFEA。
知道遍历的顺序之后我们就来实现它，那问题又来了，我们该怎么实现它？解决的办法就是用神器递归。
注意：本文三种遍历写在结点（node）里面，当然也可以写在构造的二叉树里面
前序遍历:
public void preOrder(){
System.out.println(this);
if(this.left != null){
this.left.preOrder();
}
if(this.right != null){
this.right.preOrder();
}
}
代码是不是很简洁，其实实现原理很简单就是先输出当前结点（可能会有人要问，你为啥不判断当前结点是不是null，就直接输出？原因就是我是遍历方法写在结点里的呀，已经进入结点了，所以就不用判断了，不然可不是就成了“证明你是你”的问题里的嘛。）对左子树进行递归查找，然后回溯，最后在对右子树进行遍历查找。在进行左子树和右子树遍历之前一定要先看看他们在不在，如果都不在就找不到了同理，咱们可以得到中序和后序的遍历：
中序遍历:
public void midOrder(){
if(this.left != null){
this.left.midOrder();
}
System.out.println(this);
if(this.right != null){
this.right.midOrder();
}
}
后序遍历：
public void postOrder(){
if(this.left != null){
this.left.postOrder();
}
if(this.right != null){
this.right.postOrder();
}
System.out.println(this);
}
好了，这就是二叉树的前、中、后遍历；总结一下就是按照前、中、后的遍历定义，先去看看在不在家，在家就去遍历他，然后在看看他的左子树在不在家，以此类推。
那我们来在二叉树中调用一下它，首先我们先构造一个二叉树：
class BinarTree{
//一个树是不是得有一个根，所以我们先定义一个根结点
private Node root;
//给这个根结点赋值
public void setNode(Node root){
this.root=root;
}
//前序遍历
//中序遍历
//后序遍历
}
定义完二叉树之后，我们来进行遍历的调用:
前序遍历的调用：
public void preOrder(){
//先判断根结点存不存在
if(this.root != null){
this.root.preOrder();
}else{
System.out.println("二叉树为空，不能遍历");
}
}
中序遍历的调用
public void midOrder(){
if(this.root != null){
this.root.midOrder();
}else{
System.out.println("二叉树为空，不能遍历");
}
}
后序遍历的调用：
public void postOrder(){
if(this.root != null){
this.root.postOrder();
}else{
System.out.println("二叉树为空，不能遍历");
}
}
好了，以上就是二叉树的前序、中序、后序遍历的所有内容。
等等…你说好多都是用前序、中序、后序遍历进行查找的啊，这个怎么写？
这个嘛，一样的思路：
先进行前序、中序、后序的遍历查找，按照遍历的方式进行递归查找，找到了就返回这个节点，否则的话就继续递归遍历查找
代码如下：
//前序遍历查找
public Node preOredrSearch(int no){
//比较当前节点是不是
if(this.no == no){
return this;
}
//找到节点接返回
//向左找
Node resNode =null;
if(this.left != null){
resNode = this.left.preOredrSearch(no);
}
if(resNode != null){
return resNode;
}
//向右找
if(this.right != null){
resNode = this.right.preOredrSearch(no);
}
return resNode;
}
//中序遍历查找
public Node midOrderSearch(int no){
Node resNode = null;
if(this.left != null){
resNode = this.left.midOrderSearch(no);
}
//判断是否找到
if(resNode != null){
return resNode;
}
if(this.no == no){
return this;
}
if(this.right != null){
resNode = this.right.midOrderSearch(no);
}
return resNode;
}
//后序
public Node postOrderSearch(int no){
Node resNode=null;
if(this.left != null){
resNode =this.left.postOrderSearch(no);
}
//判断不为空就return
if(resNode != null){
return resNode;
}
if(this.right != null){
resNode= this.right.postOrderSearch(no);
}
if(this.no == no){
return this;
}
return resNode;
}
在二叉树中的调用如下：
//前序遍历查找调用
public Node preOrderSearch(int no){
if(root != null){
return root.preOredrSearch(no);
}else{
return null;
}
}
//中序遍历查找调用
public Node midOrderSearch(int no){
if(root != null){
return root.midOrderSearch(no);
}else{
return null;
}
}
//后序遍历查找调用
public Node postOrderSearch(int no){
if(root != null){
return root.postOrderSearch(no);
}else{
return null;
}
}
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/24098.html
