利用三种遍历来查找具体的值
思路和代码实现
利用前序遍历查找思路
- 先确定当前节点是否是要查找的target
- 如果是，则返回当前节点
- 如果不是，则判断当前节点的左子节点是否为空，如果不为空则递归前序遍历查找
- 如果左递归前序查找找到目标节点则返回，如果左递归没有找到，则判断右子节点是否为空，如果不为空，则继续向右遍历查找，最后返回结果。
//前序查找;根节点-左子树-右子树
public NodeNN preOrderSearch(int no){
System.out.println("前序遍历的次数");
//先遍历根节点
if(this.no==no){
return this;
}
NodeNN result=null;
//如果左遍历不为空，则需要进行递归遍历
if (this.left!=null){
result=this.left.preOrderSearch(no);
}
//如何结果不为零说明左节点找着了，直接返回即可
if(result!=null){
return result;
}
//走到此处，说明左边查找的结果为null，即要开始右边进行查找
if(this.right!=null){
result=this.right.preOrderSearch(no);
}
//不管找没找到都要返回，此时result可能为null
return result;
}
利用中序遍历查找思路
- 先判断左子节点是否为空，如果不为空则递归中序查找，
- 如果找到则返回，如果没有找到则和按当前节点比较，如果是目标，则返回当前的节点，如果不是，则继续进行右递归的中序查找
- 如果右递归中序查找找到了则返回，否则返回null
//中序查找：左-根节点-右
//中序查找
public NodeNN inOrderSearch(int no){
NodeNN result=null;
//先找递归查找左边节点，
if(this.left!=null){
result=this.left.inOrderSearch(no);
}
//如果左子树遍历结束以后，结果不为空，说明找到了，直接返回即可
if(result!=null){
return result;
}
System.out.println("中序遍历的次数");
//左子树查找之后如果仍然为空，则找根节点
if(this.no==no){
return this;
}
//走到此处，说明根节点不是目标节点，则开始递归找右子树
if(this.right!=null){
result=this.right.inOrderSearch(no);
}
return result;
}
利用后序遍历查找思路
- 先判断左子节是否为空，如果不为空则左边进行递归后序遍历查找
- 左边没有，则判断右边节点是否为空，如果不为空，则对右边进行遍历查找
- 右边如果没有找到则判断当前节点是否是目标节点
//后序查找
public NodeNN postOrderSearch(int no){
NodeNN result=null;
//先判断左子树是否为空
if(this.left!=null){
result=this.left.postOrderSearch(no);
}
//返回左子树查找之后二点值，如果左子树查到了，即不为空，可以直接退出递归将结果返回
if(result!=null){
return result;
}
//走到此处说明左子树没有找到，判断右子树是否为空，如果不为空则递归查找
if(this.right!=null){
result=this.right.postOrderSearch(no);
}
//若找到结果，将结果直接返回
if(result!=null){
return result;
}
System.out.println("后序遍历的次数");
//最后判断根节点是否为目标节点
if(this.no==no){
return this;
}
return result;
}
测试代码
package com.njupt.binaryTree;
/**
* Creat with IntelliJ IDEA
*
* @Auther:倔强的加瓦
* @Date:2021/07/22/20:18
* @Description:
*/
public class Search {
public static void main(String[] args) {
Binary binary = new Binary();
NodeNN node1=new NodeNN(1,"吴吴");
NodeNN node2=new NodeNN(2,"亦亦");
NodeNN node3=new NodeNN(3,"凡凡");
NodeNN node4=new NodeNN(4,"签签");
NodeNN node5=new NodeNN(5,"word");
NodeNN node6=new NodeNN(6,"very big");
node1.left=node2;
node1.right=node4;
node2.left=node3;
node4.left=node5;
node4.right=node6;
//给根节点赋值
binary.root=node1;
System.out.println("前序遍历：");
System.out.println(binary.pre(3));
System.out.println("中序遍历：");
System.out.println(binary.in(3));
System.out.println("后序遍历：");
System.out.println(binary.post(3));
}
}
//创建二叉树，来管理每一个节点
class Binary{
public NodeNN root;
//前序遍历查找
public NodeNN pre(int no){
if(root!=null){
return root.preOrderSearch(no);
}else{
return null;
}
}
//中序遍历查找
public NodeNN in(int no){
if(root!=null){
return root.inOrderSearch(no);
}else{
return null;
}
}
//后序遍历查找
public NodeNN post(int no){
if(root!=null){
return root.postOrderSearch(no);
}else{
return null;
}
}
}
class NodeNN{
public int no;
public String name;
public NodeNN left;
public NodeNN right;
public NodeNN(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "Node1{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
//前序查找
public NodeNN preOrderSearch(int no){
System.out.println("前序遍历的次数");
if(this.no==no){
return this;
}
NodeNN result=null;
//如果左遍历不为空，则需要进行递归遍历
if (this.left!=null){
result=this.left.preOrderSearch(no);
}
//如何结果不为零说明左节点找着了，直接返回即可
if(result!=null){
return result;
}
//走到此处，说明左边查找的结果为null，即要开始右边进行查找
if(this.right!=null){
result=this.right.preOrderSearch(no);
}
return result;
}
//中序查找
public NodeNN inOrderSearch(int no){
NodeNN result=null;
//先找左边节点
if(this.left!=null){
result=this.left.inOrderSearch(no);
}
if(result!=null){
return result;
}
System.out.println("中序遍历的次数");
if(this.no==no){
return this;
}
if(this.right!=null){
result=this.right.inOrderSearch(no);
}
return result;
}
//后序查找
public NodeNN postOrderSearch(int no){
NodeNN result=null;
if(this.left!=null){
result=this.left.postOrderSearch(no);
}
if(result!=null){
return result;
}
if(this.right!=null){
result=this.right.postOrderSearch(no);
}
if(result!=null){
return result;
}
System.out.println("后序遍历的次数");
if(this.no==no){
return this;
}
return result;
}
}
结果：
前序遍历：
前序遍历的次数
前序遍历的次数
前序遍历的次数
Node1{no=3, name='凡凡'}
中序遍历：
中序遍历的次数
Node1{no=3, name='凡凡'}
后序遍历：
后序遍历的次数
Node1{no=3, name='凡凡'}
Process finished with exit code 0