二叉搜索树 超、凢脫俗 2024-04-19 09:50 1阅读 0赞 ## 二叉搜索树 ## > **二叉搜索树(又名二叉查找树、二叉排序树)：它或者是一棵空树，或者是具有下列性质的二叉树：** > ** 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；** > ** 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；** > ** 它的左、右子树也分别为二叉搜索树。** ##### 举个栗子，下图便是一个二叉搜索树： ##### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70] ##### 二叉搜索树最重要的性质：`二叉搜索树的中序遍历是升序的`。 ##### ##### 对于二叉搜索树的基本操作来讲，与二叉树的大致相同，无非增删改查。 ##### ##### 本篇文章不直接处理一颗二叉搜索树，而是自己实现一个简化版的Map集合，该简化版Map集合的底层由一颗二叉搜索树组成(Java中Map的实现是利用哈希表+红黑树)，通过对Map集合的操作，完成对二叉搜索树的学习和理解。 ##### ##### 首先定义出Map的大体轮廓，Map是由key-value组成的键值对的集合，那么首先定义二叉搜索树结点类Node(静态内部类) ##### private static class Node{ int key; int value; public Node(int key, int value) { this.key = key; this.value = value; } Node left; Node right; } ##### 并在自定义Map类(BinaryTreeForMap)中，创建二叉搜索树的根节点root。 ##### private Node root = null; ##### 根据二叉搜索树查找当前key所对应的value，此处采用while循环，也可使用递归调用。BinaryTreeForMap的get()方法如下： ##### ###### 由于二叉搜索树的中序遍历是升序的，则很容易想到，若key小于当前节点的值，则需要在当前节点的左子树中找，若key大于当前节点的值，则需要在当前节点的右子树中找，否则若相等，则返回当前节点的value值。 ###### public int get(int key){ Node cur = this.root; while (cur!=null){ if(key<cur.key){ cur = cur.left; }else if(key>cur.key){ cur = cur.right; }else { return cur.value; } } return -1; } ##### Map中元素的增加和修改都对应了二叉搜索树的插入，由于Map的特性(key不能重复)，因此如果没找到当前key所对应的节点就进行插入操作，若找到当前key所对应的结点就进行修改(更新)操作。<该段代码的注释已经讲得很清楚了> ##### public int put(int key,int value){ // 若root为null，只需要新建一个root结点即可，不需要做下面的操作了 if (this.root == null){ this.root = new Node(key,value); return -1; } // 为插入操作设置父节点 Node parent = null; Node cur = this.root; // 如果在循环里就return了，证明是找到结点并进行修改 while (cur!=null){ if(key<cur.key){ parent = cur; cur = cur.left; }else if(key>cur.key){ parent = cur; cur = cur.right; }else { int oldValue = cur.value; cur.value = value; return oldValue; } } // 如果循环退出仍没有return，证明是没找到结点，应该进行插入(记录了parent) Node node = new Node(key,value); // 新结点可能是parent的左孩子，也可能是右孩子 // 此时需要访问parent的value域，这时就要考虑，parent会不会为null // parent为null只有一种可能——root为null，程序不会进入上面的循环， // 由此，需要在上面添加一步判断root的操作 if(key<parent.key){ parent.left = node; }else { parent.right = node; } return -1; } ##### 最难理解也是最重要的就是Map的删除操作了，同样对应二叉搜索树的删除操作。二叉搜索树的删除操作有8种可能性(设cur为被删除的结点) ##### ###### 1、cur.left==null(默认包含了cur.left==null&&cur.right==null的情况) ###### ###### 1.1 cur是其父节点的左节点 ###### ###### 1.2 cur是其父节点的右节点 ###### ###### 1.3 cur是根节点 ###### ###### 2、cur.right==null ###### ###### 2.1 cur是其父节点的左节点 ###### ###### 2.2 cur是其父节点的右节点 ###### ###### 2.3 cur是根节点 ###### ###### 3、cur.left!=null&&cur.right!=null(`替换法——找左子树最大/找右子树最小——以下操作使用找左子树最大`) ###### ###### 3.1 maxNode是其父节点的左节点(可能左子树最大的元素是要被删除结点的左子节点) ###### ###### 3.2 maxNode是其父节点的右节点(普通情况) ###### ##### 先贴一下代码，返回被删除结点的value，若结点不存在，返回-1。 ##### public int remove(int key){ if(root == null){ return -1; } Node cur = this.root; Node parent = null; int ret = -1; while(cur!=null){ if(key<cur.key){ parent = cur; cur = cur.left; }else if(key>cur.key){ parent = cur; cur = cur.right; }else { ret = cur.value; // 找到结点进行删除工作 if(cur.left == null){ if(cur==this.root){ ret = cur.value; this.root = cur.right; break; } if(cur == parent.left){ parent.left = cur.right; break; }else{ parent.right = cur.right; break; } }else if(cur.right == null){ if(cur==this.root){ ret = cur.value; this.root = cur.left; break; } if(cur == parent.left){ parent.left = cur.left; break; }else { parent.right = cur.left; break; } }else { Node maxNode = cur.left; Node maxParent = cur; while (maxNode.right!=null){ maxParent = maxNode; maxNode = maxNode.right; } cur.key = maxNode.key; cur.value = maxNode.value; if(maxNode==maxParent.left){ maxParent.left = maxNode.left; }else { maxParent.right = maxNode.left; } } } } return ret; } ##### 看逻辑+代码可能有些难以理解，下面用图片来理清思路。 ##### ###### 1、cur.left==null ###### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 1] ###### 2、cur.right==null ###### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 2] ###### 3、cur.left!=null&&cur.right!=null ###### ###### 3.1 maxNode是其父节点的左节点(可能左子树最大的元素是要被删除结点的左子节点) ###### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 3] ###### 3.2 maxNode是其父节点的右节点(普通情况) ###### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 4] ##### 基本上二叉搜索树的相关操作逻辑就是这么多，最难的就是二叉搜索树删除的8种情况的讨论，然而通过二叉搜索树还可以实现Map的其他方法及操作，可以查看源码：[二叉搜索树实现简化版Map][Map]。 ##### [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/082c053e059f410ba1dfbbdf0860bfce.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1100bca848b2451ab1e84ea9ce53aa31.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/989fe360e2b346749cf99292e82ef612.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5547a43829084560ac24840092f3fab3.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ5MDQ0MA_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ae52c430438041adb6c93c89a975cb44.png [Map]: https://github.com/xiaomessi/JavaTest/blob/master/JavaDSTest/src/com/xiaoaxiao/binary_search_test/BinarySearchTree.java
相关 二叉搜索树 1 二叉搜索树 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点；右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质，当我们对二叉搜索树 心已赠人/ 2023年09月28日 09:18/ 0 赞/ 66 阅读
相关 二叉搜索树 在计算机术语中，二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树（Binary Search Tree）的定义： 它或者是一棵空树，或者是具有下列性质的二叉树： 若它的 Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 154 阅读
相关 二叉搜索树 搜索树数据结构支持许多动态集合操作，包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此，我们使用一 ╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 152 阅读
相关 二叉搜索树 二叉搜索树的特征定义就是：一个节点的左子节点的关键字值小于这个节点，右子节点的关键字大于或等于这个父节点 package Trees; import java.ut 客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 241 阅读
相关 二叉搜索树 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于 ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 198 阅读
相关 二叉搜索树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy た 入场券/ 2022年03月17日 02:18/ 0 赞/ 236 阅读
相关 二叉搜索树 思路 二叉排序树，二叉搜索树好像都行，原理应该都懂，比较基础，但要写出来还是有相当大的难度的。 查找 查找比较简单，基本都是一个while就解决。但查前驱与后继较 短命女/ 2021年12月21日 09:15/ 0 赞/ 225 阅读
相关 二叉搜索树 二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不 小咪咪/ 2021年12月20日 02:53/ 0 赞/ 249 阅读
相关 二叉搜索树 二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9 今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 227 阅读
相关 二叉搜索树 二叉搜索树 基本概念 二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 296 阅读
心已赠人
Myth丶恋晨
╰+哭是因爲堅強的太久メ
今天药忘吃喽~
还没有评论，来说两句吧...