第8章-1(查找的基本概念)讲义.ppt

例如，给定关键字序列如下： 18,7,26,34,15,42,36,70,60,55,83,90,78,72,74，假设m=3，s=5，即将该序序分成3个子表，每个子表有5 个元素，则得到的主表和索引表如图8-5所示。 8．3 树表查找 8.3.1二叉排序树查找 1．什么是二叉排序树 二叉排序树（Binary Sorting Tree），它或者是一棵空树， 　或者是一棵具有如下特征的非空二叉树： (1)若它的左子树非空，则左子树上所有结点的关键字均小 　于根结点的关键字； (2)若它的右子树非空，则右子树上所有结点的关键字均大 　于等于根结点的关键字； (3)左、右子树本身又都是一棵二叉排序树。 2．二叉排序树的数据类型描述 和第六章类似，可以用一个二叉链表来描述一棵二叉排序树，具体为： struct Btreenode { elemtype data; //代表关键字 Btreenode *left,*right; //代表左、右孩子 }; 3．二叉排序树的基本运算 （1）二叉排序树的插入 若二叉排序树为空，则作为根结点插入，否则，若待插入的值小于根结点值，则作为左子树插入，否则作为右子树插入，算法描述为： void Insert (Btreenode *BST ,elemtype X ) { if(BST= =NULL) { Btreenode *p= new Btreenode; p - data = X; p-left=p-right=NULL; BST=p; } else if (BST-data = X ) Insert ( BST - left,X); //在左子树中扦入 else Insert (BST-right,X); //在右子树中扦入 } （2）二叉排序树的建立 只要反复调用二叉排序树的扦入算法即可，算法描述为： Btreenode *Creat (int n) //建立含有n个结点的二叉排序树 { Btreenode *BST= NULL; for ( int i=1; i=n; i++) { cinx; //输入关键字序列 Insert ( BST,x); } return BST ; } 例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如图8-6所示。（注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样） 4．二叉排序 树上的查找 （1）二叉排序 树的查找思想 若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。 （2）二叉排序树查找的算法实现 Btreenode * find( Btreenode *BST,elentype x) //在以BST为根指针的二叉排队 树中查找值为x的结点 { if ( BST= =NULL) return NULL; //查找失败 else { if (BST-data= =x) //查找成功 return BST; else if (BST-datax) //进入左子树查找 return find ( BST-left,x); else //进入右子树查找 return find (BST-right,x); } } 5．二叉排序树