数据结构与程序设计(26) 王丽苹 lipingwangsei.ecnu.edu.cn8/24/20241数据结构与程序设计 10.3 P463Building a Balanced Binary Search TreenProblem: Start with an ordered list and build its entries into a binary search tree that is nearly balanced (“bushy”)近似平衡的树.nBOOK P463 FIGURE 10.128/24/20242数据结构与程序设计 10.3 Building a Balanced Binary Search TreenIf 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.nBOOK P464 FIGURE 10.13X%24=0X%23=0X%22=08/24/20243数据结构与程序设计 10.3.1 Getting Started插入一个节点时的方法讨论：插入一个节点时的方法讨论：(1) 判断该节点位于的层数。判断该节点位于的层数。X%2k=0 ，K为满足条件的最大值。在为满足条件的最大值。在10.3节，节，层数从叶子节点开始计算。叶子节点位第层数从叶子节点开始计算。叶子节点位第0层。层。(2) 节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，左孩子为空。节点如果为非叶子节点，找到左孩子为空。节点如果为非叶子节点，找到k-1层的最后一个节点为左孩子。层的最后一个节点为左孩子。(3) 关于增加节点的父节点判断，如果关于增加节点的父节点判断，如果K+1层存在，层存在，K+1层的最后一个节点的右层的最后一个节点的右孩子为空，当前点为孩子为空，当前点为K+1最后一个节点的右孩子。最后一个节点的右孩子。课堂练习：请写出按照这种方法插课堂练习：请写出按照这种方法插入入10个节点后，二叉查找树的结个节点后，二叉查找树的结构。构。8/24/20244数据结构与程序设计 10.3.1 Getting Startedn插入21个节点后的结果。完成插入操作的关键，记住每一层最后一个节点的位置（指针）。完成插入操作的关键，记住每一层最后一个节点的位置（指针）。To establish future links, we must remember pointers to one nodeon each level, the last node processed on that level.8/24/20245数据结构与程序设计 n为了完成插入操作，引入一个辅助的结构：为了完成插入操作，引入一个辅助的结构：nListBinary _node* last_node;nlast_node为为List的对象，其中的每一个元素用来记录插入过程中的对象，其中的每一个元素用来记录插入过程中每一个层最后一个节点的指针。每一个层最后一个节点的指针。 last_node的第的第0个元素初始化为个元素初始化为空，叶子节点层记录在空，叶子节点层记录在last_node的第的第1个元素中，依次类推。个元素中，依次类推。8/24/20246数据结构与程序设计 建立过程分析：建立过程分析：n问题：在插入最后一个节点之后，一棵二叉查找树是问题：在插入最后一个节点之后，一棵二叉查找树是否就建立成功了？否就建立成功了？n否，某些节点的右指针的值可能不正确，需要调整后才能生否，某些节点的右指针的值可能不正确，需要调整后才能生成一棵树成一棵树。如右图，如右图，21个节个节点插入之后，点插入之后，16，20号节点的右号节点的右孩子没有初始化孩子没有初始化成功。成功。原因是：如果只原因是：如果只插入插入21个节点，个节点，在在16号和号和20号号之间将出现断层。之间将出现断层。8/24/20247数据结构与程序设计 在最后一个节点插入成功之后，需要进行右孩子在最后一个节点插入成功之后，需要进行右孩子的处理：的处理：n方法：方法：从最高层从最高层n依次向叶子节点方向查找，如果当前第依次向叶子节点方向查找，如果当前第k层的最后一个节点层的最后一个节点node的右孩子为空。的右孩子为空。n依次查找第依次查找第K-1层到层到1层的最后一个节点，如果当前层层的最后一个节点，如果当前层i的最后一个节的最后一个节点比点比K层的最后一个节点层的最后一个节点node大，则找到它的右孩子。大，则找到它的右孩子。n继续从第继续从第i层向第层向第3层搜索，处理右孩子的链接。直到搜索到第层搜索，处理右孩子的链接。直到搜索到第3层为层为止。（叶子节点为第止。（叶子节点为第1层）层）8/24/20248数据结构与程序设计 Buildable Tree的构建方法nStep1，从有序序列中依次取出每个节点，按照，从有序序列中依次取出每个节点，按照Buildable Tree的构建方法在树中插入该节点。的构建方法在树中插入该节点。nStep2，全部节点插入成功之后，分析每层最后一个节点，全部节点插入成功之后，分析每层最后一个节点的右孩子是否链接成功，依次处理每一层右孩子的连接。的右孩子是否链接成功，依次处理每一层右孩子的连接。nStep3，右孩子的链接处理之后，获取当前二叉查找树的，右孩子的链接处理之后，获取当前二叉查找树的根，构建结束。根，构建结束。n当前二叉查找树根的地址存放于当前二叉查找树根的地址存放于last_node的最后一个元素中。的最后一个元素中。8/24/20249数据结构与程序设计 10.3.2 Declarations and the main functiontemplate class Buildable_tree: public Search_tree public:Error_code build_tree(const List &supply/*in*/); /构建二叉查找树，构建二叉查找树，supply为有序元素的组合。为有序元素的组合。private: / Add auxiliary function prototypes here.void build_insert(int count, const Record &new_data, List Binary_node* &last_node); /count，插入节点的编号；，插入节点的编号； new_data插入信息。插入信息。 / last_node 记录当前二叉查找树的每一层的最后一个节点的信息。记录当前二叉查找树的每一层的最后一个节点的信息。Binary_node * find_root(List Binary_node* &last_node); /插入结束，获得当前二叉查找树的根节点指针。插入结束，获得当前二叉查找树的根节点指针。void connect_trees(const List Binary_node* &last_node); /根据根据last_node中的信息调整每一层最后一个节点中，右孩子的信息。中的信息调整每一层最后一个节点中，右孩子的信息。;8/24/202410数据结构与程序设计 template Error_code Buildable_tree : build_tree(const List &supply)Error_code ordered_data = success;/remove it for our Binary_tree int count/int count = 0; / number of entries inserted so farRecord x, last_x;List Binary_node * last_node;/ pointers to last nodes on each levelBinary_node *none = NULL;last_node.insert(0, none); / permanently NULL (for children of leaves)while (supply.retrieve(count, x) = success) if (count 0 & x = last_x) ordered_data = fail;break; build_insert(+count, x, last_node);last_x = x; root = find_root(last_node);connect_trees(last_node);return ordered_data; / Report any data-ordering problems back to client.8/24/202411数据结构与程序设计 template void Buildable_tree : build_insert(int count, const Record &new_data,List Binary_node* &last_node)int level; / level of new node above the leaves, counting inclusivelyfor (level = 1; count%2 = 0; level+)count /= 2; / Use count to calculate level of next node .Binary_node*next_node = new Binary_node(new_data),*parent; / one level higher in last nodelast_node.retrieve(level - 1, next_node-left);if (last_node.size( ) right = NULL)parent-right = next_node; /更新父节点更新父节点8/24/202412数据结构与程序设计 Building a Balanced Binary Search TreeList Binary_node* &last_nodenullp1nullp2p1nullp2p3null8/24/202413数据结构与程序设计 Building a Balanced Binary Search TreeP468 10.14List Binary_node* &last_nodep4p2p3nullp4p2p5null8/24/202414数据结构与程序设计 template Binary_node *Buildable_tree : find_root(const List Binary_node* &last_node)/* Pre: The list last node contains pointers to the last node on each occupied level of the binary search tree.Post: A pointer to the root of the newly created binary search tree is returned.Uses: Methods of classList */Binary_node *high_node;last_node.retrieve(last_node.size( ) - 1, high_node);/ Find root in the highest occupied level in last node .return high_node;find_root 找到根节点找到根节点8/24/202415数据结构与程序设计 处理右孩子节点处理右孩子节点8/24/202416数据结构与程序设计 template void Buildable_tree : (const List Binary_node* &last_node)Binary_node*high_node, / from last node with NULL right child*low_node; / candidate for right child of high nodeint high_level = last_node.size( ) - 1, low_level;while (high_level 2) / Nodes on levels 1 and 2 are already OK.last_node.retrieve(high_level, high_node);if (high_node-right != NULL)high_level-; / Search down for highest dangling node.else / Case: undefined right treelow_level = high_level;do / Find the highest entry not in the left subtree. last_node.retrieve(-low_level, low_node); while (low_node != NULL & low_node-data data);high_node-right = low_node;high_level = low_level; Book P4698/24/202417数据结构与程序设计 Building a Balanced Binary Search Treevoid 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 168/24/202418数据结构与程序设计 Building a Balanced Binary Search Treenmytree.remove(Record(4);ncoutAfter remove(Record(4), Tree size is: mytree.size()endl;ncoutPreorder:endl;nmytree.preorder(print);ncoutendl;ncoutinorder:endl;nmytree.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree.postorder(print);ncoutendl;ncin.get();nAfter 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 168/24/202419数据结构与程序设计 Building a Balanced Binary Search Treen目录目录Buildable_tree下例程下例程8/24/202420数据结构与程序设计 C+知识补充知识补充n多态性多态性n当不同的对象收到相同的消息产生不同当不同的对象收到相同的消息产生不同的动作，这种功能称为多态性。的动作，这种功能称为多态性。nC+支持两种多态性：静态编译时的多支持两种多态性：静态编译时的多态性是通过函数重载实现的，运行时的态性是通过函数重载实现的，运行时的多态性则通过虚函数来实现。多态性则通过虚函数来实现。8/24/202421数据结构与程序设计 C+知识补充知识补充-虚函数虚函数nclass basenint a;npublic:n void printbase()coutThis is class base: printbase.n;nvirtual void vprint()coutThis is class base: virtual function vprint.n;n;nclass derived: public basenint b;npublic:nvoid printbase()coutThis is class derived: printbase.n; n/overwrite bases method.nvoid vprint()coutThis is class derived: virtual function vprint.n;nvoid others()coutprintbase();np=&d; /convert from derived * to base * np-printbase();n/not allown/p-others();n/dynamic compilenp=&b;np-vprint();np=&d;np-vprint();nThis 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.8/24/202423数据结构与程序设计 C+知识补充知识补充-虚函数虚函数n对于虚函数，程序在运行时，根据指针对于虚函数，程序在运行时，根据指针P所指向的实际所指向的实际对象，来调用该对象的成员函数。对象，来调用该对象的成员函数。n派生类中的虚函数不再需要关键字派生类中的虚函数不再需要关键字Virtual修饰，但函修饰，但函数的原型必须完全匹配在基类中说明的原型，即参数数的原型必须完全匹配在基类中说明的原型，即参数个数和类型都需一致。个数和类型都需一致。n虚函数必须是所属类的成员函数，不能是友元。虚函数必须是所属类的成员函数，不能是友元。n目录目录AboutClass5下例子程序。下例子程序。8/24/202424数据结构与程序设计 C+知识补充知识补充-纯虚函数纯虚函数n有时，基类不能为虚函数说明一个有意义的定义，可将有时，基类不能为虚函数说明一个有意义的定义，可将其说明为纯虚函数，它的定义留给派生类来做。其说明为纯虚函数，它的定义留给派生类来做。n包含纯虚函数的类称为抽象类，抽象类只能作为基类，包含纯虚函数的类称为抽象类，抽象类只能作为基类，不能说明抽象类的对象。不能说明抽象类的对象。n目录目录AboutClass6下例子程序。下例子程序。8/24/202425数据结构与程序设计 C+知识补充知识补充-纯虚函数纯虚函数nclass basenint a;npublic:nvoid printbase()coutThis is class base: printbase.n;nvirtual void vprint()=0; /纯虚函数纯虚函数n; /抽象类抽象类nclass derived: public basenint b;npublic:nvoid printbase()coutThis is class derived: printbase.n; /overwrite bases method.nvoid vprint()coutThis is class derived: virtual function vprint.n;nvoid others()coutprintbase();n/dynamic compilenp=&d;np-vprint();nThis is class derived: printbase.This is class derived: virtual function vprint.This is class base: printbase.This is class derived: virtual function vprint.8/24/202427数据结构与程序设计