查找

key ) p = p -> lchild; else p = p -> rchild; } return ( p); }null 7.3.3 二叉排序树的插入 在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。 null下面是二叉排序树插入操作的递归算法。 void bt_insert1(Bin_Sort_Tree *bt , Bin_Sort_Tree_Node *pn) { //在以bt为根的二叉排序树上插入一个由指针pn指向的新的结点 if ( *bt =NULL) *bt = pn ; else if ( *bt -> key > pn->key ) bt_insert 1( &(*bt -> lchild) , pn ) ; else if ( *bt -> key < pn -> key ) bt_insert1 ( &(*bt -> rchild) , pn) ; } null这个算法也可以用非递归的形式实现，如下所示： void bt_insert 2(Bin_Sort_Tree *bt , Bin_Sort_Tree_Node *pn) { p = bt; while ( p != NULL && p -> key!= pn->key) { q = p; if ( p ->key > pn->key ) p = p -> lchild; else p = p -> rchild; } null if ( p =NULL ) { if ( q ->key > pn -> key ) q ->lchild = pn; else q -> rchild =pn ->key; } } 利用二叉排序树的插入算法，可以很容易地实现创建二叉排序树的操作，其基本思想为：由一棵空二叉树开始，经过一系列的查找插入操作生成一棵二叉排序树。 null 例如，由结点关键字序列 （62, 15, 68, 46, 65, 12 , 57 , 79, 35）构造二叉排序树的过程为：从空二叉树开始，依次将每个结点插入到二叉排序树中插入，在插入每个结点时都是从根结点开始搜索插入位置，找到插入位置后，将新结点作为叶子结点插入，经过9次的查找和插入操作，建成由这9个结点组成的二叉排序树。 创建二叉排序树的算法如下： Bin_Sort_Tree_Node *bt_bulid (Bin_Sort_Tree a , int n) { //在数组a的a[1]~a[n]单元中存放着将要构成二叉排序树的n个结点内容 null bt = NULL ; for ( i =1; i <= n;i++) { p = (Bin_Sort_Tree_Node *)malloc (sizeof (Bin_Sort_Tree_Node)); p ->key =a[i].key; p -> otheritem= a[i].otheritem;; p -> lchile = NULL; p -> rchile = NULL; bt_insert1( &bt , p); } return ( bt) ; } null 7.3.4 二叉排序树的删除 下面分四种情况讨论一下如何确保从二叉树中删除一个结点后，不会影响二叉排序树的性质： （1）若要删除的结点为叶子结点，可以直接进行删除。 （2）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。 （3）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤⑵类似。 （4）若要删除结点的左右子树均非空，则首先找到要删除结点的右子树中关键字值最小的结点（即子树中最左结点），利用上面的方法将该结点从右子树中删除，并用它取代要删除结点的位置，这样处理的结果一定能够保证删除结点后二叉树的性质不变。7.4 哈希表7.4 哈希表 7.4.1 哈希表的概念 前面介绍的静态查找表和动态查找表的特点是：为了从查找表中找到关键字值等于某个值的记录，都要经过一系列的关键字比较，以确定待查记录的存储位置或查找失败，查找所需时间总是与比较次数有关。 如果将记录的存储位置与它的关键字之间建立一个确定的关系H，使每个关键字和一个唯一的存储位置对应，在查找时，只需要根据对应关系计算出给定的关键字值k对应的值H(k)，就可以得到记录的存储位置，这就是本节将要介绍的哈希表查找方法的基本思想。null 哈希