基于树的查找法

二叉排序树

定义

二叉排序树是一种特殊的二叉树，它分为两种：

  1. 一棵空树
  2. 具有如下性质的二叉树

如果左子树非空，左子树上的所有结点都小于根节点
如果右子树非空，右子树上的所有结点都大于根节点
它的左右子树也分别为二叉排序树
如上文所述，因为它是一种特殊的二叉树，所以结构上也大致与二叉树相同。

对于一个Node来说，我们需要如下结构：

  • 用于存储自身数据并且被查找的一个关键字key
  • 用于告诉我们谁是左右Child节点的两个指针变量 lchild、rchild

所以代码如下：

  1. typedef struct node{
  2.     KeyType key;
  3.     struct node *lchild, *rchild;
  4. } BSTNode, *BSTree;

操作

对于二叉排序树的操作分三类：插入与创建、查找、删除。

插入与创建

我们想要把一个新的节点插入进一棵二叉排序树中，就要让这个节点插入后仍然符合定义的要求。
于是咱们分这么几步：

  • 首先看看这棵树是否为空，如果是空，那么直接生成一个节点作为当前树的root
  • 如果非空，就把它与当前的root比较大小，比root小就去以lchild作为下一次判断的root进入下一次判断，比root大就以rchild作为下一次判断的root，如果相等，说明目前的树里已经包含了你要插入的元素，直接停止插入。

从而我们有了如下代码：

  1. void InsertBST(BSTree *bst, KeyType key){
  2.     BiTree s;
  3.     if(*bst==NULL){
  4.         s=(BSTree)malloc(sizeof(BSTNode));
  5.         s->key=key;
  6.         s->lchild=NULL; s->rchild=NULL;
  7.         *bst=s;
  8.     }else if(key<(*bst)->key)
  9.         InsertBST(&((*bst)->lchild), key);
  10.      else if(key>(*bst)->key)
  11.          InsertBST(&((*bst)->rchild), key);
  12. }

时间复杂度：

  • 插入算法的核心是找到它应该插入的位置。
  • 这棵树最多有多少层，就需要最多找多少次

所以时间复杂度为数据结构大纲 - 图1

如果我们需要从键盘上不断获取值来从头创建一个树，可以从键盘上获取一个值就InsertBST一次，直到获取到你设定的ENDKEY。

  1. void CreateBST(BSTree *bst){
  2.     KeyType key;
  3.     *bst=NULL;
  4.     scanf("%d", &key);
  5.     while(key!=ENDKEY){
  6.         InsertBST(bst,key);
  7.         scanf("%d", &key);
  8.     }
  9. }

时间复杂度：

  • 创建一个有n个节点的树，需要把相应的节点进行插入操作。
  • 所以时间复杂度为数据结构大纲 - 图2

查找

从上面插入元素的原则我们可以看出，比root小的元素全在左子树上，比root大的全在右子树上。所以说我们查找的时候就是在做两件事：

  • 把要找的这个数与现在的root对比
  • 如果这个数比root小，去左边继续找，如果不是，就去右边找，如果相等就输出。

由于每次的“找”这个过程涉及的逻辑都是一样的，所以我们可以用递归来完成这个程序。

  1. BSTree SearchBST(BSTree bst, KeyType key){
  2.     if(!bst) return NULL;
  3.     else if (bst->key==key) return bst;
  4.     else if (bst->key>key) return SearchBST(bst->lchild, key);
  5.     else
  6.         return SearchBST(bst->rchild, key);
  7. }

如果不使用递归，我们可以用下面的逻辑来实现同样的过程。

  1. BSTree SearchBST(BSTree bst, KeyType key){
  2.     BSTree q;
  3.     q=bst;
  4.     while(q){
  5.         if(q->key==key)    return q;
  6.         if(q->key>key)    q=q->lchild;
  7.         else q=q->rchild;
  8.     }
  9.     return NULL;
  10. }

删除

从二叉排序树中删除一个节点时，不能仅考虑这个节点的删除，还应该妥善处理这个节点的子节点。
我们用如下方法处理：

  1. 如果p为叶子节点，就直接删除
  2. 如果p节点只有左子树或者只有右子树，则可将p的左子树或右子树直接改为其双亲节点f的子树
  3. 如果p既有左子树，又有右子树，则：
  • 找到中序序列直接前驱节点s，s的双亲节点记为q
  • 把s的值赋给p
  • （如果s有左子树）把s的左子树链接到p的同侧child
  • 删除s节点

转换为如下代码：

  1. BSTNode *DelBST(BSTree t, char k){
  2.     BSTNode *p,*f,*s,*q;
  3.     p=t;f=NULL; 
  4.     while (p){
  5.         if (p->key==k)break;
  6.         f=p;
  7.         if (p->key>k)p=p->lchild;
  8.         else p=p->rchild;
  9.     }
  10.     if (p==NULL)return t;
  11.     if (p->lchild==NULL){
  12.         if (f==NULL)t=p->rchild;
  13.         else if (f->lchild==p)
  14.             f->lchild=p->rchild;
  15.         else
  16.             f->rchild=p->rchild;
  17.         free(p);
  18.     }
  19.     else{
  20.         q=p;s=p->lchild;
  21.         while (s->rchild){
  22.             q=s;s=s->rchild;
  23.         }
  24.         if (q==p)q->lchild=s->lchild;
  25.         else q->rchild=s->lchild;
  26.         p->key=s->key;
  27.         free(s);
  28.     }
  29.     return t;
  30. }
  • 由于删除操作的核心也是查找到需要删除元素的位置再进行删除操作，所以时间复杂度为数据结构大纲 - 图3