二叉搜索树Java实现
2021/11/19 20:12:43
本文主要是介绍二叉搜索树Java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.二叉搜索树(Binary Search Tree):
(又:二叉查找树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
2.建二叉树
static class TreeNode { public int val;//值 public TreeNode left;//左边 public TreeNode right;//右边 public TreeNode(int val) {//构造方法,用于赋值 this.val = val; } }
3.搜索操作
//搜索操作 public TreeNode search(int key) {//查找key TreeNode cur = root; while(cur != null) { if(cur.val == key) { return cur; } else if(cur.val < key) { cur = cur.right; }else { cur = cur.left; } } return null; }
4.插入操作
//插入操作 public void insertTree(int val) { //如果二叉搜索树为空,直接插入值 if(root == null) { root = new TreeNode(val); return; } TreeNode cur = root; TreeNode parent = null; while(cur != null) { if(cur.val < val) { parent = cur; cur = cur.right; } else { parent = cur; cur = cur.left; } } TreeNode node = new TreeNode(val); if(parent.val < val) { parent.right = node; } else { parent.left = node; } }
5.删除操作
5.1:cur.lelf == null 左子树为空
cur 是root,则root = cur.right
cur不是root,cur是parent.left,则parent.left=cur.right
cur不是root,cur是parent.right,则parent.right=cur.right
5.2:cur.right == null 右子树为空
右子树为空与左子树为空大致相同,可以自行推理。
5.3:cur.lelf != null&&cur.right != null 左右子树都不为空
思路:
- 左树找最大数据
- 右树找最小数据
这里演示右树找最小数据
top1:找的树在左边
**top2:**找的树在右边
//删除操作 public void remove(int key) { TreeNode cur = root; TreeNode parent = null;//查找相应结点然后删除 while(cur != null) { if(cur.val == key) { removeNode(parent,cur);//删除函数 return ; } else if(cur.val < key) { parent = cur; cur = cur.right; } else { parent = cur; cur = cur.left; } } } //通过removeNode函数进行删除 public void removeNode(TreeNode parent,TreeNode cur) { if(cur.left == null) {//左子树为空 if(cur == root) { root = cur.right; } else if(cur == parent.left) { parent.left = cur.right; } else { parent.right = cur.right; } } else if(cur.right == null) { if(cur == root) {//右子树为空 root = cur.left; } else if(cur == parent.left) { parent.left = cur.left; } else { parent.right = parent.left; } } else {//替罪羊的删除*//左边找最大,右边找最小 TreeNode targetparent = cur; TreeNode target = cur.right; while(target.left != null) { targetparent = target; target = target.left; } cur.val = target.val; if(targetparent.left == target) { targetparent.left = target.right; } else { targetparent.right = target.right; } } }
二叉搜索树测试及完整代码:
https://gitee.com/btyyt/growing-xbt/commit/d2976f8036a9ef757cb9f00e3f42ac460096d90a
这篇关于二叉搜索树Java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 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课程入门指南