java二叉树的查找(2)
2021/12/8 20:17:05
本文主要是介绍java二叉树的查找(2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一. 递归方式
1. 前序查找
- 先判断当前节点是否要查找的节点
- 当前节点有左子树,向左递归,如果找到不为空的节点,说明查找成功
- 否则向右递归,当前节点有右子树,向右递归,如果找到不为空的节点,说明查找成功
- 否则返回null
public HeroNode preOrderSearch(int i) { System.out.println("进入前序查找"); //比较当前结点是不是 if (this.id == i) return this; //1.则判断当前结点的左子节点是否为空,如果不为空,则递归前序查找 //2.如果左递归前序查找,找到结点,则返回 HeroNode node = null; if (this.left != null) { node = this.left.preOrderSearch(i); } if (node != null) return node; //2.当前的结点的右子节点是否为空,如果不空,则继续向右递归前序查找 if (this.right != null) { node = this.right.preOrderSearch(i); } return node; }
2. 中序查找
- 当前节点有左子树,向左递归,如果找到不为空的节点,说明查找成功
- 否则判断当前节点是否要查找的节点,如果是返回
- 否则向右递归,当前节点有右子树,向右递归,如果找到不为空的节点,说明查找成功
- 否则返回null
public HeroNode infixOrderSearch(int i) { HeroNode node = null; if (this.left != null) { node = this.left.infixOrderSearch(i); } System.out.println("进入中序查找"); if (node != null) return node; //比较当前结点是不是 if (this.id == i) return this; if (this.right != null) { node = this.right.infixOrderSearch(i); } return node; }
3. 后序查找
- 当前节点有左子树,向左递归,如果找到不为空的节点,说明查找成功
- 否则向右递归,当前节点有右子树,向右递归,如果找到不为空的节点,说明查找成功
- 否则判断当前节点是否要查找的节点,如果是返回
- 否则返回null
public HeroNode postOrderSearch(int i) { HeroNode node = null; if (this.left != null) { node = this.left.postOrderSearch(i); } if (node != null) return node; if (this.right != null) { node = this.right.postOrderSearch(i); } if (node != null) return node; System.out.println("进入后序查找"); if (this.id == i) return this; return node; }
二、非递归方式查找
1.前序查找
- 用一个栈储存当前节点
- 若栈不为空,弹出栈中一个节点,判断当前节点是否要查找的节点,如果是返回
- 否则若当前节点有右子树,右子树入栈
- 若当前节点有左子树,左子树入栈
- 栈为空,结束循环
- 否则返回null
public HeroNode preOrderSearch1(int i) { System.out.println("前序非递归查找~~"); Stack<HeroNode> stack = new Stack<>(); stack.push(this); while (!stack.isEmpty()) { HeroNode node = stack.pop(); if (node.id == i) return node; if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return null; }
2.中序查找
- 用一个临时变量代替当前节点,创建一个栈
- 若栈不为空或者当前节点不为空
- 若当前节点不为空,则循环至最左节点
- 若当前节点为空,栈弹出一个节点,判断当前节点是否为查找的节点,如果是返回
- 如果不是,若该节点有右节点,令节点等于右节点
- 否则返回null
public HeroNode infixOrderSearch1(int i) { System.out.println("中序非递归查找~~"); Stack<HeroNode> stack = new Stack<>(); HeroNode node = this; while (!stack.isEmpty() || node != null) { if (node != null) { stack.push(node); node = node.left; } else { node = stack.pop(); if (node.id == i) return node; node = node.right; } } return null; }
3.后续查找
- 用一个临时变量代替当前节点,创建两个栈s1,s2,
- 当前节点入栈S1
- 若栈s1不为空,则弹出一个节点
- 将当前节点入栈s2
- 如果当前节点有左节点,则入栈s1
- 如果当前节点有右节点,则入栈s1
- 若栈s2不为空,依次弹出元素判断是否为查找值,否则返回null
public HeroNode postOrderSearch1(int i) { System.out.println("后序非递归查找~~"); Stack<HeroNode> s1 = new Stack<>(); Stack<HeroNode> s2 = new Stack<>(); HeroNode node = this; s1.push(node); while (!s1.isEmpty()){ node=s1.pop(); s2.push(node); if(node.left!=null){ s1.push(node.left); } if(node.right!=null){ s1.push(node.right); } } while (!s2.isEmpty()){ node=s2.pop(); if(node.id==i) return node; } return null; }
- 用一个临时变量代替当前节点,lastnode代表最右节点;创建1个栈s1
- 若当前节点不为空,则循环至最左节点入栈s1
- 若栈s1不为空,则弹出一个节点
- 若当前节点有有右节点,且右节点没有被访问过,则当前节点变为右节点,循环至右节点的最左节点
- 否则判断当前是否为查找值,将当前节点的值赋给lastnode,标记已访问
- 否则返回null
public HeroNode postOrderSearch2(int i) { System.out.println("后序非递归查找~~"); Stack<HeroNode> s1 = new Stack<>(); HeroNode node = this; HeroNode lasrnode = null; while (node!=null){ s1.push(node); node=node.left; } while (!s1.isEmpty()){ node=s1.pop(); if(node.right!=null&& node.right!=lasrnode){ s1.push(node); node=node.right; while (node!=null){ s1.push(node); node=node.left; } }else { if(node.id==i) return node; lasrnode=node; } } return null; } }
三、二叉树删除节点
- 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
- 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
- 如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
- 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
- 如果第4步也没有删除结点,则应当向右子树进行递归删除.
public void delNode(int i) { if(root==null) return; if(root.id==i) root=null; else root.delNode(i); } public void delNode(int i) { if(this.left!=null&&this.left.id==i){ this.left=null; return; } if(this.right!=null&&this.right.id==i){ this.right=null; return; } if(this.left!=null) this.left.delNode(i); if(this.right!=null) this.right.delNode(i); }
- 找到该值,如果该节点为叶子节点或者该节点只有左节点,返回该节点的左子树
- 如果用该节点的右节点的最左节点与该节点进行值交换
- 递归得到总树
public HeroNode delNode1(HeroNode root,int i) { if (root == null) return root; if (root.id == i) { if (root.right == null) { // 这里第二次操作目标值:最终删除的作用 return root.left; } HeroNode cur = root.right; while (cur.left!=null) { cur = cur.left; } HeroNode node = new HeroNode(root.id, root.name); root.id=cur.id; root.name=cur.name; cur.id=node.id; cur.name=node.name;// 这里第一次操作目标值:交换目标值其右子树最左面节点。仅仅是值替换,引用没有交换 } root.left = delNode1(root.left, i); root.right = delNode1(root.right, i); return root; }
这篇关于java二叉树的查找(2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南