在上节我们对二叉树基本的操作有了一定的认识,熟悉了二叉树的三种遍历方式分别是:前序遍历和中序遍历以及后序遍历操作,这节的操作我们还会基于上节的基础上来完成的,首先来看下我们的基本需求:
需求:
我们利用二叉树的三种遍历方式来实现指定节点的查找如: heroNode=5的节点
看完了需求我们来分析下,首先来看我们的图:
图.png
首先我们需要新增节点5同时将它设置为节点3的左子节点,我们分别来看下这三种的遍历查找的思路分析:
- 前序遍历查找思路分析:
1.首先判断当前节点的编号(no)跟我们要查找的是否是同一个,如果是直接返回即可.
2.如果不相等,我们需要判断当前节点的左子节点是否为null,不为null则递归前序遍历去找,如果找到了就返回即可
3.如果在左子节点中没有找到,我们需要首先 判断右子节点是否为null,如果不为null则递归前序遍历去找,如果找到了就返回即可
我们看完了前序遍历查找的思路分析,我们接着通过代码来实现,首先来看HeroNode的代码实现:
//节点查找方法
//前序遍历查找
/**
*
* @param no 要查找节点的编号
* @return
*/
public HeroNode queryPreOrder(int no){
//1.首先和root节点记性比较
if (this.no == no){ //表示已经找到了
return this;
}
//2.没有找打,先判断左子节点是否为null,如果不为null,则我们递归前序找
HeroNode heroResult = null;
if (this.left !=null){
heroResult = this.left.queryPreOrder(no);
if (heroResult !=null){
return heroResult;
}
}
//如果左子节点没有找到,我们继续找
//判断右子节点是否为null,如果不为null,则我们递归前序找
if (this.right !=null){
heroResult = this.right.queryPreOrder(no);
}
return heroResult;
}
上述代码就是HeroNode的前序遍历查找的具体代码实现过程,接着我们来看二叉树中是如何来调这个前序遍历的代码的,具体代码如下:
//前序遍历查找
public HeroNode queryPreOrder(int no){
if (root !=null){
return root.queryPreOrder(no);
}else {
return null;
}
}
接着我们来看测试代码,首先我们需要创建节点5,具体代码如下:
public static void main(String[] args) {
//测试
BinaryTree binaryTree = new BinaryTree();
//节点的创建
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
HeroNode node5 = new HeroNode(5,"关胜");
//设置二叉树跟节点
binaryTree.setRoot(root);
//手动创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
//将node5设置为节点3的左子节点
node3.setLeft(node5);
上述是节点5的创建和将它设置为节点3的左子节点,接着我们来看具体的测试代码:
System.out.println("前序遍历查找测试:");
HeroNode heroNode = binaryTree.queryPreOrder(5);
if (heroNode !=null){
System.out.printf("找到了,信息为 no=%d name= %s\t\n",heroNode.getNo(),heroNode.getName());
}else {
System.out.printf("没有找到,信息为 no=%d的英雄",5);
}
来看测试结果如下图所示:
前序遍历查找测试代码.png
上图结果所示我们找到了,接着我们来看中序遍历查找的过程
- 中序遍历查找的思路分析
1.首先需要我们判断当前节点的左子节点是否为null,不为null则递归中序遍历去找,如果找到了就返回即可
2.如果左子节点没有找到,则跟当前节点的编号(no)跟我们要查找的是否是同一个,如果是直接返回即可,没有的话继续找.
3.我们需要首先 判断右子节点是否为null,如果不为null则递归中序遍历去找,如果找到了就返回即可
接着我们通过代码来实现该过程,首先来看HeroNode的代码实现:
//中序遍历查找
public HeroNode queryMidOrder(int no){
//定义一个临时存储的变量
HeroNode heroResult = null;
//先判断左子节点是否为null,如果不为null我们递归中序遍历
if (this.left !=null){
heroResult = this.left.queryMidOrder(no);
if (heroResult !=null){ //表示已经找到
return heroResult;
}
}
//2.跟当前节点(root节点)进行比较,如果是直接返回
if (this.no == no){
return this;
}
//3.右边节点找,先判断右子节点是否为null,如果不为null我们递归中序遍历
if (this.right !=null){
heroResult = this.right.queryMidOrder(no);
}
return heroResult;
}
上述代码就是HeroNode的前序遍历查找的具体代码实现过程,接着我们来看二叉树中是如何来调这个前序遍历的代码的,具体代码如下:
//中序遍历
public HeroNode queryMidOrder(int no){
if (root !=null){
return root.queryMidOrder(no);
}else {
return null;
}
}
接着我们来看测试代码,具体代码如下:
System.out.println("中遍历查找测试:");
HeroNode heroNode = binaryTree.queryMidOrder(5);
if (heroNode !=null){
System.out.printf("找到了,信息为 no=%d name= %s\t\n",heroNode.getNo(),heroNode.getName());
}else {
System.out.printf("没有找到,信息为 no=%d的英雄",5);
}
测试结果如下图所示:
中序遍历测试结果图.png
上述就是中序查找的过程,我们最后来看后序遍历查找的具体过程
- 后序遍历查找的思路分析:
1.首先需要我们判断当前节点的左子节点是否为null,不为null则递归后序遍历去找,如果找到了就返回即可
2.我们需要首先 判断右子节点是否为null,如果不为null则递归后序遍历去找,如果找到了就返回即可
3.如果右子节点没有找到,则跟当前节点的编号(no)跟我们要查找的是否是同一个,如果是直接返回即可,没有的话返回null即可.
接着我们通过代码来实现该过程,首先来看HeroNode的代码实现:
//后序遍历查找
public HeroNode queryPostOrder(int no){
//定义一个临时存储的变量
HeroNode heroResult = null;
//先判断左子节点是否为null,如果不为null我们递归后序遍历查找
if (this.left !=null){
heroResult = this.left.queryPostOrder(no);
if (heroResult !=null){
return heroResult;
}
}
//2.右边节点找,先判断右子节点是否为null,如果不为null我们递归后序遍历查找
if (this.right !=null){
heroResult = this.right.queryPostOrder(no);
if (heroResult !=null){
return heroResult;
}else {
return null;
}
}
//跟当前节点(root节点)进行比较,如果是直接返回
if (this.no == no){
return this;
}
//都没找到返回null
return null;
}
上述代码就是HeroNode的前序遍历查找的具体代码实现过程,接着我们来看二叉树中是如何来调这个前序遍历的代码的,具体代码如下:
//后序遍历
public HeroNode queryPostOrder(int no){
if (root !=null){
return root.queryPostOrder(no);
}else {
return null;
}
}
接着我们来看测试代码,具体代码如下:
System.out.println("后序遍历查找测试:");
HeroNode heroNode = binaryTree.queryPostOrder(5);
if (heroNode !=null){
System.out.printf("找到了,信息为 no=%d name= %s\t\n",heroNode.getNo(),heroNode.getName());
}else {
System.out.printf("没有找到,信息为 no=%d的英雄",5);
}
来看测试结果如图所示:
后续遍历查找测试结果图.png
那么关于二叉树的遍历查找的学习就到这里了,下节我们来学习二叉树的删除操作
网友评论