Question

二叉排序树怎么构造

Answer 1

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

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

  int InsertBST(BSTNode *p, KeyType k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k==p->key)
return 0;
else if(k<p->key)
return InsertBST(p->lchild, k);
else
return InsertBST(p->rchild, k);
}
二叉排序树的生成算法：
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InsertBST(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 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。

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

                                                  

Answer 2

二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。

扩展资料：

二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：

1、如果相等，查找成功；

2、如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；

3、如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；