|
构造一棵二叉排序树就是依次输入数据元素，并将它们插入到二叉排序树中的适当位置上的过程。
具体过程是，每读入一个元素，就建立一个新结点，若二叉排序树非空，则将新结点的值与根结点的值比较，
如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新结点作为二叉排序树的根结点。
void Creat_BST(BiTree ST,KeyType str[],int n) {
//用关键字数组 str[] 建立一个二叉排序树
T=NULL; //初始时 bt 为空树
int i=0;
while(i<n){ / /依次将每个元素插入
BST_Insert(T,str[i]);
i++;
}
}
（5）二叉排序树的删除
在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，
必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。
删除操作的实现过程按 3 种情况来处理：
- 如果被删除结点 z 是计结点，则直接删除，不会破坏二叉排序树的性质。
- 若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
- 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z,然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
如图 4-22 所示，在 3 种情况下分别删除结点 45、78、78。
思考：若在二叉排序树中删除并插入某结点，得到的二叉排序树是否和原来的相同？
（6）二叉排序树的査找效率分析
对于高度为 H 的二叉排序树，其插入和删除操作的运行时间都是 (mathcal{O}(H))。
但在最坏的情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数 N,如图 4-23 所示。
在等概率情况下，图 4-23(a) 的査找成功的平均査找长度为
[ASL_a = (1+2x2+3x4+4x3)/10 = 2.9]
而图 4-23(b) 的査找成功的平均査找长度为
[ASL_b = (1+2+3+4+5+6+7+8+9+10)/10 = 5.5]
由上可知，二叉排序树査找算法的平均査找长度，主要取决于树的高度，即与二叉树的形态有关。
如果二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），其平均査找长度和单链表相同，为 (mathcal{O}(n))。
如果二叉排序树的左、右子树的高度之差的绝对值不超过 1，这样的二叉排序树称为平衡二叉树，它的平均査找长度达到 (mathcal{O}(log_2 n))。
从査找过程看，二叉排序树与二分査找相似。
就平均时间性能而言，二叉排序树上的査找和二分査找差不多。
但二分査找的判定树唯一，而二叉排序树不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树，如图 4-23 所示。
就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为 (mathcal{O}(log_2 n))。
二分査找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是 (mathcal{O}(n))。
当有序表是静态査找表时，宜用顺序表作为其存储结构，而采用二分査找实现其査找操作；若有序表是动态査找表，则应选择二叉排序树作为其逻辑结构。
4.5.2 平衡二叉树（Balanced Binary Tree）
（1）平衡二又树的定义
为了避免树的高度增长过快，降低二叉排序树的性能，我们规定
在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL 树）。
定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0 或 1。
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
