二叉排序树(二叉排序树平均查找长度)

什么是二叉排序树

二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：

若左子树不空，则左子树上所有节点的值均小于它的根节点的值

若右子树不空，则右字数上所有节点的值均大于它的根节点的值

它的左、右子树也分别为二叉排序数（递归定义）

从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）

所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）

二叉排序树定义

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

定义一：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

定义二：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树。

定义三：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不 同的需求进行进行选择。

插入删除：
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

什么是二叉排序树?

二叉排序树要么是空二叉树，要么具有如下特点：

二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；二叉排序树的左右子树也要求都是二叉排序树；

二叉树排序

二叉排序树就是中序遍历之后是有序的；

构造二叉排序树步骤如下；

插入法构造

第二个结点4比6来的小所以插入在6的左子树；

第三个结点8比6来的大所以插入在6的右子树；

第四个结点5比6来得小先进入左子树然后跟4比较，

5比4大所以插入在4的右子树；

以此类推将要插入的结点先跟根结点比较，比根结点大进入右子树反之进入左子树；

在跟进入的左子树（右子树）的结点比较方法同上；

直到没有结点了 在插入； 你给的排序最后的二叉排序树如下；

中序遍历结果是 ： 3456789；

先序遍历结果是：6435879；

【数据结构】二叉排序树(Binary Sort Tree)（建立、插入、删除）

二叉排序树(Binary Sort Tree) ，又称 二叉查找树 。它是一颗 空树 ，或者具有下列性质：

二叉排序树的删除操作相对复杂，因为不能因为删除了结点，让这颗二叉排序树变得不满足二叉排序树的性质，所以对于二叉排序树的删除存在三种情况：

将它的直接前驱或者直接后继作为删除结点的数据

对于二叉排序树的建立，可以通过二叉排序树的插入操作来实现。
通过中序遍历二叉排序树，结果是从小到大输出。

二叉排序树怎么构造

假设二叉排序树T为空，则创建一个keyword为k的结点。将其作为根结点。

否则将k和根结点的keyword进行比较，假设相等则返回，假设k小于根结点的keyword则插入根结点的左子树中，否则插入根结点的右子树中。

int InrtBST(BSTNode *p, KeyType k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
el if(k==p->key)
return 0;
el if(k<p->key)
return InrtBST(p->lchild, k);
el
return InrtBST(p->rchild, k);
}
二叉排序树的生成算法：
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InrtBST(bt, A[i]);
i++;
}
return bt;
}

扩展资料：

在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。

参考资料来源：百度百科——二叉排序树