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

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

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

4、，如果k+1層存在，層存在，k+1層的最后一個(gè)節(jié)點(diǎn)的層的最后一個(gè)節(jié)點(diǎn)的右孩子為空，當(dāng)前點(diǎn)為右孩子為空，當(dāng)前點(diǎn)為k+1最后一個(gè)節(jié)點(diǎn)的右孩子。最后一個(gè)節(jié)點(diǎn)的右孩子。課堂練習(xí)：請(qǐng)寫出按照這種方法插課堂練習(xí)：請(qǐng)寫出按照這種方法插入入10個(gè)節(jié)點(diǎn)后，二叉查找樹的結(jié)個(gè)節(jié)點(diǎn)后，二叉查找樹的結(jié)構(gòu)。構(gòu)。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 510.3.1 getting startedn插入21個(gè)節(jié)點(diǎn)后的結(jié)果。完成插入操作的關(guān)鍵，記住每一層最后一個(gè)節(jié)點(diǎn)的位置（指針）。完成插入操作的關(guān)鍵，記住每一層最后一個(gè)節(jié)點(diǎn)的位置（指針）。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è)計(jì) 6n為了完成插入操作，引入一個(gè)輔助的結(jié)構(gòu)：為了完成插入操作，引入一個(gè)輔助的結(jié)構(gòu)：nlistbinary _node* last_node;nlast_node為為list的對(duì)象，其中的每一個(gè)元素用來記錄插入過程的對(duì)象，其中的每一個(gè)元素用來記錄插入過程中每一個(gè)層最后一個(gè)節(jié)點(diǎn)的指針。中每一個(gè)層最后一個(gè)節(jié)點(diǎn)的指針。 last_node的第的第0個(gè)元素初始個(gè)元素初始化為空，葉子節(jié)點(diǎn)層記錄在化為空，葉子節(jié)點(diǎn)層記錄在las

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

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

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

9、二叉查找樹的，右孩子的鏈接處理之后，獲取當(dāng)前二叉查找樹的根，構(gòu)建結(jié)束。根，構(gòu)建結(jié)束。n當(dāng)前二叉查找樹根的地址存放于當(dāng)前二叉查找樹根的地址存放于last_node的最后一個(gè)元素中。的最后一個(gè)元素中。10/22/2021數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì) 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é)點(diǎn)的編號(hào)；，插入節(jié)點(diǎn)的編號(hào)； new_data插入信息。插入信息。 / last_node 記錄當(dāng)前二叉查找樹的每一層的最后一個(gè)節(jié)點(diǎn)的信息。記錄當(dāng)前二叉查找樹的每一層的最后一個(gè)節(jié)點(diǎn)的信息。binary_node * find_root(list binary_node* &last_node);

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

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

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

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