数据结构-二叉排序树（图文详细版） 文章目录 ⭐前言⭐🍓一，二分搜索树的特性1，中序遍历的序列是递增的序列2，中序遍历的下一个节点，称后继节点，即比当前节点大的最小节点3，中序遍历的前一个节点，称前驱节点，即比当前节点小的最大节点 🍒二，添加节点1，思路2，代码实现 🍌三，删除任意节点1，思路2，示例分析3，代码实现 🍎四，查找节点1，思路2，代码实现 🍇五，总结1，二分搜索树的优缺点2，时间-空间复杂度 ⭐前言⭐ 二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 二叉排序树或者是一棵空树，或者是具有下列特点的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树； 🍓一，二分搜索树的特性 1，中序遍历的序列是递增的序列 public LinkedList inorder(TreeNode root, LinkedList arr) { if (root == null) return arr; inorder(root.left, arr); arr.add(root.val); inorder(root.right, arr); return arr; } 
2，中序遍历的下一个节点，称后继节点，即比当前节点大的最小节点 public int successor(TreeNode root) { root = root.right; while (root.left != null) root = root.left; return root; } 3，中序遍历的前一个节点，称前驱节点，即比当前节点小的最大节点 public int predecessor(TreeNode root) { root = root.left; while (root.right != null) root = root.right; return root; } 
🍒二，添加节点 1，思路 🌸（1）比较根节点和value的值 🌸（2）把value添加在叶子节点 
2，代码实现 🍌三，删除任意节点 1，思路 （1）若value < root.val，则在左子树进行删除 （2）若value >root.val，则在右子树进行删除 （3）若value == root.val，此节点就是要删除的 ① 该节点是叶子，直接删除 ②该节点只有左子树，将前驱节点代替根节点，删除前驱节点 ③该节点只有右子树，将后继节点代替根节点，删除后继节点 （4）返回根节点root 
2，示例分析 （1）要删除的节点为叶子节点，可以直接删除 
（2）删除的节点不是叶子节点，只有右节点，则该节点可以由该节点的后继节点替代，然后可以从后继节点的位置递归向下操作以删除后继节点。 
（3）删除的节点不是叶子节点，只有左节点。这意味着它的后继节点在它的上面，但是我们并不想返回。我们可以使用它的前驱节点进行替代，然后再递归的向下删除前驱节点。 
3，代码实现 🍎四，查找节点 1，思路 🍎 (1)查找二分搜索树是否包含指定值-二分查找 🍎 (2)返回二分搜索树的最小值 🍎 (3)返回二分搜索树的最大值 
2，代码实现 🍇五，总结 1，二分搜索树的优缺点 （1）⭐优势⭐ 查找素、插入素、删除素的时间复杂度都是O(logn)。还可以方便的回答很多数据之间关系的问题:min，max，floor，ceil，rank，select （2）⭐局限性⭐ 当将一组数据以近乎有序的顺序插入空二分搜索树中时，几乎每一个节点都是父节点的右孩子，二分搜索树近乎退化成了一个链表，相关算法时间复杂度都退化成了O(N)。因此有了平衡二叉树，不会退化成链表，如：红黑树等。 2，时间-空间复杂度 🍓二叉排序树是平衡的，则n个节点的二叉排序树的高度为,其查找效率为，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。 🍓二叉树的空间复杂度：因为需要建立排序二叉树，所以空间复杂度为O（n）
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/90048.html
