生成二叉排序树过程。
10 3 2 7 8 18 12
注:二叉排序树与关键字排列顺序有关,排列顺 序不一样,得到的二叉排序树也不一样。
二叉排序树的建立的算法
反复调用二叉排序树的插入算法即可 Bitree Creat (int n) { //建立含有n个结点的二叉排序树
Bitree T= NULL;
for ( int i=1; i<=n; i++) {
else if LT(key,p->key) p->lchild=s;
else p->rchild=s
return TRUE; }
//被插结点*s为右孩子
else return FALSE;
}// Insert BST
//树中已有关键字相同的结点,不再插入
4)二叉排序树的建立
例:关键字序列{ 10、18、3、8、12、2、7、3 }
5)二叉排序树上的删除
对于二叉排序树,删去树上一个结点相当于删去有序 序列中的一个记录,在删除某个结点之后依旧要保持二叉 排序树的特性。
如何在二叉排序树上删去一个结点呢?
设在二叉排序树上被删结点为*p(指向结点的指针为 p),其双亲结点为*f,设*p是*f的左孩子。 f F p P c PR C q Q s CL S QL SL
low
( 08,
( 08,
mid
14,
14,
high
55, 68, 79,
79,
23,
23,
37,
37,
46,
46,
91 )
low
55,
mid
68,
high
91 )
low mid