數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計王麗蘋26平衡二分查找樹

1、10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(26) 王麗蘋 10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 410.3.1 getting started

3、插入一個節(jié)點時的方法討論：插入一個節(jié)點時的方法討論：(1) 判斷該節(jié)點位于的層數(shù)。判斷該節(jié)點位于的層數(shù)。x%2k=0 ，k為滿足條件的最大值。在為滿足條件的最大值。在10.3節(jié)，節(jié)，層數(shù)從葉子節(jié)點開始計算。葉子節(jié)點位第層數(shù)從葉子節(jié)點開始計算。葉子節(jié)點位第0層。層。(2) 節(jié)點的右孩子默認(rèn)為空（該節(jié)點為樹中的最大值）。節(jié)點如果為葉子節(jié)點，節(jié)點的右孩子默認(rèn)為空（該節(jié)點為樹中的最大值）。節(jié)點如果為葉子節(jié)點，左孩子為空。節(jié)點如果為非葉子節(jié)點，找到左孩子為空。節(jié)點如果為非葉子節(jié)點，找到k-1層的最后一個節(jié)點為左孩子。層的最后一個節(jié)點為左孩子。(3) 關(guān)于增加節(jié)點的父節(jié)點判斷，如果關(guān)于增加節(jié)點的父節(jié)點判斷

4、，如果k+1層存在，層存在，k+1層的最后一個節(jié)點的層的最后一個節(jié)點的右孩子為空，當(dāng)前點為右孩子為空，當(dāng)前點為k+1最后一個節(jié)點的右孩子。最后一個節(jié)點的右孩子。課堂練習(xí)：請寫出按照這種方法插課堂練習(xí)：請寫出按照這種方法插入入10個節(jié)點后，二叉查找樹的結(jié)個節(jié)點后，二叉查找樹的結(jié)構(gòu)。構(gòu)。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 510.3.1 getting startedn插入21個節(jié)點后的結(jié)果。完成插入操作的關(guān)鍵，記住每一層最后一個節(jié)點的位置（指針）。完成插入操作的關(guān)鍵，記住每一層最后一個節(jié)點的位置（指針）。to establish future links, we must remember

5、pointers to one nodeon each level, the last node processed on that level.10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 6n為了完成插入操作，引入一個輔助的結(jié)構(gòu)：為了完成插入操作，引入一個輔助的結(jié)構(gòu)：nlistbinary _node* last_node;nlast_node為為list的對象，其中的每一個元素用來記錄插入過程的對象，其中的每一個元素用來記錄插入過程中每一個層最后一個節(jié)點的指針。中每一個層最后一個節(jié)點的指針。 last_node的第的第0個元素初始個元素初始化為空，葉子節(jié)點層記錄在化為空，葉子節(jié)點層記錄在las

6、t_node的第的第1個元素中，依次類推。個元素中，依次類推。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 7建立過程分析：建立過程分析：n問題：在插入最后一個節(jié)點之后，一棵二叉查找樹是問題：在插入最后一個節(jié)點之后，一棵二叉查找樹是否就建立成功了？否就建立成功了？n否，某些節(jié)點的右指針的值可能不正確，需要調(diào)整后才能生否，某些節(jié)點的右指針的值可能不正確，需要調(diào)整后才能生成一棵樹成一棵樹。如右圖，如右圖，21個節(jié)個節(jié)點插入之后，點插入之后，16，20號節(jié)點的右孩號節(jié)點的右孩子沒有初始化成子沒有初始化成功。功。原因是：如果只原因是：如果只插入插入21個節(jié)點，個節(jié)點，在在16號和號和20號號之間將出現(xiàn)斷層。

7、之間將出現(xiàn)斷層。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 8在最后一個節(jié)點插入成功之后，需要進行右孩子在最后一個節(jié)點插入成功之后，需要進行右孩子的處理：的處理：n方法：方法：從最高層從最高層n依次向葉子節(jié)點方向查找，如果當(dāng)前第依次向葉子節(jié)點方向查找，如果當(dāng)前第k層的最后一個節(jié)點層的最后一個節(jié)點node的右孩子為空。的右孩子為空。n依次查找第依次查找第k-1層到層到1層的最后一個節(jié)點，如果當(dāng)前層層的最后一個節(jié)點，如果當(dāng)前層i的最后一個節(jié)的最后一個節(jié)點比點比k層的最后一個節(jié)點層的最后一個節(jié)點node大，則找到它的右孩子。大，則找到它的右孩子。n繼續(xù)從第繼續(xù)從第i層向第層向第3層搜索，處理右孩子的鏈接

