二叉树的应用

1、第六章 二叉树的应用讲课教师：白晶计算机应用（专科）专业-数据结构 1、二叉搜索树的定义和性质。2、二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度。 3、二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度。4、二叉搜索树的删除元素的方法。堆的定义和顺序存储结构。5、堆的定义和顺序存储结构。6、堆的插入和删除元素的过程、算法描述及时间复杂度。n二叉搜索树的递归算法与非递归算二叉搜索树的递归算法与非递归算法的转换。法的转换。n堆的插入及插入后的调整过程堆的插入及插入后的调整过程n堆的删除及删除后的调整过程堆的删除及删除后的调整过程定义定义 30155274632

2、3182612n对二叉搜索树BST的操作主要有：查找、更新、插入、删除元素。各操作函数的声明如下：Bool Find(BTreeNode *BST, ElemType & item);Bool Update(BTreeNode *BST, const ElemType & item);Void Insert(BTreeNode *&BST, const ElemType & item);Void Delete(BTreeNode *&BST, const ElemType & item);在二叉搜索树上在二叉搜索树上查找查找等于给定值等于给定值item的元素，的元素，是一个从根结点开始，沿某一

3、个分支逐层向下进行是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程比较判等的过程，其过程为：，其过程为： 如果二叉搜索树为空，则表明查找失败，应如果二叉搜索树为空，则表明查找失败，应返回假；返回假； 若若item等于根结点的值，则表明查找成功，由等于根结点的值，则表明查找成功，由引用参数带回根结点的值并返回真；引用参数带回根结点的值并返回真； 若若item小于根结点的真，则继续在根的左子树小于根结点的真，则继续在根的左子树中查找；中查找； 若若item大于根结点的真，则继续在根的右子树大于根结点的真，则继续在根的右子树中查找。中查找。 这是一个这是一个递归查找递归查找过程。过程。30

4、1552746323121826bool Find (BTreeNode * BST, Elemtype & item)/从二叉搜索树中查找等于给定值item的元素的/递归算法 if (BST = =NULL ) return false; /查找失败 else if (item= =BST-data ) /相等,搜索成功 item= BST-data ; return true; else if (itemdata) /向左子树继续查找 return Find( BST-left, item); else return Find( BST-right, item); /向右子树继续查找/进行

5、二叉搜索树查找的非递归算法bool Find (BstNode * BST, Elemtype & item) while (BST ! =NULL ) if (item= =BST-data ) /相等,搜索成功 item= BST-data ; return true; else if (itemdata) /向左子树查找 BST =BST-left ; else BST= BST-right ; /向右子树查找 return false; 35154550402510203028插入新结点插入新结点28 向二叉搜索树中插入元素向二叉搜索树中插入元素item的过程为：的过程为：n若二叉树为

6、空，则由若二叉树为空，则由item元素生成的新结点将元素生成的新结点将作为根结点插入；作为根结点插入；n若二叉树非空，判断：若二叉树非空，判断： 若若item小于根结点，则将新结点插入到根小于根结点，则将新结点插入到根的左子树上；的左子树上； 若若item大于根结点，则将新结点插入到根大于根结点，则将新结点插入到根的右子树上；的右子树上； 当插入的当插入的item已经存在时，就不需要插入。已经存在时，就不需要插入。这也是一个递归算法。这也是一个递归算法。/向二叉搜索树中插入一个元素的递归算法Void Insert (BTreeNode *& BST, const ElemType& item)

7、 if (BST= NULL ) /空二叉树 BstNode * p = new BstNode ; /创建结点 p-data= item; p-left= p-right= NULL; BST= p; else if (item data ) /向左子树插入 Insert (BST-left, item ); else Insert (BST-left, item ); /向右子树插入 /向二叉搜索树中插入一个元素的非递归算法Void Insert (BTreeNode *& BST, const ElemType& item) / 为插入新元素寻找插入位置，定义指针t指向 /当前待比较的结

8、点，初始指向树根结点，定义 /指针parent指向t 结点的双亲结点，初始为NULL BTreeNode * t =BST, * parent =NULL; while( t != NULL ) parent = t ; if( itemdata) t = t-left ; else t = t-right ; /建立值为item，左、右指针域为空的新结点 BTreeNode * p=new BTreeNode; p- data = item; p- left = p-right =NULL; / 将新结点插入到以引用参数BST为树根针的 / 二叉搜索树中的确定位置上 if( parent =

9、 =NULL) BST =p ; else if (itemdata) parent -left = p ; else parent -right = p ; 383826382662382662943862943526386235 5026943862502826873538625055269435285378651787092345删除23双亲结点指向它的指针去掉537865178709455378651787092345删除45缺右子树, 用左子树顶替5378651787092353788117940923删除78缺左子树, 用右子树顶替5394811709235378811794094

