二叉排序树（二叉排序树的删除）
如果有更好的建议或者想看更多关于综合百科技术大全及相关资讯，可以多多关注茶馆百科网。
#本文目录一览
1、什么是二叉排序树?2、二叉排序树3、什么是二叉排序树二叉排序树要么是空二叉树，要么具有如下特点：
二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
二叉排序树的左右子树也要求都是二叉排序树；
二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。
实例
当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的左孩子是不是空，如果是空则将要插入的值作为当前节点的左孩子，不是空则将当前节点的左孩子作为当前节点继续查找；当要插入的值比当前节点的值大时，判断当前节点的右孩子是不是空，如果是空则将要插入的值作为当前节点的右孩子，不是空则把当前节点的右孩子作为当前节点继续查找
节点定义
递归实现
非递归实现
使用中序遍历，遍历出来的结构刚好是一个升序排列的数列
递归写法
非递归写法
搜索二叉排序树的时候，从根节点开始搜索，将根节点作为当前节点，如果当前节点的值和搜索的值相等，则搜索结束，返回成功；如果当前节点的值小于搜索值，则判断当前节点的左孩子是不是空，如果是空，则搜索的值不在树中，搜索结束返回失败，如果不为空，则将当前节点的左孩子作为当前节点，继续搜索；如果当前节点的值大于搜索值，则判断当前节点的右子树是不是空，如果是空，则搜索的值不在树中，搜索结束，返回失败，如果不为空，则将当前节点的右孩子作为当前节点，继续搜索。
二叉排序树的删除分为如下三种基本的情况
直接删除节点即可
将要删除的节点的孩子节点替换当前节点即可
在要删除的节点的右子树中找一个最小的值来替换掉要删除的节点，同时将这个最小的节点删除掉（也可以从左子树中找一个更大的节点）
具体情况
算法实现：
二叉排序树的查找时间与二叉树的高度有关，高度越高需要的查找时间就越多。
二叉排序树的高度有两种极端的情况，一种是完全二叉树，一种是每层只有一个节点的情况，变成了一个链表。
当是完全二叉树的时候：这种情况下的时间复杂为O(log2N)
当每一层只有一个节点时，也就是链表的时候：这种情况下的时间复杂度为O(n)
所以二叉排序树的搜索时间复杂度在：O(log2N)O(n)之间。它的插入，删除复杂度也在O(log2N)O(n)之间
二叉排序树（BinarySortTree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：
若左子树不空，则左子树上所有节点的值均小于它的根节点的值
若右子树不空，则右字数上所有节点的值均大于它的根节点的值
它的左、右子树也分别为二叉排序数（递归定义）
从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（BalencedBinaryTree）
所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）
OK，关于二叉排序树和二叉排序树的删除的内容到此结束了，希望对大家有所帮助。
本文主要介绍了关于二叉排序树（二叉排序树的删除）的相关养殖或种植技术，综合百科栏目还介绍了该行业生产经营方式及经营管理，关注综合百科发展动向，注重系统性、科学性、实用性和先进性，内容全面新颖、重点突出、通俗易懂，全面给您讲解综合百科技术怎么管理的要点，是您综合百科致富的点金石。
以上文章来自互联网，不代表本人立场，如需删除，请注明该网址：http://23.234.50.4:8411/article/222119.html