第4节 二叉排序树查找.ppt

第七章 查找技术 1.若它的左子树不空，则左子树上所有结点的值均小于根结点的值； 二叉排序树或者是一棵空树，或者是具有如下特性的二叉树： 3.它的左、右子树也都分别是二叉排序树。 2.若它的右子树不空，则右子树上所有结点的值均大于根结点的值； §7.4 二叉排序树查找 一、二叉排序树的定义 50 30 80 20 90 10 85 40 35 25 23 88 是二叉排序树。 66 不 §7.4 二叉排序树查找 将数据元素构造成二叉排序树的优点： 1.查找过程与顺序结构有序表中的折半查找相似，查找效率高； 2.中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； 3.如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。 §7.4 二叉排序树查找 ——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。 45 24 53 12 90 查找成功，返回 查找成功，返回 则生成二叉排序树的过程为： 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 二、二叉排序树的建立 §7.4 二叉排序树查找 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90） 24 53 45 12 90 则生成的二叉排序树形态不同： 查找成功，返回 查找成功，返回 注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！ §7.4 二叉排序树查找 struct btnode *inbsort (ET a[ ],int n) { struct btnode *p, *q, *bt; int k; bt=NULL; for ( k=0;kn;k++) { p=(struct btnode *) malloc ( sizeof (struct btnode ); //新接点 p-d=a[k];p-lchild=NULL; p-rchild=NULL; q=bt; if (q==NULL) bt=p; //如果二叉排序树为空 else //如果二叉排序树不为空 { while ((q-lchild!=p)(q-rchild!=p)) //找到叶子接点 { if (a[k] q-d) //插入到左子树 { if (q-lchild!=NULL) q=q-lchild; else q-lchild=p; } else //插入到右子树 { if (q-rchild!=NULL) q=q-rchild; else q-rchild=p; } } } } return (bt) }; 若给定值等于根结点的关键字，则查找成功； 若给定值小于根结点的关键字，则继续在左子树上进行查找； 若给定值大于根结点的关键字，则继续在右子树上进行查找。 否则， 若二叉排序树为空，则查找不成功； 三、二叉排序树的查找算法 §7.4 二叉排序树查找 50 30 80 20 90 85 40 35 88 32 例如: 二叉排序树 查找关键字 == 50 , 50 50 35 , 50 30 40 35 50 90 , 50 80 90 95 §7.4 二叉排序树查找 从上述查找过程可见， 在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; 或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 ——查找成功 ——查找不成功 §7.4 二叉排序树查找 struct btnode *bstserch (struct btnode *bt, ET x) // 返回被查找值x 所在接点的存储地址 { struct btnode *p; p=bt