8、。直到搜索到第層搜索，處理右孩子的鏈接。直到搜索到第3層為層為止。（葉子節(jié)點為第止。（葉子節(jié)點為第1層）層）10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 9buildable tree的構(gòu)建方法nstep1，從有序序列中依次取出每個節(jié)點，按照，從有序序列中依次取出每個節(jié)點，按照buildable tree的構(gòu)建方法在樹中插入該節(jié)點。的構(gòu)建方法在樹中插入該節(jié)點。nstep2，全部節(jié)點插入成功之后，分析每層最后一個節(jié)點，全部節(jié)點插入成功之后，分析每層最后一個節(jié)點的右孩子是否鏈接成功，依次處理每一層右孩子的連接。的右孩子是否鏈接成功，依次處理每一層右孩子的連接。nstep3，右孩子的鏈接處理之后，獲取當(dāng)前

9、二叉查找樹的，右孩子的鏈接處理之后，獲取當(dāng)前二叉查找樹的根，構(gòu)建結(jié)束。根，構(gòu)建結(jié)束。n當(dāng)前二叉查找樹根的地址存放于當(dāng)前二叉查找樹根的地址存放于last_node的最后一個元素中。的最后一個元素中。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 1010.3.2 declarations and the main functiontemplate class buildable_tree: public search_tree public:error_code build_tree(const list &supply/*in*/); /構(gòu)建二叉查找樹，構(gòu)建二叉查找樹，supply為有序元素的組合。為

10、有序元素的組合。private: / add auxiliary function prototypes here.void build_insert(int count, const record &new_data, list binary_node* &last_node); /count，插入節(jié)點的編號；，插入節(jié)點的編號； new_data插入信息。插入信息。 / last_node 記錄當(dāng)前二叉查找樹的每一層的最后一個節(jié)點的信息。記錄當(dāng)前二叉查找樹的每一層的最后一個節(jié)點的信息。binary_node * find_root(list binary_node* &last_node);

11、 /插入結(jié)束，獲得當(dāng)前二叉查找樹的根節(jié)點指針。插入結(jié)束，獲得當(dāng)前二叉查找樹的根節(jié)點指針。void connect_trees(const list binary_node* &last_node); /根據(jù)根據(jù)last_node中的信息調(diào)整每一層最后一個節(jié)點中，右孩子的信息。中的信息調(diào)整每一層最后一個節(jié)點中，右孩子的信息。;10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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; /更新父節(jié)點更新父節(jié)點10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 13building a balanced binary search treelist binary_node* &last_nodenullp1nullp2p1nullp2p3null10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 14building a balanced binary search treep4

16、68 10.14list binary_node* &last_nodep4p2p3nullp4p2p5null10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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 找到根節(jié)點找到根節(jié)點10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 16處理右孩子節(jié)點處理右孩子節(jié)點10/22/2021數(shù)據(jù)結(jié)

18、構(gòu)與程序設(shè)計 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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 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數(shù)據(jù)結(jié)

24、構(gòu)與程序設(shè)計 20building a balanced binary search treen目錄目錄buildable_tree下例程下例程10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 21c+知識補充知識補充n多態(tài)性多態(tài)性n當(dāng)不同的對象收到相同的消息產(chǎn)生不同當(dāng)不同的對象收到相同的消息產(chǎn)生不同的動作，這種功能稱為多態(tài)性。的動作，這種功能稱為多態(tài)性。nc+支持兩種多態(tài)性：靜態(tài)編譯時的多支持兩種多態(tài)性：靜態(tài)編譯時的多態(tài)性是通過函數(shù)重載實現(xiàn)的，運行時的態(tài)性是通過函數(shù)重載實現(xiàn)的，運行時的多態(tài)性則通過虛函數(shù)來實現(xiàn)。多態(tài)性則通過虛函數(shù)來實現(xiàn)。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 22c+知識補充知識補充-

25、虛函數(shù)虛函數(shù)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數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計 24c+知識補充知識補充-虛函數(shù)虛函數(shù)n對于虛函數(shù)，程序在運行時，根據(jù)指針對于虛函數(shù)，程序在運行時，根據(jù)指針p所指向的實際所指向的實際對象，來調(diào)用該對象的成員函數(shù)。對象，來調(diào)用該對象的成員函數(shù)。n派生類中的虛函數(shù)不再需要關(guān)鍵字派生類中的虛函數(shù)不再需要關(guān)鍵字virtual修飾，但函修飾，但函數(shù)的原型必須完全匹配在基類中說明的原型，即參數(shù)數(shù)的原型必須完全匹配在基類中說明的原