数据结构与程序设计(王丽苹)26平衡二分查找树.pptVIP

*数据结构与程序设计*10.3P463

BuildingaBalancedBinarySearchTree

Problem:Startwithanorderedlistandbuilditsentriesintoabinarysearchtreethatisnearlybalanced(“bushy”)[近似平衡的树].BOOKP463FIGURE10.12*数据结构与程序设计*10.3

BuildingaBalancedBinarySearchTreeIfthenodesofacompletebinarytreearelabeledininordersequence,startingwith1,theneachnodeisexactlyasmanylevelsabovetheleavesasthehighestpowerof2thatdividesitslabel.BOOKP464FIGURE10.13X%24=0X%23=0X%22=0*数据结构与程序设计*10.3.1

GettingStarted插入一个节点时的方法讨论：(1)判断该节点位于的层数。X%2k=0，K为满足条件的最大值。在10.3节，层数从叶子节点开始计算。叶子节点位第0层。(2)节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，左孩子为空。节点如果为非叶子节点，找到k-1层的最后一个节点为左孩子。(3)关于增加节点的父节点判断，如果K+1层存在，K+1层的最后一个节点的右孩子为空，当前点为K+1最后一个节点的右孩子。课堂练习：请写出按照这种方法插入10个节点后，二叉查找树的结构。*数据结构与程序设计*10.3.1

GettingStarted插入21个节点后的结果。完成插入操作的关键，记住每一层最后一个节点的位置（指针）。Toestablishfuturelinks,wemustrememberpointerstoonenodeoneachlevel,thelastnodeprocessedonthatlevel.为了完成插入操作，引入一个辅助的结构：ListBinary_nodeentry*last_node;last_node为List的对象，其中的每一个元素用来记录插入过程中每一个层最后一个节点的指针。last_node的第0个元素初始化为空，叶子节点层记录在last_node的第1个元素中，依次类推。建立过程分析：*数据结构与程序设计*问题：在插入最后一个节点之后，一棵二叉查找树是否就建立成功了？否，某些节点的右指针的值可能不正确，需要调整后才能生成一棵树。如右图，21个节点插入之后，16，20号节点的右孩子没有初始化成功。原因是：如果只插入21个节点，在16号和20号之间将出现断层。在最后一个节点插入成功之后，需要进行右孩子的处理：方法：从最高层n依次向叶子节点方向查找，如果当前第k层的最后一个节点node的右孩子为空。依次查找第K-1层到1层的最后一个节点，如果当前层i的最后一个节点比K层的最后一个节点node大，则找到它的右孩子。继续从第i层向第3层有哪些信誉好的足球投注网站，处理右孩子的链接。直到有哪些信誉好的足球投注网站到第3层为止。（叶子节点为第1层）BuildableTree的构建方法Step1，从有序序列中依次取出每个节点，按照BuildableTree的构建方法在树中插入该节点。Step2，全部节点插入成功之后，分析每层最后一个节点的右孩子是否链接成功，依次处理每一层右孩子的连接。Step3，右孩子的链接处理之后，获取当前二叉查找树的根，构建结束。当前二叉查找树根的地址存放于last_node的最后一个元素中。10.3.2Declarationsandthemainfunction

templateclassRecordclassBuildable_tree:publicSearch_treeRecord{public: Error_codebuild_tree(constListRecordsupply/*in*/);//构建二叉查找树，supply为有序元素的组合。private://Addauxiliaryfunctionprototypeshere. voidbuild_insert(intcount,constRecordnew_data,L