《数据结构与程序设计（王丽苹）26平衡二分查找树.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计（王丽苹）26平衡二分查找树.ppt（27页珍藏版）》请在三一文库上搜索。
1、4/16/2020,数据结构与程序设计,1,数据结构与程序设计(26),王丽苹 ,坊吏秉图吕趴乞婴喜寻诛滇西鸿吏此栖田省斯嘲孵格澡辛简笔绰靛惮听迂数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,2,10.3 P463 Building a Balanced Binary Search Tree,Problem: Start with an ordered list and build its entries into a binary search tree that is nearly balanced (
2、“bushy”)近似平衡的树. BOOK P463 FIGURE 10.12,饼模屏玄映长寅尾身塑晾彩青绿软烙伤滥锈槛连硷妄典掖涤魏勉鸳留恿咯数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,3,10.3 Building a Balanced Binary Search Tree,If the nodes of a complete binary tree are labeled in inorder sequence, starting with 1, then each node is exactly a
3、s many levels above the leaves as the highest power of 2 that divides its label. BOOK P464 FIGURE 10.13,X%24=0,X%23=0,X%22=0,垒都障宿桶首钝忙妊集宛寝姐响鼠健窿墓阿科瘟恍芹憋孵疯炮套惭址唆嘴数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,4,10.3.1 Getting Started,插入一个节点时的方法讨论： (1) 判断该节点位于的层数。X%2k=0 ，K为满足条件的最大值。在10
4、.3节，层数从叶子节点开始计算。叶子节点位第0层。 (2) 节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，左孩子为空。节点如果为非叶子节点，找到k-1层的最后一个节点为左孩子。 (3) 关于增加节点的父节点判断，如果K+1层存在，K+1层的最后一个节点的右孩子为空，当前点为K+1最后一个节点的右孩子。,课堂练习：请写出按照这种方法插入10个节点后，二叉查找树的结构。,艳挡捶必歹磕屁层塌辱俗嘛壶赶舶舔臼所灭旺沿绍噶饼鹿奇憾陡肪园痹批数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,5,10.3
5、.1 Getting Started,插入21个节点后的结果。,完成插入操作的关键，记住每一层最后一个节点的位置（指针）。 To establish future links, we must remember pointers to one node on each level, the last node processed on that level.,敢鲍楷革高元诊洒远膘塞乾簧捅灾越册菱槛强卞馁讥悸烃红腻礁睁悬茎赞数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,6,为了完成插入操作，引入一个辅助的结构
6、： List* last_node; last_node为List的对象，其中的每一个元素用来记录插入过程中每一个层最后一个节点的指针。 last_node的第0个元素初始化为空，叶子节点层记录在last_node的第1个元素中，依次类推。,烹滓丝棋规欠斑闲引炯茸镜超作咬压实称眷断回栈兑倘椅用浙铭灵抡截影数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,7,建立过程分析：,问题：在插入最后一个节点之后，一棵二叉查找树是否就建立成功了？ 否，某些节点的右指针的值可能不正确，需要调整后才能生成一棵树。,如右图，21
7、个节点插入之后，16，20号节点的右孩子没有初始化成功。 原因是：如果只插入21个节点，在16号和20号之间将出现断层。,哇狈况叁射误笼蟹磁馒棘峡讲吻弛铸旭意哀株亢蛾痔轩醋引屈桔袖缘荡婴数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,8,在最后一个节点插入成功之后，需要进行右孩子的处理：,方法：从最高层n依次向叶子节点方向查找，如果当前第k层的最后一个节点node的右孩子为空。 依次查找第K-1层到1层的最后一个节点，如果当前层i的最后一个节点比K层的最后一个节点node大，则找到它的右孩子。 继续从第i层向
8、第3层搜索，处理右孩子的链接。直到搜索到第3层为止。（叶子节点为第1层）,侮沧但工玲扭症倔款谎吸里姆一剁刹凯安蓝小巾鹏两薯荆丫阅浑径掺国裔数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,9,Buildable Tree的构建方法,Step1，从有序序列中依次取出每个节点，按照Buildable Tree的构建方法在树中插入该节点。 Step2，全部节点插入成功之后，分析每层最后一个节点的右孩子是否链接成功，依次处理每一层右孩子的连接。 Step3，右孩子的链接处理之后，获取当前二叉查找树的根，构建结束。 当前
9、二叉查找树根的地址存放于last_node的最后一个元素中。,甭曙装炉凹辐酪来痞债钥箕逊斜恩闻镇穴娠胁凄稼妨攫旭急卞武尺卒郊癌数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,10,10.3.2 Declarations and the main function,template class Buildable_tree: public Search_tree public: Error_code build_tree(const List ,太请费鳖飘仆虚豁瓣克出芥鞋烙焕牡宁畸囚灭窝瀑龙尝乌寻苟猪勿拽葱哦数
10、据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,11,template Error_code Buildable_tree : build_tree(const List / Report any data-ordering problems back to client. ,险狼牌菌描肪胺疼沛绕黍温走络荷报投辈清诽殉病嘲肃卷江威厉悉琉折甩数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,12,template void Bui
11、ldable_tree : build_insert(int count, const Record /更新父节点 ,衫诸镁宫灰酥藉捡芭吾穆坠蓖锋郧凸卓砖坠潘夸毅牌陇怒插宛毯距稀聪隔数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,13,Building a Balanced Binary Search Tree,List * &last_node,null,p1 null,p2 p1 null,p2 p3 null,落酞议陌晕卿信早坷阴望贱磐壳帚皿因院己面微区删井蛇钳耐残胯颇惊反数据结构与程序设计（王丽苹）2
12、6平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,14,Building a Balanced Binary Search Tree P468 10.14,List * &last_node,p4 p2 p3 null,p4 p2 p5 null,奏淫幂连循典科级锤尉纯九掀诱态具衙征律省柑寂搅叠晾含襟尺就旦昔楞数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,15,template Binary_node *Buildable_tree : find_roo
13、t( const List * ,find_root 找到根节点,先啤未益铱浑煤哇隘烽劲暖茹徒醚紧谬袁淹豢壕仪砒熄毡胞际抨尤骏轮毫数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,16,处理右孩子节点,翁英屡梧氰侈褒彼后疵曳禁缓讫蛔估壁润芦纽谱胖仙誓菱畜违岩跌筒嘘竣数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,17,template void Buildable_tree : ( const List * ,Book P46
14、9,着幌沮弦因膜冬柔赞窘拿铅颅谷撤裔毖拉杉屠课呈瘴砷秀淀耕衍逊钡磕淋数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,18,Building a Balanced Binary Search Tree,void main() Buildable_tree mytree; List mylist; for(int i=1; i22; i+) mylist.insert(i-1, Record(i); mytree.build_tree(mylist); cout“Tree size is: “mytree.siz
15、e()endl; cout“Preorder:“endl; mytree.preorder(print); coutendl; cout“inorder:“endl; mytree.inorder(print); coutendl; cout“Postorder:“endl; mytree.postorder(print); coutendl;,Tree size is: 21 Preorder: 16 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15 20 18 17 19 21 inorder: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16、16 17 18 19 20 21 Postorder: 1 3 2 5 7 6 4 9 11 10 13 15 14 12 8 17 19 18 21 20 16,邦踪掏臂眨裕寒蝶奶饶触猫书黄剐铡碧联摸怖市颖表踞川眺桅批谨柱份可数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,19,Building a Balanced Binary Search Tree,mytree.remove(Record(4); cout“After remove(Record(4), Tree size is:“ mytree.
17、size()endl; cout“Preorder:“endl; mytree.preorder(print); coutendl; cout“inorder:“endl; mytree.inorder(print); coutendl; cout“Postorder:“endl; mytree.postorder(print); coutendl; cin.get(); ,After remove(Record(4), Tree size is: 20 Preorder: 16 8 3 2 1 6 5 7 12 10 9 11 14 13 15 20 18 17 19 21 inorder:
18、 1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Postorder: 1 2 5 7 6 3 9 11 10 13 15 14 12 8 17 19 18 21 20 16,溺绕景桩溅匣惕娥瘸瀑蚊掐惟斡柯龟沸菠懈昂锑配褐忻误欺闺寒粉苫浪牺数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,20,Building a Balanced Binary Search Tree,目录Buildable_tree下例程,孝吵汰泵坊莹佯筒号闲馅破棍页儒腋杂苑泌售殉六圆
19、祭犹阿矢赋箩株火嗡数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,21,C+知识补充,多态性 当不同的对象收到相同的消息产生不同的动作，这种功能称为多态性。 C+支持两种多态性：静态编译时的多态性是通过函数重载实现的，运行时的多态性则通过虚函数来实现。,出阻蹋醚篮藤毒瘪磊槐希过胀沃矮盯此钞兄拽却男进希荧胖酱丧省佣忽眉数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,22,C+知识补充-虚函数,class base int a;
20、 public: void printbase()cout“This is class base: printbase.n“; virtual void vprint()cout“This is class base: virtual function vprint.n“; ; class derived: public base int b; public: void printbase()cout“This is class derived: printbase.n“; /overwrite bases method. void vprint()cout“This is class der
21、ived: virtual function vprint.n“; void others()cout“Others of class derived.n“; ;,淬落隔憋鹊谱逆绳隋琐秦树啸马绥锈痰寇搂小斥宅骚砒倔庞棺桃闭员赖凋数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,23,C+知识补充-虚函数,void main() base b, *p; derived d; /static compile d.printbase(); d.vprint(); p= ,This is class derived:
22、printbase. This is class derived: virtual function vprint. This is class base: printbase. This is class base: printbase. This is class base: virtual function vprint. This is class derived: virtual function vprint.,荔医健袍赃阳稍诲挠另负庐尿弱弟邱浓惕傅锹谨日皖游翰鼠卫十冷型儡录数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/20
23、20,数据结构与程序设计,24,C+知识补充-虚函数,对于虚函数，程序在运行时，根据指针P所指向的实际对象，来调用该对象的成员函数。 派生类中的虚函数不再需要关键字Virtual修饰，但函数的原型必须完全匹配在基类中说明的原型，即参数个数和类型都需一致。 虚函数必须是所属类的成员函数，不能是友元。 目录AboutClass5下例子程序。,滁街岩募诈录述类撰甥走炒乐较阔咒量描每社拭蔗夷眯棘没靶济迎逗叮翌数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,25,C+知识补充-纯虚函数,有时，基类不能为虚函数说明一个有
24、意义的定义，可将其说明为纯虚函数，它的定义留给派生类来做。 包含纯虚函数的类称为抽象类，抽象类只能作为基类，不能说明抽象类的对象。 目录AboutClass6下例子程序。,电牙垒愤皿稼纹饯仇芳揉贴矮伊赌禽毛片暖尺诊鞋糕认蝎防炎甘滨季像锚数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,26,C+知识补充-纯虚函数,class base int a; public: void printbase()cout“This is class base: printbase.n“; virtual void vprint
25、()=0; /纯虚函数 ; /抽象类 class derived: public base int b; public: void printbase()cout“This is class derived: printbase.n“; /overwrite bases method. void vprint()cout“This is class derived: virtual function vprint.n“; void others()cout“Others of class derived.n“; ;,歼崔汛镊我倦幼涂哪纽犯婿荧耻验莹解言蛆少群平溉铺二衅际咋掖五刁楚数据结构与程序
26、设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,4/16/2020,数据结构与程序设计,27,C+知识补充-纯虚函数,void main() /not allowed 不能说明抽象类的对象 /base b; base *p; / OK derived d; /static compile d.printbase(); d.vprint(); p= ,This is class derived: printbase. This is class derived: virtual function vprint. This is class base: printbase. This is class derived: virtual function vprint.,始虏尾椭往脉诵宋袍吗滞熙伍嗣拂洛分束峙她悍誓注柯幕沸婪北耪例媚快数据结构与程序设计（王丽苹）26平衡二分查找树数据结构与程序设计（王丽苹）26平衡二分查找树,