8.3 动态查找,动态查找 特点：表结构本身是在查找中动态生成，对于给定值K，如表中存在，则查找成功；否则在适当的位置插入K 动态查找的结构主要针对二叉树结构讲解。,二叉排序树 又称为二叉查找树,它或者是空树，或者是满足如下性质的二叉树： （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。 （2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。 （3）它的左、右子树本身又各是一棵二叉排序树。,8.3 动态查找,例如，由关键字值序列50，70，20，10，60，30，80，5，75，35，95 构成的一棵二叉排序树如下图所示。,按中序遍历该树所得到的中序序列是一个递增有序序列 如上例：（5, 10, 20,30, 35,50,60,70,75,75,80,95）,二叉排序树的查找 在二叉排序树中查找的基本思想 用给定值k与根结点关键字值比较，如果k小于根结点的值，就继续在左子树中查找，否则将继续在右子树中查找，依此方法，一直查找下去，直至查找成功或查找失败为止。,二叉排序树查找的过程描述如下： （1）若二叉树为空树，则查找失败 （2）将给定值k 与根结点的关键字值比较，若相等，则查找成功 （3）若给定值k小于根结点的关键字值，则在左子树中继续搜索，如果左子树为空，则查找失败。 （4）否则，在右子树中继续查找，如果右子树为空，则查找失败,二叉排序树结构的定义： typedef struct BSTNode KeyType key; struct BSTNode * lchild, *rchild; BSTNode,*BSTree;,二叉排序树的查找算法描述如下 BSTree f; /* f指向移动指针p的双亲*/ BSTree BSTSearch(BSTree t, KeyType k) /*在根结点为t的二叉排序树中查找关键字值 等于k的结点*/ p=t; f=NULL; while (p!=NULL) if (k=p-key) return (p); /*查找成功*/ else if (kkey) f=p; p=p-lchild; /*在左子树中继续查找*/ else f=p; p=p-rchild; /*在右子树中继续查找*/ return (NULL); /*查找失败*/ /*BSTSearch*/,