10、5删除78找该结点的中序下的前驱结点填补23655365811794094523定义定义 （a）小根堆（b）大根堆745342353618222520182635604873堆顶结点堆尾结点 链接存储结构：与二叉树的存储结构相同,这里不再赘述。 顺序存储结构:首先，对堆中的所有结点进行编号，让堆中的结点编号从0开始，若堆中有n个结点，则编号范围从0n-1；然后，以编号为下标存储到指定数组的对应元素中。堆的顺序存储结构18 26 35 73 48 600123456789012345678974 53 42 25 36 35 20 18 22182635604873012345745342353

11、618222520堆的运算堆类型定义： struct Heap ElemType heap HeapMaxSize; int size; ; 1、初始化堆 2、清除堆 3、检查一个堆是否为空 4、向堆中插入一个元素向堆中插入一个元素 5、从堆中删除元素从堆中删除元素18263560487350182635604873插入插入 50182635604873插入插入 1515182635604873不再是一个堆不再是一个堆15182635604873插入一个新元素后调整过程15与与18交换交换151826356048731518263560487315与与35交换交换向堆中插入一个元素的过程n新元

12、素插入到堆中最后一个元素的位置（堆尾结点），亦即下标为size的位置。n调整成为一个新堆，调整方法调整方法为：n判断新元素是否小于双亲结点的值，若不小于，就满足堆的性质，不用调整就让它们互换位置；n若小于双亲结点的值 ，就让它们交换位置；n再次判断以新元素是还小于此位置的双结点的值，按上述方法继续调整；直到以新位置的双亲结点为根的子树仍为一个堆或者调整到堆顶为止。/ 向堆中插入一个元素的算法描述：向堆中插入一个元素的算法描述：void InsertHeap(Heap &HBT,const ElemType item) HBT.heapHBT.size=item; / 向堆尾添加新元素 HBT.

13、size+; ElemType x=item; / 将新元素暂存在x中 / 用i指向待调整元素的位置，初始指向堆尾 int i=HBT.size-1; while (i!=0) int j=(i-1)/2; / j指向下标为i的元素的双亲结点 if (x= HBT.heapj) break; / 调整结束，退出循环 HBT.heapi= HBT.heapj; / 双新元素下移 i=j; / 改变调整元素的位置为其双亲位置 HBT.heapi=x;从堆中删除元素的过程n删除堆顶元素并返回；n堆顶元素被删除后，留下的堆顶位置就由堆尾元素来填补；n把新的二叉树调整成为一个新堆/p>

14、32635487360删除删除18后后由由60补位补位2635487360再次调整再次调整60与与48交换交换2635487360调整调整60与与26交换交换删除删除18调整过程从根结点开始：n若树根结点的值大于两个孩子结点中的最小值，就将根结点与具有最小值的孩子结点交换，使根结点的值小于两个孩子结点的值。n原根结点被对调到一个孩子结点的位置后，如果对于以该位置为根的子树又不为堆，需要使新元素向孩子一层调整，如此反复调整下去，直到以调整后的位置为根的子树成为一个堆或调整到叶子结点为止。 从堆中删除堆顶元素的算法描述：从堆中删除堆顶元素的算法描述：ElemType DeleteHeap(Heap

15、 &HBT) / 删除堆顶元素后将它返回，删除后仍要成为 一个堆 / 若为空堆，则显示错误信息并退出运行 if (HBT.size = =0) cerr“Heap null!”endl; exit(1); / 将堆顶元素暂存到temp中以便返回 ElemType temp=HBT.heap0; HBT.size-; / 若删除操作后变成空堆，则返回 if(HBT.size= =0) return temp; / 将待调整的堆尾元素暂存到x中，以便放入最终位置 ElemType x=HBT.heapHBT.size; / 用i指向待调整元素的位置，初始指向堆顶位置 int i=0; / 用j指向i的左孩子位置，初始指向下标为1的位置 int j=2*i+1; / 寻找待调整元素的最终位置，每次使孩子元素上移一层 while(j=HBT.size-1) / 调整到孩子元素为空时止 if ( jHBT.heapj+1) j+; / 若右孩子存在并且较小，就使j指向右孩子 if ( x=HBT.heapj) break; / 若条件成立则调整结束，退出循环 HBT.heapi =HBT.heapj; / 孩子元素上移到双亲位置 i=j; j=2*i+1; / 使i和j分别指向下一层结点 / 把待调整元素放到最终位置 HBT.heapi = x; / 返回原堆顶元素 return temp