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

1、10/22/2021数据结构与程序设计 1数据结构与程序设计(26) 王丽苹 10/22/2021数据结构与程序设计 210.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.1210/22/2021数据结构与程序设计 310.3 building a balanced

2、 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=010/22/2021数据结构与程序设计 410.3.1 getting started

3、插入一个节点时的方法讨论：插入一个节点时的方法讨论：(1) 判断该节点位于的层数。判断该节点位于的层数。x%2k=0 ，k为满足条件的最大值。在为满足条件的最大值。在10.3节，节，层数从叶子节点开始计算。叶子节点位第层数从叶子节点开始计算。叶子节点位第0层。层。(2) 节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，节点的右孩子默认为空（该节点为树中的最大值）。节点如果为叶子节点，左孩子为空。节点如果为非叶子节点，找到左孩子为空。节点如果为非叶子节点，找到k-1层的最后一个节点为左孩子。层的最后一个节点为左孩子。(3) 关于增加节点的父节点判断，如果关于增加节点的父节点判断

4、，如果k+1层存在，层存在，k+1层的最后一个节点的层的最后一个节点的右孩子为空，当前点为右孩子为空，当前点为k+1最后一个节点的右孩子。最后一个节点的右孩子。课堂练习：请写出按照这种方法插课堂练习：请写出按照这种方法插入入10个节点后，二叉查找树的结个节点后，二叉查找树的结构。构。10/22/2021数据结构与程序设计 510.3.1 getting startedn插入21个节点后的结果。完成插入操作的关键，记住每一层最后一个节点的位置（指针）。完成插入操作的关键，记住每一层最后一个节点的位置（指针）。to establish future links, we must remember

5、pointers to one nodeon each level, the last node processed on that level.10/22/2021数据结构与程序设计 6n为了完成插入操作，引入一个辅助的结构：为了完成插入操作，引入一个辅助的结构：nlistbinary _node* last_node;nlast_node为为list的对象，其中的每一个元素用来记录插入过程的对象，其中的每一个元素用来记录插入过程中每一个层最后一个节点的指针。中每一个层最后一个节点的指针。 last_node的第的第0个元素初始个元素初始化为空，叶子节点层记录在化为空，叶子节点层记录在las

6、t_node的第的第1个元素中，依次类推。个元素中，依次类推。10/22/2021数据结构与程序设计 7建立过程分析：建立过程分析：n问题：在插入最后一个节点之后，一棵二叉查找树是问题：在插入最后一个节点之后，一棵二叉查找树是否就建立成功了？否就建立成功了？n否，某些节点的右指针的值可能不正确，需要调整后才能生否，某些节点的右指针的值可能不正确，需要调整后才能生成一棵树成一棵树。如右图，如右图，21个节个节点插入之后，点插入之后，16，20号节点的右孩号节点的右孩子没有初始化成子没有初始化成功。功。原因是：如果只原因是：如果只插入插入21个节点，个节点，在在16号和号和20号号之间将出现断层。

7、之间将出现断层。10/22/2021数据结构与程序设计 8在最后一个节点插入成功之后，需要进行右孩子在最后一个节点插入成功之后，需要进行右孩子的处理：的处理：n方法：方法：从最高层从最高层n依次向叶子节点方向查找，如果当前第依次向叶子节点方向查找，如果当前第k层的最后一个节点层的最后一个节点node的右孩子为空。的右孩子为空。n依次查找第依次查找第k-1层到层到1层的最后一个节点，如果当前层层的最后一个节点，如果当前层i的最后一个节的最后一个节点比点比k层的最后一个节点层的最后一个节点node大，则找到它的右孩子。大，则找到它的右孩子。n继续从第继续从第i层向第层向第3层搜索，处理右孩子的链接

