《(完整word版)特殊二叉树.doc》由会员分享，可在线阅读，更多相关《(完整word版)特殊二叉树.doc（25页珍藏版）》请在金锄头文库上搜索。
1、(完整word版)特殊二叉树 第6章 特殊二叉树6.1 二叉搜索树6.1。1 二叉搜索的定义 二叉搜索树（Binary Sort Tree）又称二叉排序树(Binany Search Tree），它或者是一棵空树，或者是一棵具有如下特性的非空二叉树： (1） 若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字; (2) 若它的右子树非空，则右子树上所有结点的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字； (3） 左、右子树本身又各是一棵二叉搜索树。 在树中当每个结点的元素类型为简单类型时，则结点的关键字就是该结点的值，当每个结点的元素类型为记录类型时
2、，则结点的关键字为该结点的某一个域的值。 对搜索树进行中序遍历得到的结点序列是一个有序序列。 231274521530632618 该图的中序遍历得到的结点序列是： 12,15，18，23,26，30,52，63，74 6。1。2 二叉搜索树的抽象数据类型 搜索树的抽象数据类型中的数据部分：是具有链接存储结构;操作部分除了已经讨论过的对一般树的操作外，还具有查找、更新、插入和删除元素的操作。假定搜索树中的结点类型为BTreeNode,指向树的根结点指针为BST，则对搜索树BST的查找、更新、插入和删除元素的操作定义如下： int Find(BTreeNode BST, ElemType ite
3、m)；/从搜索树中查找等于给定值item的元素，若查找成功则返回真，并由item返回该元素的值，否则返回假; int Update(BTreeNode * BST，const ElemType &item）； / 从二叉搜索树中查找等于给定值item的元素,若查找成功则用item的值重写该元素的值并返回真,否则返回假； void lnsert（BTreeNode *&BST,const ElemType item)；/ 按item的大小向搜索树中插入一个元素item，使得插入后仍是一棵搜索树； int Delete（BTreeNode *&BST, const ElemType &item)
4、/ 从二叉搜索树中删除值为item的第一个结点， 若删除成功则返回1, 否则返回0； 下面分别对这四种运算进行讨论.6。1。3 二叉搜索树的运算1. 查找查找等于给定值item的元素的过程为：若搜索树为空，则表明查找失败，应返回空指针；若给定值 item 等于根结点的值,则表明查找成功，应由变参（即引用参数)带回根结点的值并返回1；若给定值 item 小于根结点的值，则继续在根的左子树中查找；若给定值 item 大于根结点的值，则继续在根的右子树中查找。这是一个递归的查找过程.例子：在下图中查找值为18的结点（是成功,能找到）；在下图中查找值为48的结点(是失败，不能找到）.bool Find
5、 （ BTreeNode *BST，ElemType & item) /从搜索树中查找等于给定值 item 的元素 if （ BST = NULL） return false;/ 查找失败返回 false else if( item = BST- data ) / 查找成功,将元素的值赋给变参item 带回， 并返回真true item = BST-data； return true； else if ( item left，item）；else / 向右子树继续查找 return Find （ BST-right，item）； 由于此递归算法中的递归调用属于末尾递归(即递归调用语句是函数体执
6、行中最后一条可执行语句）的调用。每次递归调用返回后不执行任何语句又返回到上一层，因此原先保存在系统堆栈中的信息都是没有用处的。为了避免无效开销在进出系统栈操作上的时间和使用系统栈的空间，可编写出相应的非递归算法如下：bool Find ( BTreeNode *BST，ElemTypeitem) /进行搜索树查找的非递归算法 while （ BST ！= NULL） if ( item = BST- data ) item = BST-data; return true; else if （ item BST-data ） BST=BST-left； else BST=BST-right； r
7、eturn false； 算法的时间复杂性为O（log2n）。 在搜索树上查找比在线性表上进行顺序查找的时间复杂性O(n）要好得多，这正是构造搜索树的优点之一，因此也常把搜索树称为查找树。 2。 更新 二叉搜索树的更新算法与查找算法基本相同，区别主要在于在更新算法中当查找到待更新的元素时，应将item的值赋给该元素.3。 插入 过程为:若搜索树为空，则由 item 元素生成的新结点将作为根结点.若 item 小于根结点的关键字,则新结点将插入到根的左子树上；若 item 大于等于根结点的关键字,则新结点将插入到根的右子树上.这种插入过程是递归的. void Insert （ BTreeNode
8、 *&BST，const ElemType item ） / 向搜索树中插入一个元素item if ( BST = NULL) /把由item元素生成的新结点链接到已找到的插入位置 BTreeNode *p=new BTreeNode； p-data = item； p-left = p-right = NULL； BST =p； else if ( item BST-data ） / 向左子树中插入元素 Insert ( BST-left,item）；else / 向右子树中插入元素 Insert (BST-right,item)； 同搜索树的查找算法一样，此算法也属于末尾递归的调用，所以为
9、了消除末尾递归,可编写非递归算法。首先需要查找插入位置，然后再进行插入。查找插入位置从根结点开始，若根指针为空，则根结点就是新结点的插入位置；若 item 小于根结点的关键字，则沿着根的左指针在左子树上继续查找插入位置;若 item 大于等于根结点的关键字，则沿着根的右指针在右子树上继续查找插入位置；当查找到一个结点（假定由parent指针所指向）的左指针或右指针为空时，则这个空的指针位置就是新元素结点的插入位置。 在进行插入时,若原树为空，则将新结点指针赋给 BST，该新结点就成为树根结点,否则，将新结点赋给 parent 结点的左指针域或右指针域，作为该结点的左孩子或右孩子。void In
10、sert（BTreeNode BST，const ElemType item） / 为插入新元素寻找插入位置，定义指针 t 指向当前待比较的结点,初始指向树根结点；定义指针 parent 指向 t 结点的双亲结点，初始为NULL。 BTreeNode * t=BST，parent=NULL； while ( t! = NULL ） parent=t； if ( item data = item; p-left = p-right=NULL； / 将新结点插人到以引用参数BST为树根指针的搜索树中的确定位置上 if（ parent = NULL) BST=p； else if ( item da
11、ta ) parent -left =p; else parent -right =p； 利用搜索树的插入算法,可以很容易地写出生成一棵具有n个结点的搜索树的算法。设生成搜索树的n个元素由数组提供，算法描述为： void CreateBSTree（BTreeNode &BST，ElemType a，int n ） / 利用数组中的元素建立搜索树的算法 BST=NULL; For （ int i=0；in;i+) Insert （ BST，ai ); 例子：建立搜索树的一组元素为： ( 38，26，62，94，35，50,28，55) 4. 删除 删除的是叶子结点、分支结点，可能破坏原有结点之间
12、的链接关系，需要重新修改指针,使得删除后仍为一棵搜索树。 下面以图63（a） ( P217） 所示的搜索树为例，说明删除结点的操作： 删除叶子结点 只要将其双亲结点链接到它的指针置为空即可。如删除图叶结点A时,把D结点的左指针域置空即可。LWSDPFGMWSDLMAFGP 删除单分支结点 这种单分支结点只有左子树或右子树,也就是说，其后继只 有一个，左孩子或右孩子.删除该结点时,只要将后继指针链接到它所在的链接位置即可。 如删除单分支结点M时，将M的右指针（即指向s结点的指针）赋给L结点的右指针域即可。PFGAMWSLLFGADDSWP删除单分支结点G时，将G的左指针（即指向F结点的指针）赋给D结点的右指针域.WASDLPFFGASDLWP 删除双分支结点 这种删除比较复杂，因为待删除的结点有两个后继指针,需要妥善处理。删除这种结点有两种方法: 一种方法是：首先把它的右子树链接到它的中序前驱结点的右指针域，（因为此中序前驱结点的右指针一定为空）；然后把它的左子树链接到它所在的链接位置。 例如删除双分支结点D。中序遍历为：A, D， F, G, L， M, P, S， W。SLDPFGAMWAFGPMWSL
