8.3 树表的查找

南山隐士 2022年07月31日 31 0

要求能够叙述二叉排序树的定义和性质,对给定关键字序列,能够熟练的构造出一棵二叉排序树,能手工操作二叉排序树的插入和删除。

树表查找是指查找表用一棵二叉树表示,其存储结构采用二叉链表,链表中每个结点对应查找表的一个记录。

1.二叉排序树的定义

二叉排序树(Binary Sort Tree)或者是一棵空树,或者是具有下列性质的二叉树:

若它的左子树非空,则在左子树的所有结点的值都小于它的根结点的值

若它的右子树非空,则在右子树的所有结点的值都大于(若允许结点有相同的值,则大于等于)它的根结点的值

左、右子树也分别是一棵二叉排序树

简言之,二叉排序树的每个结点的值都大于它的左子树上的所有结点的值,而小于它的右子树上所有结点的值。图8-5所示就是一棵二叉排序树。

图8-5 二叉排序树示例

2.二叉排序树的性质

中序遍历二叉排序树,可以得到一个由小到大的有序序列。

例如,中序遍历如图8-5所示的二叉排序树,其结果序列为(26,40,50,55,58,65,68),是一个由小到大的有序序列。

想一想:为什么中序遍历二叉排序树可以得到一个由小到大的有序序列?

解题分析:

二叉排序树的定义是:二叉排序树的每个结点的值都大于它的左子树上的所有结点的值,小于它的右子树上所有结点的值。而中序遍历的规则是:先遍历左子树,然后访问根结点,再遍历右子树。所以中序遍历二叉排序树就会得到一个由小到大的有序序列。

3.二叉排序树的查找

若将查找表按二叉排序树的结构来组织,即树中每个结点对应一个记录,所有记录的关键字值满足二叉排序树的要求。对给定的查找值,就能针对二叉排序树进行查找。具体做法如下:当二叉排序树为空时,查找失败;当二叉排序树非空时,先将给定值与根结点的关键字进行比较,若相等则表示查找成功;否则,判断给定值与根结点关键字之间的大小关系,小于根结点则在其左子树中继续查找,大于根结点则在其右子树中继续查找。很显然,每次只需要在根结点的左或右子树中的某一个分支进行查找,因此,查找效率大大提高。

二叉排序树中结点的结构类型定义如下:

typedef struct Bnode

{

int key;

struct Bnode *left;

struct Bnode *right;

} Bnode;

【算法8-4】 二叉排序树的查找算法

Bnode *BSearch(Bnode *bt, int k)

/在二叉树bt中查找关键字值为key的记录/

{

  Bnode *p;

  if(bt==NULL)

  return (bt);

  p=bt;

  while(p->key!=k)       /若没有查找到,继续查找过程/

  {

    if(kkey)         /准备从左子树继续查找/

      p=p->left;

    else p=p->right;     /准备从右子树继续查找/

      if(p==NULL) break;  /查完能查找的最后一个关键字,仍未查到,结束查找/

  }

  Return(p);

}

4.二叉排序树的插入和删除

二叉排序树是一种有重要应用意义的数据类型,在二叉排序树上能有效地进行查找操作。同时采用适当算法,根据一组关键字值可以方便地建立与之相应的二叉排序树。按照一定规则在二叉排序树上插入、删除结点仍能保持二叉排序树的性质。

(1)二叉排序树的插入操作

如何建立一棵二叉排序树以及如何在二叉排序树中插入一个新结点呢,实际上,只要解决了插入问题,建树过程就是从空树开始逐次插入新结点的操作,需要注意的是插入一个结点后的二叉树仍然为一棵二叉排序树。

具体做法是:动态生成一个新结点,若二叉排序树为空,则结点作为根结点插入;若非空,则用新结点的关键字值与根结点的关键字比较,若小于根结点的关键字值,新结点应插入左子树,否则,应插入右子树。在左子树或右子树上进行同样的操作,实际上这是一个递归过程。最后新结点的插入位置是二叉排序树中某结点的空指针位置。新结点是作为二叉排序树的叶结点插入,所以新结点插入时它的左、右指针均为空指针。

