二叉排序树的构造过程
假设二叉排序树T为空，则创建一个keyword为k的结点。将其作为根结点。否则将k和根结点的keyword进行比较，假设相等则返回，假设k小于根结点的keyword则插入根结点的左子树中，否则插入根结点的右子树中。在二叉排序树删去一个结点，分三种情况讨论：若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树。其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱，即让*f的左子树(如果有的话)成为*p左子树的最左下结点(如果有的话)，再让*f成为*p的左右结点的双亲结点。扩展资料：在一般情况下，设 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 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。
二叉排序树怎么构造
假设二叉排序树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、二叉排序树：二叉排序树的左、右子树也分别为二叉排序树。
二叉排序树
二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。 实例 当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的左孩子是不是空，如果是空则将要插入的值作为当前节点的左孩子，不是空则将当前节点的左孩子作为当前节点继续查找；当要插入的值比当前节点的值大时，判断当前节点的右孩子是不是空，如果是空则将要插入的值作为当前节点的右孩子，不是空则把当前节点的右孩子作为当前节点继续查找 节点定义 递归实现 非递归实现 使用中序遍历，遍历出来的结构刚好是一个升序排列的数列 递归写法 非递归写法 搜索二叉排序树的时候，从根节点开始搜索，将根节点作为当前节点，如果当前节点的值和搜索的值相等，则搜索结束，返回成功；如果当前节点的值小于搜索值，则判断当前节点的左孩子是不是空，如果是空，则搜索的值不在树中，搜索结束返回失败，如果不为空，则将当前节点的左孩子作为当前节点，继续搜索；如果当前节点的值大于搜索值，则判断当前节点的右子树是不是空，如果是空，则搜索的值不在树中，搜索结束，返回失败，如果不为空，则将当前节点的右孩子作为当前节点，继续搜索。 二叉排序树的删除分为如下三种基本的情况 直接删除节点即可 将要删除的节点的孩子节点替换当前节点即可 在要删除的节点的右子树中找一个最小的值来替换掉要删除的节点，同时将这个最小的节点删除掉（也可以从左子树中找一个最大的节点） 具体情况 算法实现： 二叉排序树的查找时间与二叉树的高度有关，高度越高需要的查找时间就越多。 二叉排序树的高度有两种极端的情况，一种是完全二叉树，一种是每层只有一个节点的情况，变成了一个链表。 当是完全二叉树的时候：这种情况下的时间复杂为O(log2N) 当每一层只有一个节点时，也就是链表的时候：这种情况下的时间复杂度为O(n) 所以二叉排序树的搜索时间复杂度在：O(log2N) O(n)之间。它的插入，删除复杂度也在O(log2N) O(n)之间
