前序中序后序遍历查找

首页 » 算法 » 前序中序后序遍历查找

遍历

  • 前序遍历:先输出父节点,再遍历左子树和右子树
  • 中序遍历:先遍历左子树,再输出父节点,再遍历右子树
  • 后序遍历:先遍历左子树,再遍历右子树,再输出父节点

查找

前序查找思路
* 先判断当前节点的no是否等于要查找的值
* 如果相等,则返回当前节点
* 如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归前序查找


中序查找思路
* 判断当前节点的左子节点是否为空,如果不为空,则递归中序查找
* 如果找到,则返回,如果没找到,就和当前节点比较,如果是则返回当前节点,否则继续右递归中序查找
* 如果右递归中序查找,找到就返回,否则返回null


后序查找思路
* 判断当前节点的左子节点是否为空,如果不为空,则递归后序查找
* 如果找到,就返回,如果没找到,就判断当前节点是否为空,如果不为空,则右递归进行后序查找,如果找到,就返回
* 就和当前节点进行比较,如果是就返回,否则返回null

public class 树 {
public static void main(String[] args) {
 Tree tree = new Tree();
 HeroNode root=new HeroNode(1,"a");
 HeroNode node2=new HeroNode(2,"b");
 HeroNode node3=new HeroNode(3,"c");
 HeroNode node4=new HeroNode(4,"d");
 root.setLeft(node2);
 root.setRight(node3);
 node3.setRight(node4);
 tree.setRoot(root);
 System.out.println("前序");
 tree.qianxu();
 System.out.println("中序");
 tree.zhongxu();
 System.out.println("后序");
 tree.houxu();
 System.out.println("查找3");
 System.out.println(tree.qiancha(4));
}
}
class Tree{
 private HeroNode root;
 public void setRoot(HeroNode root) {
  this.root=root;
 }
 //前序遍历
 public void qianxu() {
  if(this.root != null) {
   this.root.qianxu();
  }else {
   System.out.println("空");
  }
 }
 //后序遍历
 public void houxu() {
  if(this.root != null) {
   this.root.houxu();
  }else {
   System.out.println("空");
  }
 }
 //中序遍历
 public void zhongxu() {
  if(this.root != null) {
   this.root.zhongxu();
  }else {
   System.out.println("空");
  }
 }
 //前序查找
 public HeroNode qiancha(int no) {
  if(root != null)
   return root.qiancha(no);
  else
   return null;
 }
 //后序查找
 public HeroNode houcha(int no) {
  if(root != null)
   return root.houcha(no);
  else
   return null;
 }
//删除节点
	public void del(int no) {
		if(root != null) {
			//如果只有一个root节点,就判断呢root是不是要删除的节点
			if(root.getNo() == no) {
				root=null;
			}else {
				root.del(no);
			}
		}else {
			System.out.println("空树");
		}
	}
}
//节点
class HeroNode{
 private int no;
 private String name;
 private HeroNode left;
 private HeroNode right;
 public HeroNode(int no,String name) {
  this.name=name;
  this.no=no;
 }
 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 del(int no) {
		//如果当前节点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left=null
		if(this.left != null && this.left.no == no) {
			this.left=null;
			return;
		}
		//如果当前节点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right=null
		if(this.right !=null && this.right.no==no) {
			this.right=null;
			return;
		}
		//然后就进行左子树递归删除
		if(this.left != null) {
			this.left.del(no);
		}
		if(this.right != null) {
			this.right.del(no);
		}
	}
 //前序
 public void qianxu() {
  System.out.println(this);//父节点
  if(this.left != null) {
   this.left.qianxu();
  }
  if(this.right != null) {
   this.right.qianxu();
  }
 }
 //中序
 public void zhongxu() {
  if(this.left != null) {
   this.left.zhongxu();
  }
  System.out.println(this);
  if(this.right != null) {
   this.right.zhongxu();
  }
 }
 //后序
 public void houxu() {
  if(this.left != null) {
   this.left.zhongxu();
  }
  if(this.right != null) {
   this.right.zhongxu();
  }
  System.out.println(this);
 }
 //前序查找
 public HeroNode qiancha(int no) {
/*
 * 前序查找思路
 * 先判断当前节点的no是否等于要查找的值
 * 如果相等,则返回当前节点
 * 如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归前序查找
*/
  if(this.no == no) {
   return this;
  }
  //判断当前节点的左子节点是否为空,如果不为空,则递归前序查找
  //如果左递归前序找到节点,则返回
  HeroNode resnode=null;
  if(this.left != null) {
   resnode=this.left.qiancha(no);
  }
  if(resnode != null) {
   //左子树找到
   return resnode;
  }
  if(this.right != null) {
   resnode=this.right.qiancha(no);
  }
  return resnode;
 }
 //中序chazhao
 /*
  * 中序查找思路
  * 判断当前节点的左子节点是否为空,如果不为空,则递归中序查找
  * 如果找到,则返回,如果没找到,就和当前节点比较,如果是则返回当前节点,否则继续右递归中序查找
  * 如果右递归中序查找,找到就返回,否则返回null
  */
 public HeroNode zhongcha(int no) {
  HeroNode resnode=null;
  //判断当前节点的左子节点是否为空,如果不为空,则递归中序查找
  if(this.left != null) {
   resnode=this.left.zhongcha(no);
  }
  if(resnode != null) {
   return resnode;//找到
  }
  if(this.no ==no) {
   return this;
  }
  if(this.right != null) {
   resnode=this.right.zhongcha(no);
  }
  return resnode;
 }
 /*
  * 后序查找思路
  * 判断当前节点的左子节点是否为空,如果不为空,则递归后序查找
  * 如果找到,就返回,如果没找到,就判断当前节点是否为空,如果不为空,则右递归进行后序查找,如果找到,就返回
  * 就和当前节点进行比较,如果是就返回,否则返回null
  */
 public HeroNode houcha(int no) {
  HeroNode resnode=null;
  if(this.left != null) {
   resnode=this.left.houcha(no);
  }
  if(resnode != null) {
   return resnode;//找到
  }
  if(this.right != null) {
   resnode=this.right.houcha(no);
  }
  if(resnode != null) {
   return resnode;//找到
  }
  if(this.no ==no) {
   return this;
  }
  return resnode;
 }
}
分享到:
赞(0) 打赏

评论 5

评论前必须登录!

 

  1. #1

    可以

    奋斗6个月前 (03-27)
  2. #2

    白云6个月前 (03-28)
  3. #3

    我也是小白以后多多交流

    沥青6个月前 (03-28)
  4. #4

    挺明白的

    我是你哥6个月前 (03-28)
  5. #5

    给你点赞

    笨鸟先飞6个月前 (03-29)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00