【算法8-5】 二叉排序树中插入新结点的非递归算法

#include

#include

#define MAX 5

#define NULL 0

Bnode * btInsert(int x, Bnode *root);

void main()

{

int i;

int a[MAX]={60, 40, 70, 20, 80};

Bnode * root=NULL;

for(i=0;i

root=btInsert(a[i],root);

/通过循环调用插入函数,把a[i]逐次插入root为根的二叉排序树中/

}

Bnode * btInsert(int x, Bnode *root)

/root为二叉排序树的根指针,x为新结点的关键字值/

{

Bnode *p, *q;

int flag=0; /是否完成插入的标志/

p=(Bnode *)malloc(sizeof(Bnode));

p->key=x ; /为新结点关键字赋值/

p->right=p->left=NULL; /新结点要作为叶结点插入/

if(root==NULL)

{

root=p;

return p;

}

q=root;

while(flag==0) /flag==1标志完成插入/

{

if(q->key>x)

{

  if(q->left!=NULL)

  q=q->left;

else

{

  q->left=p;               /*在左子树插入*/

  flag=1;

}

}

else

{

  if(q->right!=NULL)

     q=q->right;

  else

  {

    q->right=p;          /*在右子树插入*/

    flag=1;

  }

}

}

return root;

}

对于给定的一个数据元素的集合,循环调用上述二叉排序树的非递归插入算法,便可构造出一棵二叉排序树。图8-6 是对关键字序列{60,40,70,20,80},按所给关键字的顺序用插入法构造一棵二叉排序树的过程。

图8-6 构造二叉排序树的过程示意图

第一个关键字60为根结点,第二个关键字40小于60,所以应为根结点的左孩子,第三个关键字70大于根结点60,因此应为其右孩子。接下来,20先和根结点60比较,小于60,则20应在根的左子树上,继续与左子树的根结点40比较,20小于40,应为40这个结点的左孩子。以此类推,可得出一棵二叉排序树。

用二叉排序树的插入算法动态生成的二叉排序树,树的形状、高度不仅仅依赖于关键字值的大小和数量,还与记录输入的先后次序有关系。如上例中的关键字序列{60,40,70,20,80},若按{20,40,60,70,80}的次序输入的话,得到的二叉排序树如图8-7所示。


图8-7 构造二叉排序树的过程示意图

(2)二叉排序树的删除操作

同插入结点一样,要求删除一个结点后的二叉树仍然为一棵二叉排序树。图8-8为删除二叉排序树中不同位置结点的示例。图8-8 (a)为要删除结点的二叉排序树,分下面四种情况来考虑:

(1)若待删除的是叶子结点,直接删除即可。如图8-8(b)所示。

(2)若待删除结点只有右子树,而没有左子树,可以直接将其右子树的根结点放到被删除结点的位置上。如图8-8(c)所示。

(3)若待删除结点只有左子树,而没有右子树,可以直接将其左子树的根结点放到被删除结点的位置上。如图8-8(d)所示。

(4)若待删除结点p既有左子树又有右子树,首先找出p结点的右子树中关键字最小的结点,设为s,因为它最小,所以s没有左子树。此时,用结点s取代结点p的位置,而用s的右子树的根结点(连带该根结点的后代)取代s结点的位置,如图8-8(e)所示。


图8-8 在二叉排序树中删除结点示意图

可以证明,二叉排序树的平均查找长度为O(log2n)。在二叉排序树上可以方便地进行结点的插入和删除,因此,对于经常要进行插入和删除运算的查找表,采用二叉排序树是最佳的选择。

Last Updated: 2022/07/31 23:24:04
8.4 哈希表及其查找 8.2 线性表的查找