二叉搜索树 心已赠人 2023-09-28 09:18 71阅读 0赞 ## 1 二叉搜索树 ## 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点;右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质,当我们对二叉搜索树进行中序遍历时,就可以得到有序的序列。 ### 1.1 基本操作 ### ##### 新增 ##### 根据二叉搜索树的性质,当需要新增元素时,我们只需要判断这个元素是大于根节点还是小于根节点。如果是大于,则在右子树中继续寻找;如果是小于,则在左子树中继续寻找,直到找到适合自己的空位。 代码如下: /** * 新增 * @param data */ public void add(int data){ // 用于判断新增的位置是左孩子还是右孩子 boolean isLeft = true; // 父节点 BSTreeNode parent = null; // 当前节点 BSTreeNode cur = head; while(cur != null){ parent = cur; // 比当前节点大,往右找 if(data > cur.data){ cur = cur.right; isLeft = false; }else if(data < cur.data){ // 比当前节点小,往左找 cur = cur.left; isLeft = true; }else{ // 已存在直接返回 return; } } // 生成节点,便于子类扩展 BSTreeNode newNode = createNode(data); if(isLeft){ parent.left = newNode; }else{ parent.right = newNode; } newNode.parent = parent; // 新增后处理方法,用于子类扩展 afterAdd(newNode); } -------------------- ##### 查找 ##### 查找就比较简单了,跟新增有些类似。从根节点开始,如果当前节点小于新节点,就从右树上继续查找;如果当前节点大于新节点,就从左树上继续查找; 代码如下: /** * 查询 * @param data * @return */ public BSTreeNode search(int data){ BSTreeNode cur = head; while(cur != null){ // 比当前节点大,向右找 if(data > cur.data){ cur = cur.right; }else if(data < cur.data){ // 比当前节点小,向左找 cur = cur.left; }else{ // 找到后返回 return cur; } } // 找不到返回空 return null; } -------------------- ##### 删除 ##### 删除比较复杂,需要分情况讨论: (1)待删除节点没有左、右孩子,直接删除即可。 ![006c8c58f037da6facedc5a056a47802.png][] (2)待删除节点只有左孩子或只有右孩子,让子节点代替自己的位置。 ![43bcbb24c022ba18b346f3277e7e35b9.png][] (3)待删除节点既有左孩子又有右孩子,需要找到待删除节点的左子树的最右节点或右子树的最左节点K,将K从原本的位置转移到待删除节点的位置。 ![90c4ca60f381b2ea8131b9cf9945495c.png][] 前两中情况比较好理解,下面着重解释一下第三种情况。 当我们删除一个节点时,仍然需要保持二叉搜索树的性质,即任何一个节点的左子树上的节点都小于根节点,右子树上的节点都大于根节点。 为了保持这个性质,我们就需要从它的子树中找到一个节点K,K必须比左子树上的节点都要大,比右子树上的节点都要小。然后让K代替自己的位置。 图中满足条件的节点有两个:14和17。 其实我们只需要对整棵树进行中序遍历就可以发现,14和17分别在待删除节点15的左右两侧。 `中序遍历:3 5 7 9 10 12 13 14 15 17` 这样一来,为什么要用这两个节点替代待删除节点也就清晰明了了。 代码如下: /** * 删除 * @param data */ public void delete(int data){ BSTreeNode node = search(data); if(node == null){ return; } // 如果节点没有左子树,让右子树接替自己的位置 if(node.left == null){ if(node.parent.left == node){ node.parent.left = node.right; }else{ node.parent.right = node.right; } }else if(node.right == null){ // 如果节点没有右子树,让左子树接替自己的位置 if(node.parent.left == node){ node.parent.left = node.left; }else{ node.parent.right = node.left; } }else{ // 如果既有左子树又有右子树 // 找到左子树的最右节点,也就是[替代节点] BSTreeNode cur = node.left; while(cur.right != null){ cur = cur.right; } // 用[替代节点]替换待删除节点 node.data = cur.data; // 删除原本的[替代节点] // 如果左子树没有最右节点,即cur不变 if(cur == node.left){ // 直接把[替代节点]的左树接到父节点上 cur.parent.left = cur.left; }else{ // 否则把[替代节点]的左树接到父节点上 cur.parent.right = cur.left; } } } ### 1.2 扩展操作 ### 之所以称之为扩展操作,是因为经典的二叉搜索树并不需要这些操作,但是由经典二叉搜索树衍生出的红黑树、AVL树、SB树等会频繁用到这些操作。 ##### 左旋 ##### 左旋就是让原本的根节点(H)的右孩子(R)作为新的根,此时H会成为R的左孩子,而R原本的左孩子就需要调整位置,成为H的右孩子。 ![1fa54f16869a60c65bb91dd3eb5d621e.png][] 代码如下: /** * 左旋 * @param node */ public void leftRotate(BSTreeNode node){ // 先找到根节点的右孩子 BSTreeNode R = node.right; // 没有右子树无法左旋 if(R == null){ return; } // R的左孩子成为根节点的右孩子 node.right = R.left; if(R.left != null){ R.left.parent = node; } // 根节点成为R的左孩子 R.left = node; R.parent = node.parent; if(node.parent != null){ if(node == node.parent.left){ node.parent.left = R; }else{ node.parent.right = R; } } node.parent = R; // 如果是整棵树的根节点,重新赋值head if(node == head){ head = R; } } ##### 右旋 ##### 与左旋相对,右旋就是让原本的根节点(H)的左孩子(L)作为新的根,此时H会成为L的右孩子,而L原本的右孩子就需要调整位置,成为H的左孩子。 ![852a8e2797648827ba0672a0b7d9e69b.png][] 代码如下: /** * 右旋 * @param node */ public void rightRotate(BSTreeNode node){ // 先找到根节点的左孩子 BSTreeNode L = node.left; // 没有左子树无法右旋 if(L == null){ return; } // L的右孩子成为根节点的左孩子 node.left = L.right; if(L.right != null){ L.right.parent = node; } // 根节点成为L的右孩子 L.right = node; L.parent = node.parent; if(node.parent != null){ if(node == node.parent.left){ node.parent.left = L; }else{ node.parent.right = L; } } node.parent = L; // 如果是整棵树的根节点,重新赋值head if(node == head){ head = L; } } -------------------- ### 1.3 代码实现 ### 下面是完整的代码实现: /** * 二叉搜索树节点类 */ public class BSTreeNode { /** * 左孩子 */ public BSTreeNode left; /** * 右孩子 */ public BSTreeNode right; /** * 父节点 */ public BSTreeNode parent; /** * 数据域 */ public int data; /** * 构造方法 * @param data */ public BSTreeNode(int data){ this.data = data; } } /** * 二叉搜索树 */ public class BSTree { /** * 根节点 */ private BSTreeNode head; public BSTree(int data){ head = createNode(data); } /** * 创建一个节点 * @param data * @return */ protected BSTreeNode createNode(int data){ return new BSTreeNode(data); } /** * 删除 * @param data */ public void delete(int data){ BSTreeNode node = search(data); if(node == null){ return; } // 如果节点没有左子树,让右子树接替自己的位置 if(node.left == null){ if(node.parent.left == node){ node.parent.left = node.right; }else{ node.parent.right = node.right; } }else if(node.right == null){ // 如果节点没有右子树,让左子树接替自己的位置 if(node.parent.left == node){ node.parent.left = node.left; }else{ node.parent.right = node.left; } }else{ // 如果既有左子树又有右子树 // 找到左子树的最右节点,也就是[替代节点] BSTreeNode cur = node.left; while(cur.right != null){ cur = cur.right; } // 用[替代节点]替换待删除节点 node.data = cur.data; // 删除原本的[替代节点] // 如果左子树没有最右节点,即cur不变 if(cur == node.left){ // 直接把[替代节点]的左树接到父节点上 cur.parent.left = cur.left; }else{ // 否则把[替代节点]的左树接到父节点上 cur.parent.right = cur.left; } } } /** * 查询 * @param data * @return */ public BSTreeNode search(int data){ BSTreeNode cur = head; while(cur != null){ // 比当前节点大,向右找 if(data > cur.data){ cur = cur.right; }else if(data < cur.data){ // 比当前节点小,向左找 cur = cur.left; }else{ // 找到后返回 return cur; } } // 找不到返回空 return null; } /** * 新增 * @param data */ public void add(int data){ // 用于判断新增的位置是左孩子还是右孩子 boolean isLeft = true; // 父节点 BSTreeNode parent = null; // 当前节点 BSTreeNode cur = head; while(cur != null){ parent = cur; // 比当前节点大,往右找 if(data > cur.data){ cur = cur.right; isLeft = false; }else if(data < cur.data){ // 比当前节点小,往左找 cur = cur.left; isLeft = true; }else{ // 已存在直接返回 return; } } BSTreeNode newNode = createNode(data); if(isLeft){ parent.left = newNode; }else{ parent.right = newNode; } newNode.parent = parent; afterAdd(newNode); } /** * 新增成功后触发 */ protected void afterAdd(BSTreeNode node){ } /** * 左旋 * @param node */ public void leftRotate(BSTreeNode node){ // 先找到根节点的右孩子 BSTreeNode R = node.right; // 没有右子树无法左旋 if(R == null){ return; } // R的左孩子成为根节点的右孩子 node.right = R.left; if(R.left != null){ R.left.parent = node; } // 根节点成为R的左孩子 R.left = node; R.parent = node.parent; if(node.parent != null){ if(node == node.parent.left){ node.parent.left = R; }else{ node.parent.right = R; } } node.parent = R; // 如果是整棵树的根节点,重新赋值head if(node == head){ head = R; } } /** * 右旋 * @param node */ public void rightRotate(BSTreeNode node){ // 先找到根节点的左孩子 BSTreeNode L = node.left; // 没有左子树无法右旋 if(L == null){ return; } // L的右孩子成为根节点的左孩子 node.left = L.right; if(L.right != null){ L.right.parent = node; } // 根节点成为L的右孩子 L.right = node; L.parent = node.parent; if(node.parent != null){ if(node == node.parent.left){ node.parent.left = L; }else{ node.parent.right = L; } } node.parent = L; // 如果是整棵树的根节点,重新赋值head if(node == head){ head = L; } } /** * 中序遍历 * @return */ @Override public String toString() { StringBuffer buffer = new StringBuffer(); Stack<BSTreeNode> stack = new Stack<>(); BSTreeNode cur = head; while(cur != null || !stack.isEmpty()){ if(cur != null){ stack.push(cur); cur = cur.left; }else{ cur = stack.pop(); buffer.append(cur.data+" "); cur = cur.right; } } return buffer.toString(); } /** * 打印整棵树 */ public void printTree(){ Stack<BSTreeNode> stack = new Stack<>(); BSTreeNode cur = head; stack.push(cur); while(!stack.isEmpty()){ cur = stack.pop(); if(cur.left != null){ System.out.println(cur.data +" -l-> "+cur.left.data); stack.push(cur.left); } if(cur.right != null){ System.out.println(cur.data +" -r-> "+cur.right.data); stack.push(cur.right); } } } } [006c8c58f037da6facedc5a056a47802.png]: https://img-blog.csdnimg.cn/img_convert/006c8c58f037da6facedc5a056a47802.png [43bcbb24c022ba18b346f3277e7e35b9.png]: https://img-blog.csdnimg.cn/img_convert/43bcbb24c022ba18b346f3277e7e35b9.png [90c4ca60f381b2ea8131b9cf9945495c.png]: https://img-blog.csdnimg.cn/img_convert/90c4ca60f381b2ea8131b9cf9945495c.png [1fa54f16869a60c65bb91dd3eb5d621e.png]: https://img-blog.csdnimg.cn/img_convert/1fa54f16869a60c65bb91dd3eb5d621e.png [852a8e2797648827ba0672a0b7d9e69b.png]: https://img-blog.csdnimg.cn/img_convert/852a8e2797648827ba0672a0b7d9e69b.png
相关 二叉搜索树 1 二叉搜索树 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点;右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质,当我们对二叉搜索树 心已赠人/ 2023年09月28日 09:18/ 0 赞/ 72 阅读
相关 二叉搜索树 在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的 Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 156 阅读
相关 二叉搜索树 搜索树数据结构支持许多动态集合操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此,我们使用一 ╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 155 阅读
相关 二叉搜索树 二叉搜索树的特征定义就是:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字大于或等于这个父节点 package Trees; import java.ut 客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 243 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于 ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 201 阅读
相关 二叉搜索树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy た 入场券/ 2022年03月17日 02:18/ 0 赞/ 240 阅读
相关 二叉搜索树 思路 二叉排序树,二叉搜索树好像都行,原理应该都懂,比较基础,但要写出来还是有相当大的难度的。 查找 查找比较简单,基本都是一个while就解决。但查前驱与后继较 短命女/ 2021年12月21日 09:15/ 0 赞/ 229 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不 小咪咪/ 2021年12月20日 02:53/ 0 赞/ 252 阅读
相关 二叉搜索树 二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9 今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 232 阅读
相关 二叉搜索树 二叉搜索树 基本概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 298 阅读
还没有评论,来说两句吧...