免费做网站怎么做网站吗2,阿里云这么建设网站,网络工程师证书有哪些,青岛 网站制作1.搜索树 前面我们已经使用C语言学习完了二叉树#xff0c;懂得了一些二叉树的基本性质已经实现方法 https://mp.csdn.net/mp_blog/creation/editor/139572374#xff0c;本文我们来一起进行二叉树的衍生-二叉搜索树
1.1 概念 二叉搜索树又称二叉排序树#xff0c;它或者是…1.搜索树 前面我们已经使用C语言学习完了二叉树懂得了一些二叉树的基本性质已经实现方法 https://mp.csdn.net/mp_blog/creation/editor/139572374本文我们来一起进行二叉树的衍生-二叉搜索树
1.1 概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
简单来说就是给二叉树定义为左右节点左子树比根节点小右子树比根节点大 1.2简单实现二叉搜索树的增加和删除
1.2.1创建二叉搜索树 1.首先在搜索树内定义一个静态类来表示初始二叉树 定义出右指针左指针根节点其他的交给二叉树的增加即可 static class TreeNode{//在类中使用一个整体类来表示二叉树要用静态类int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val val;}}public TreeNode root;//定义根节点
2.判断输入值是否存在搜索树中
将输入的值和根节点比较大于就将根节点向右移小于就将根节点的值向左移直到找到为止找不到就返回false. public boolean search(int val){//创建二叉搜索树TreeNode cur root;while(cur !null){if(cur.val val){cur cur.left;}else if(cur.valval){cur cur.right;}else {return true;}}return false;} 1.2.2向二叉搜索树内添加元素
首先进行判空将要赋值的数放在二叉树类里
1.判断要添加的值要放在哪和判断是否存在一个道理但是需要找到根节点的上一个指针方便插入。
比方说我们要在这么个搜索二叉树内插入4 1. 4比5小所以往左走
2. 4比3大所以往右走发现cur为空则停止 3. 将parent.right 赋值为4 public void insert(int val){//二叉搜索树的添加TreeNode noot new TreeNode(val);if(root null){root noot;//若为空添加进来的元素则为根节点return;}TreeNode parent null;//负责记录cur的上一个指针TreeNode cur root;while(cur!null){//若cur为零则说明parent的左指针或者右指针已经为插入位置if(valcur.val){parent cur;cur cur.right;}else if(valcur.val){parent cur;cur cur.left;}else{return;//如果找到就没必要添加了}}if(valparent.val){parent.rightnoot;//此时cur是叶子节点所以需要有parent这个变量}else {parent.left noot;}} 1.2.3删除搜索树内的元素难点
思路首先得先找到删除节点的位置 然后我们将删除分为三种情况
1.删除的元素的左子树 null
1.1 cur root
当需要删除的元素在根节点时直接将根节点右子树改为根节点即可
root cur.right;
1.2 cur parent.right parent.right cur.right 由图可得
1.3cur parent.left
parent.left cur.right
2.删除的元素的右子树 null(和上面一样)
1.1 cur root
1.2 cur parent.right
1.3cur parent.left
3.删除的元素左子树 null 右子树 null难点
这时我们可以采用替换法找到搜索树中同样适合放在删除位置的元素进行交换
这时 我们可以把左子树的最大值找到也可以将右子树的最小值找到 此时我们在删除的时候可能会面对以下情况
我们发现cur 10的情况可以和9,15进行交换此时我们任选一个即可 接下来我就统一使用找右子树最小值来写找右子树的最小值一定是根节点的左子树所以我们需要找target.left null的位置此时target为cur右子树的最小值
其中target负责找到最小值的位置targetParent负责给target擦屁股连接target的右子树
首先将target定义为cur.right,targetParent cur 然后遍历搜索树找到替换节点 然后将target位置的值给到cur targetParent.left指向target.right 记得考虑特殊情况
target一开始就没有left 所以找到替换位置后需要判断target和targetParent的位置关系
当 target在targetParent右边时需要特殊处理
删除总代码实现 public void remove(int key) {TreeNode cur root;TreeNode parent null;while (cur ! null) {if(cur.val key) {parent cur;cur cur.right;}else if(cur.val key) {parent cur;cur cur.left;}else {removeNode(cur,parent);//找到需要删除的位置return;}}}public void removeNode(TreeNode cur,TreeNode parent){if(cur.left null){if(cur root){//当根节点为删除点时root cur.right;}else if(cur parent.left){//当cur是parent的左节点parent.left cur.right;}else{//当cur是parent的右节点parent.right cur.right;}}else if(cur.right null){if(cur root) {//当根节点为删除点时root cur.left;}else if(parent.left cur){//当cur是parent的右节点parent.left cur.left;}else {//当cur是parent的左节点parent.right cur.left;}}else{TreeNode target cur.right,targetparent cur;//targetParent是为了方便替换后直接连接下一个节点while(target.left!null){targetparent target;target target.left;}cur.val target.val;//将替换值赋值给需要删除位置的值if(targetparent.right target) {//对一开始就没有left的target进行特殊处理targetparent.right target.right;}else {targetparent.left target.right;}}
1.3性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
最好情况最优情况下二叉搜索树为完全二叉树其平均比较次数为log2 **n
最坏情况单分支二叉树其平均比较次数为n/2
