数据结构与程序设计(王丽苹)26平衡二分查找树.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(26),王丽苹,5/27/2023,数据结构与程序设计,2,10.3 P463Building a Balanced Binary Search Tree,Problem:Start with an ordered list and build its entries into a binary search tree that is nearly balanced(“bushy”)近似平衡的树.BOOK P463 FIGURE 10.12,5/27/2023,数据结构与程序设计,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 as 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,5/27/2023,数据结构与程序设计,4,10.3.1 Getting Started,插入一个节点时的方法讨论：(1)判断该节点位于的层数。X%2k=0，K为满足条件的最大值。在10.3节，层数从叶子节点开始计算。叶子节点位第0层。(2)节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，左孩子为空。节点如果为非叶子节点，找到k-1层的最后一个节点为左孩子。(3)关于增加节点的父节点判断，如果K+1层存在，K+1层的最后一个节点的右孩子为空，当前点为K+1最后一个节点的右孩子。,课堂练习：请写出按照这种方法插入10个节点后，二叉查找树的结构。,5/27/2023,数据结构与程序设计,5,10.3.1 Getting Started,插入21个节点后的结果。,完成插入操作的关键，记住每一层最后一个节点的位置（指针）。To establish future links,we must remember pointers to one nodeon each level,the last node processed on that level.,5/27/2023,数据结构与程序设计,6,为了完成插入操作，引入一个辅助的结构：List*last_node;last_node为List的对象，其中的每一个元素用来记录插入过程中每一个层最后一个节点的指针。last_node的第0个元素初始化为空，叶子节点层记录在last_node的第1个元素中，依次类推。,5/27/2023,数据结构与程序设计,7,建立过程分析：,问题：在插入最后一个节点之后，一棵二叉查找树是否就建立成功了？否，某些节点的右指针的值可能不正确，需要调整后才能生成一棵树。,如右图，21个节点插入之后，16，20号节点的右孩子没有初始化成功。原因是：如果只插入21个节点，在16号和20号之间将出现断层。,5/27/2023,数据结构与程序设计,8,在最后一个节点插入成功之后，需要进行右孩子的处理：,方法：从最高层n依次向叶子节点方向查找，如果当前第k层的最后一个节点node的右孩子为空。依次查找第K-1层到1层的最后一个节点，如果当前层i的最后一个节点比K层的最后一个节点node大，则找到它的右孩子。继续从第i层向第3层搜索，处理右孩子的链接。直到搜索到第3层为止。（叶子节点为第1层）,5/27/2023,数据结构与程序设计,9,Buildable Tree的构建方法,Step1，从有序序列中依次取出每个节点，按照Buildable Tree的构建方法在树中插入该节点。Step2，全部节点插入成功之后，分析每层最后一个节点的右孩子是否链接成功，依次处理每一层右孩子的连接。Step3，右孩子的链接处理之后，获取当前二叉查找树的根，构建结束。当前二叉查找树根的地址存放于last_node的最后一个元素中。,5/27/2023,数据结构与程序设计,10,10.3.2 Declarations and the main function,template class Buildable_tree:public Search_tree public:Error_code build_tree(const List,5/27/2023,数据结构与程序设计,11,template Error_code Buildable_tree:build_tree(const List/Report any data-ordering problems back to client.,5/27/2023,数据结构与程序设计,12,template void Buildable_tree:build_insert(int count,const Record/更新父节点,5/27/2023,数据结构与程序设计,13,Building a Balanced Binary Search Tree,List*&last_node,null,p1null,p2p1null,p2p3null,5/27/2023,数据结构与程序设计,14,Building a Balanced Binary Search TreeP468 10.14,List*&last_node,p4p2p3null,p4p2p5null,5/27/2023,数据结构与程序设计,15,template Binary_node*Buildable_tree:find_root(const List*,find_root 找到根节点,5/27/2023,数据结构与程序设计,16,处理右孩子节点,5/27/2023,数据结构与程序设计,17,template void Buildable_tree:(const List*,Book P469,5/27/2023,数据结构与程序设计,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);coutTree size is:mytree.size()endl;coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendl;,Tree size is:21Preorder:16 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15 20 18 17 19 21inorder:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21Postorder:1 3 2 5 7 6 4 9 11 10 13 15 14 12 8 17 19 18 21 20 16,5/27/2023,数据结构与程序设计,19,Building a Balanced Binary Search Tree,mytree.remove(Record(4);coutAfter remove(Record(4),Tree size is:mytree.size()endl;coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendl;cin.get();,After remove(Record(4),Tree size is:20Preorder:16 8 3 2 1 6 5 7 12 10 9 11 14 13 15 20 18 17 19 21inorder:1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21Postorder:1 2 5 7 6 3 9 11 10 13 15 14 12 8 17 19 18 21 20 16,5/27/2023,数据结构与程序设计,20,Building a Balanced Binary Search Tree,目录Buildable_tree下例程,5/27/2023,数据结构与程序设计,21,C+知识补充,多态性当不同的对象收到相同的消息产生不同的动作，这种功能称为多态性。C+支持两种多态性：静态编译时的多态性是通过函数重载实现的，运行时的多态性则通过虚函数来实现。,5/27/2023,数据结构与程序设计,22,C+知识补充-虚函数,class baseint a;public:void printbase()coutThis is class base:printbase.n;virtual void vprint()coutThis is class base:virtual function vprint.n;class derived:public baseint b;public:void printbase()coutThis is class derived:printbase.n;/overwrite bases method.void vprint()coutThis is class derived:virtual function vprint.n;void others()coutOthers of class derived.n;,5/27/2023,数据结构与程序设计,23,C+知识补充-虚函数,void main()base b,*p;derived d;/static compiled.printbase();d.vprint();p=,This is class derived: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.,5/27/2023,数据结构与程序设计,24,C+知识补充-虚函数,对于虚函数，程序在运行时，根据指针P所指向的实际对象，来调用该对象的成员函数。派生类中的虚函数不再需要关键字Virtual修饰，但函数的原型必须完全匹配在基类中说明的原型，即参数个数和类型都需一致。虚函数必须是所属类的成员函数，不能是友元。目录AboutClass5下例子程序。,5/27/2023,数据结构与程序设计,25,C+知识补充-纯虚函数,有时，基类不能为虚函数说明一个有意义的定义，可将其说明为纯虚函数，它的定义留给派生类来做。包含纯虚函数的类称为抽象类，抽象类只能作为基类，不能说明抽象类的对象。目录AboutClass6下例子程序。,5/27/2023,数据结构与程序设计,26,C+知识补充-纯虚函数,class baseint a;public:void printbase()coutThis is class base:printbase.n;virtual void vprint()=0;/纯虚函数;/抽象类class derived:public baseint b;public:void printbase()coutThis is class derived:printbase.n;/overwrite bases method.void vprint()coutThis is class derived:virtual function vprint.n;void others()coutOthers of class derived.n;,5/27/2023,数据结构与程序设计,27,C+知识补充-纯虚函数,void main()/not allowed 不能说明抽象类的对象/base b;base*p;/OKderived d;/static compiled.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.,
