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

但由于折半查找要求表为有序表，且不能采用链接存储结构，特别是当对表的插入或删除操作较为频繁时，为维持表的有序性，需移动表中的大量结点。这也会在很大程度上降低折半查找的时间性能。因此，折半查找只适用于静态查找结构。为了具有较高的查找效率又适合表的动态变化，可以将查找表组织成树形结构，我们把组织成树形结构的查找表统称为树 形 表，这是一种基于树形结构的动态查找结构。9.3.1 二叉排序树二叉排序树 binary sort tree 又称二叉查找 搜索 树 binary search tree 。二叉排序树或者是一棵空树；或者是具有如下性质的二叉树：⑴ 左子树 若存在 中所有结点的关键字都小于根结点的关键字；⑵ 右子树 若存在 中所有结点的关键字都大于根结点的关键字；⑶ 左子树和右子树也是二叉排序树。例9.4 设有关键字集合为 45, 12, 90, 03, 37, 52, 24, 78, 100, 61 ，其中每个关键字对应二叉树中的一个结点，可以构造出一棵如图9-5所示的二叉排序树。在讨论二叉排序树的运算之前，先给出存储结构的描述：typedef int keyType; //关键字类型设为整型typedef struct nodekeyType key;infoType otherinfo;struct node *lchild, *rchild;BSTNode;BSTNode *root, *p, *q, *r, *f ;KeyType K;下面讨论二叉排序树的运算：1. 查找设待查的关键字为K，在二叉排序树上进行查找的过程，就是从根结点开始，即首先把根结点作为当前结点，用给定值K与当前结点的关键字进行比较：⑴ 若指向当前结点的指针为空，则查找失败。

⑵ 若给定值K等于当前结点的关键字，则查找成功。⑶ 若K小于当前结点的关键字，则进入左子树把子树根作为当前结点继续进行比较。⑷ 若K大于当前结点的关键字，则进入右子树把子树根作为当前结点继续进行比较。重复以上⑴～⑷步，直到查找成功或查找失败 比较到叶仍不相等 为止。二叉排序树的查找算法可以用递归和迭代两种方法实现，下面分别给出二叉排序树查找的递归和迭代算法。算法开始时，二叉排序树已用lchild- rchild表示法链式存储，实参指针root指向其根；变量K中存放要查找的关键字。算法结束时，若查找成功，则返回查找到的结点地址；否则查找失败，返回NULL。算法9.3 查找的递归算法 C/C++ 程序：SearchBST p, K BSTNode* SearchBST BSTNode* p, keyType K 1. 若 p NULL if p NULL则 return NULL [ 查找失败 ] return NULL;否则 若 K p- key else if K p- key则return p [ 查找成功 ] return p;否则 若 K p - key else if K p- key则 return SearchBST p- lchild, K return SearchBST p- lchild,K ;否则return SearchBST p- rchild, K else2. [ 算法结束 ] ▌ return SearchBST p- rchild,K ; 算法9.4 查找的迭代算法 C/C++ 程序：SearchBST root, K BSTNode* SearchBST BSTNode *root,keyType K 1. p ← root BSTNode *p root;2. 循环 当p≠NULL 时，执行 while p ! NULL ⑴ 若 K p- key if K p- key return p;则return p [查找成功 ] if K p- key⑵ 若 K p- key p p- lchild;则 p ←p- lchild else否则 p ←p- rchild p p- rchild;3. return NULL [ 查找失败 ] 4. [ 算法结束 ] ▌ return NULL; 例如，在图9-5所示的二叉排序树中查找关键字等于给定值37的结点。

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