二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(7)

首先给定值37与根结点的关键字45进行比较，因为给定值37 45，所以进入根的左子树中查找，再用给定值37与左子树的根12比较，37 12，再进入12的右子树，继续与右子树的根37比较，这时两者相等，以查找成功而结束。又例如查找与给定值50相等的结点。首先也是与根结点比较，50 45，进入根的右子树，再与右子树的根90比较，50 90，再进入90的左子树，继续与左子树的根52比较，50 52，还应进入52的左子树，但这时52的左子树为空，所以得到的是空指针，即以查找失败而告终。2. 插入往二叉排序树里插入新结点，要保证插入后仍满足二叉排序树的定义。插入的方法是：将待插结点的关键字与树根的的关键字进行比较，若待插入结点的关键字小于根结点的关键字，则进入左子树，否则进入右子树，在子树里再继续与子树的根进行比较，如此进行下去，直到把新结点作为一个新的树叶插入到二叉排序树中。实际上，新结点的插入位置就是在二叉排序树中进行查找时最后一次比较的结点的左子女或右子女。因此，只需对二叉排序树的查找算法稍加修改即可。下面是对查找算法修改后的二叉排序树插入的递归和迭代算法。算法开始时，指针root指向二叉排序树的根；指针q指向欲插入的新结点。

算法结束时，已完成一个新结点的插入。算法9.5 插入的递归算法 C/C++ 程序：InsertBST p, q InsertBST BSTNode* &p, BSTNode* q 1. 若 p NULL [ 空二叉树 ] if p NULL则 p ← q [ 插入 ] p q;否则 若 q- key p- key [ 结点已存在 ] else if q- key p- key则 算法结束 return;否则 若 q- key p- key else if q- key p- key则 Insert BST p- lchild, q InsertBST p- lchild, q ;否则 InsertBST p- rchild, q else2. [ 算法结束 ] ▌ InsertBST p- rchild, q ; 算法9.6 插入的非递归算法 C/C++ 程序：InsertBST root, q InsertBST BSTNode* &root, BSTNode* q 1. p ← root; f ← NULL [ *f是*p的父母 ] BSTNode *f NULL, p root;2. 循环 当p≠NULL 时，执行 while p ! NULL ⑴ 若 q- key p- key if q- key p- key return;则 算法结束 [ 结点已存在 ] if q- key p- key⑵ 若 q- key p- key f p; p p- lchild;则 f ←p; p ←p- lchild else否则f ←p; p ←p- rchild f p; p p- rchild;3. 若 f NULL [ 插入 ] 则 root ← q if f NULL root q;否则 若 q- key f - key else if q- key f- key 则 f - lchild ← q f- lchild q;否则f - rchild ← q else f- rchild q;4. [ 算法结束 ] ▌ 对于给定的关键字集合，为了建立二叉排序树，可以从一个空的二叉排序树开始，反复调用插入算法，将关键字逐个地插入进去， 前面二叉排序树的例子就可以通过这样的方法得到的。

将关键字集合组织成二叉排序树，实际上起到了对集合里的关键字进行排序的作用。按对称序遍历二叉排序树，就能得到排好序的关键字序列。3. 删除从二叉排序树里删除一个结点时，要保证删除这个结点后仍保持二叉排序树原来的性质。设p, f, r是指针变量，*p为欲删结点，*f为*p的双亲结点，则删除的一种方法是：? 若结点 *p没有左子树，则用它的右子树的根来替代被删除结点 *p；? 若结点 *p有左子树，则在它的左子树里找“最右下” 即中序遍历最后一个访问的 结点 *r，将 *r的右指针置成指向 *p的右子树的根，然后用结点 *p的左子树的根去替代被删除的结点 *p。例9.5 图9-6给出了上述两种情况的示例。图9-6情况 a 是欲删结点45没有左子树的情形；图9-6情况 b 是欲删结点45有左子树的情形。删除的方法不止一种，只要删除后仍保持二叉排序树的性质即可。例如，上述的删除方法中的?可以改为：?' 找到结点* r后先将* r从树中删除 * r的右指针显然为空，直接用 *r的左子树替代 *r即可 ，然后用 *r去替代真正要删除的结点 *p 参见图9-7 。下面给出按方法 ?、? 的规定所进行的二叉排序树的结点删除算法，而编制按方法 ?、?' 的规定所进行的二叉排序树的结点删除算法留给读者编写 请见本章后的习题 。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-7.html