8、。直到搜索到第层搜索，处理右孩子的链接。直到搜索到第3层为层为止。（叶子节点为第止。（叶子节点为第1层）层）10/22/2021数据结构与程序设计 9buildable tree的构建方法nstep1，从有序序列中依次取出每个节点，按照，从有序序列中依次取出每个节点，按照buildable tree的构建方法在树中插入该节点。的构建方法在树中插入该节点。nstep2，全部节点插入成功之后，分析每层最后一个节点，全部节点插入成功之后，分析每层最后一个节点的右孩子是否链接成功，依次处理每一层右孩子的连接。的右孩子是否链接成功，依次处理每一层右孩子的连接。nstep3，右孩子的链接处理之后，获取当前

9、二叉查找树的，右孩子的链接处理之后，获取当前二叉查找树的根，构建结束。根，构建结束。n当前二叉查找树根的地址存放于当前二叉查找树根的地址存放于last_node的最后一个元素中。的最后一个元素中。10/22/2021数据结构与程序设计 1010.3.2 declarations and the main functiontemplate class buildable_tree: public search_tree public:error_code build_tree(const list &supply/*in*/); /构建二叉查找树，构建二叉查找树，supply为有序元素的组合。为

10、有序元素的组合。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);

11、 /插入结束，获得当前二叉查找树的根节点指针。插入结束，获得当前二叉查找树的根节点指针。void connect_trees(const list binary_node* &last_node); /根据根据last_node中的信息调整每一层最后一个节点中，右孩子的信息。中的信息调整每一层最后一个节点中，右孩子的信息。;10/22/2021数据结构与程序设计 11template error_code buildable_tree : build_tree(const list &supply)error_code ordered_data = success;/remove it for

12、 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)

13、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.10/22/2021数据结构与程序设计 12template void buildable_tree : build_insert(int count

14、, 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 las

15、t nodelast_node.retrieve(level - 1, next_node-left);if (last_node.size( ) right = null)parent-right = next_node; /更新父节点更新父节点10/22/2021数据结构与程序设计 13building a balanced binary search treelist binary_node* &last_nodenullp1nullp2p1nullp2p3null10/22/2021数据结构与程序设计 14building a balanced binary search treep4

16、68 10.14list binary_node* &last_nodep4p2p3nullp4p2p5null10/22/2021数据结构与程序设计 15template 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

17、 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 找到根节点找到根节点10/22/2021数据结构与程序设计 16处理右孩子节点处理右孩子节点10/22/2021数据结

18、构与程序设计 17template 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.

19、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 &

20、low_node-data data);high_node-right = low_node;high_level = low_level; book p46910/22/2021数据结构与程序设计 18building 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;co

21、utpreorder: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

22、 2 5 7 6 4 9 11 10 13 15 14 12 8 17 19 18 21 20 1610/22/2021数据结构与程序设计 19building 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;

23、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 1610/22/2021数据结

24、构与程序设计 20building a balanced binary search treen目录目录buildable_tree下例程下例程10/22/2021数据结构与程序设计 21c+知识补充知识补充n多态性多态性n当不同的对象收到相同的消息产生不同当不同的对象收到相同的消息产生不同的动作，这种功能称为多态性。的动作，这种功能称为多态性。nc+支持两种多态性：静态编译时的多支持两种多态性：静态编译时的多态性是通过函数重载实现的，运行时的态性是通过函数重载实现的，运行时的多态性则通过虚函数来实现。多态性则通过虚函数来实现。10/22/2021数据结构与程序设计 22c+知识补充知识补充-

25、虚函数虚函数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()co

26、utthis 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

27、is class base: printbase.this is class base: printbase.this is class base: virtual function vprint.this is class derived: virtual function vprint.10/22/2021数据结构与程序设计 24c+知识补充知识补充-虚函数虚函数n对于虚函数，程序在运行时，根据指针对于虚函数，程序在运行时，根据指针p所指向的实际所指向的实际对象，来调用该对象的成员函数。对象，来调用该对象的成员函数。n派生类中的虚函数不再需要关键字派生类中的虚函数不再需要关键字virtual修饰，但函修饰，但函数的原型必须完全匹配在基类中说明的原型，即参数数的原型必须完全匹配在基类中说明的原