二叉排序树怎么构造
假设二叉排序树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(kkey)return InsertBST(p->lchild, k);elsereturn 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 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。参考资料来源：百度百科——二叉排序树
二叉树和二叉排序树有啥区别
二叉树和二叉排序树区别为：子树结点不同、键值相等不同、子树树型不同。一、子树结点不同1、二叉树：二叉树的左/右子树上所有结点的值可以大于、等于和小于它的根结点的值。2、二叉排序树：二叉排序树若左/右子树不空，则左/右子树上所有结点的值均小于它的根结点的值。二、键值相等不同1、二叉树：二叉树可以有键值相等的结点。2、二叉排序树：二叉排序树没有键值相等的结点。三、子树树型不同1、二叉树：二叉树的左、右子树也分别为二叉树。2、二叉排序树：二叉排序树的左、右子树也分别为二叉排序树。
