李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--二叉树查找指定节点
Leefs
2020-02-10 PM
1696℃
0条
# 数据结构和算法学习--二叉树查找指定节点 **要求:** (1)请编写前序查找,中序查找和后序查找的方法。 (2)并分别使用三种查找方式,查找heroNO=5的节点 (3)并分析各种查找方式,分别比较了多少次 (4)思路分析图解 ![29.二叉树查找指定节点01.png][1] **使用前序,中序,后序的方式来查找指定的结点** > **前序查找思路** > > 1. 1.先判断当前结点的no是否等于要查找的 > 2. 2.如果是相等,则返回当前结点 > 3. 3.如果不等,则判断当前结点的左子节点是否为空,如果不为空,则递归前序查找 > 4. 4.如果左递归前序查找,找到结点,则返回,否则继续判断,当前的结点的右子节点是否为空,如果不空,则继续向右递归前序查找。 > > **中序查找思路** > > 1. 1.判断当前结点的左子结点是否为空,如果不为空,则递归中序查找 > 2. 2.如果找到,则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点,否则继续进行右递归的中序查找 > 3. 3.如果右递归中序查找,找到就返回,否则返回null > > **后序查找思路** > > 1. 1.判断当前结点的左子节点是否为空,如果不为空,则递归后序查找 > 2. 2.如果找到,就返回,如果没有找到,就判断当前结点的右子节点是否为空,如果不为空,则右递归进行后序查找,如果找到,就返回 > 3. 3.和当前节点进行比较,如果是则返回,否则返回null **代码实现** ```java public class BinaryTreeDemo { 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,"关胜"); //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); binaryTree.setRoot(root); //测试 System.out.println("前序遍历"); binaryTree.preOrder(); System.out.println("中序遍历"); binaryTree.infixOrder(); System.out.println("后序遍历"); binaryTree.postOrder(); /*System.out.println("前序遍历方式"); HeroNode resNode = binaryTree.preOrderSearch(5); if(resNode != null){ System.out.printf("找到了,信息为no=%d name=%s",resNode.getNo(),resNode.getName()); }else{ System.out.printf("没有找到no=%d的英雄",5); }*/ //中序遍历查找 //中序遍历3次 System.out.println("中序遍历方式~~~"); HeroNode resNode2 = binaryTree.infixOrderSearch(5); if(resNode2 !=null){ System.out.printf("找到了,信息为no=%d name=%s",resNode2.getNo(),resNode2.getName()); }else{ System.out.printf("没有找到no=%d 的英雄",5); } //后序遍历查找 System.out.println("后序遍历方式~~~"); HeroNode resNode = binaryTree.postOrderSearch(5); if(resNode!=null){ System.out.printf("找到了,信息为no=%d name=%s",resNode.getNo(),resNode.getName()); }else{ System.out.printf("没有找到no=%d的英雄",5); } } } class BinaryTree{ private HeroNode root; public void setRoot(HeroNode root){ this.root=root; } //前序遍历 public void preOrder(){ if(this.root != null){ this.root.preOrder(); }else{ System.out.println("二叉树为空,无法遍历"); } } //中序遍历 public void infixOrder(){ if(this.root != null){ this.root.infixOrder(); }else{ System.out.println("二叉树为空,无法遍历"); } } //后序遍历 public void postOrder(){ if(this.root != null){ this.root.postOrder(); }else{ System.out.println("二叉树为空,无法遍历"); } } //前序遍历 public HeroNode preOrderSearch(int no){ if(root != null){ return root.preOrderSearch(no); }else{ return null; } } //中序遍历 public HeroNode infixOrderSearch(int no){ if(root != null){ return root.infixOrderSearch(no); }else{ return null; } } //后序遍历 public HeroNode postOrderSearch(int no){ if(root != null){ return this.root.postOrderSearch(no); }else{ return null; } } } //先创建HeroNode结点 class HeroNode{ private int no; private String name; private HeroNode left;//默认null private HeroNode right;//默认null public HeroNode(int no,String name){ this.no=no; this.name=name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } //编写前序遍历的方法 public void preOrder(){ System.out.println(this);//先输出父节点 //递归向左子树前序遍历 if(this.left!=null){ this.left.preOrder(); } //递归向右子树前序遍历 if(this.right != null){ this.right.preOrder(); } } //中序遍历 public void infixOrder(){ //递归向左子树中序遍历 if(this.left != null){ this.left.infixOrder(); } //输出父结点 System.out.println(this); //递归向右子树中序遍历 if(this.right != null){ this.right.infixOrder(); } } //后序遍历 public void postOrder(){ if(this.left != null){ this.left.postOrder(); } if(this.right != null){ this.right.postOrder(); } System.out.println(this); } //前序遍历查找 public HeroNode preOrderSearch(int no){ System.out.println("进入前序遍历"); //比较当前结点是否满足条件 if(this.no==no){ return this; } //1.判断当前结点的左子结点是否为空,如果不为空,则递归前序查找 //2.如果左递归前序查找,找到节点,则返回 HeroNode resNode=null; if(this.left!=null){ resNode = this.left.preOrderSearch(no); } if(resNode != null){//说明在左子树找到 return resNode; } //1.左递归前序查找,找到节点,则返回,否则继续判断 //2. 当前的结点的右子节点是否为空,如果不为空,则继续向右递归前序查找 if(this.right != null){ resNode = this.right.preOrderSearch(no); } return resNode; } //中序遍历查找 public HeroNode infixOrderSearch(int no){ //判断当前结点的左子节点是否为空,如果不为空,则递归中序查找 HeroNode resNode=null; if(this.left != null){ resNode=this.left.infixOrderSearch(no); } if(resNode != null){ return resNode; } System.out.println("进入中序查找"); //如果找到,则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点 if(this.no == no){ return this; } //否则继续进行右递归的中序查找 if(this.right!=null){ resNode = this.right.infixOrderSearch(no); } return resNode; } //后序遍历查找 public HeroNode postOrderSearch(int no){ //判断当结点的左子结点是否为空,如果不为空,则递归后序查找 HeroNode resNode = null; if(this.left != null){ resNode = this.left.postOrderSearch(no); } if(resNode != null){//说明在左子树找到 return resNode; } //如果左子树没有找到,则向右子树递归进行后序遍历查找 if(resNode.right != null){ resNode = this.right.postOrderSearch(no); } if(resNode != null){ return resNode; } System.out.println("进入后序查找"); //如果左右子树都没有找到,就比较当前结点是不是 if(this.no == no){ return this; } return resNode; } } ``` [1]: https://lilinchao.com/usr/uploads/2020/02/2195389575.png
标签:
数据结构和算法
,
二叉树
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/580.html
上一篇
数据结构和算法学习--二叉树删除节点
下一篇
数据结构和算法学习--顺序存储二叉树
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
DataWarehouse
Kafka
Scala
并发编程
散列
JavaWEB项目搭建
Spark RDD
SpringBoot
国产数据库改造
队列
栈
人工智能
GET和POST
Eclipse
Azkaban
排序
Spark Streaming
JavaSE
Hbase
HDFS
持有对象
Docker
Java工具类
Flume
线程池
Hive
数据结构和算法
Spark Core
数学
稀疏数组
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