二叉樹(shù)和其他樹(shù)

1、第8章 二叉樹(shù)和其他樹(shù)學(xué)習(xí)內(nèi)容m簡(jiǎn)單樹(shù)和二叉樹(shù)q術(shù)語(yǔ)q公式化描述和鏈表描述q遍歷m應(yīng)用q表達(dá)式后綴表示表達(dá)式樹(shù)8.1 樹(shù)m線性表、表：不適合描述層次結(jié)構(gòu)數(shù)據(jù)m祖先后代、上級(jí)下屬、整體部分m樹(shù)結(jié)構(gòu)：模仿自然界中的植物樹(shù)例8-1：家庭關(guān)系例8-2m公司結(jié)構(gòu)例8-3m政府機(jī)構(gòu)例8-4m軟件工程數(shù)據(jù)結(jié)構(gòu)“樹(shù)”m定義：樹(shù)（tree）t是一個(gè)非空的有限元素的集合，一個(gè)特殊的元素稱為根（root），余下的元素（如果有的話）組成t的若干子樹(shù)（subtree）m遞歸！例8-6 家庭關(guān)系例樹(shù)的描述m數(shù)據(jù)集合Joe，Ann，Mary，Mark，Sue，John，Chrismn=7，根為Joe家庭關(guān)系例樹(shù)的描述（續(xù)）

2、m余下的元素qAnn單一元素子樹(shù)qMary，Mark，Sue，根為Mary的子樹(shù)Mark和Sue，均為單元素的子樹(shù)qJohn，Chris，根為John的子樹(shù)Chris 也為單元素子樹(shù)相關(guān)術(shù)語(yǔ)m元素節(jié)點(diǎn)m根節(jié)點(diǎn)與子樹(shù)的根節(jié)點(diǎn)的關(guān)系邊m邊的兩端父母（parent）和孩子（children）相關(guān)術(shù)語(yǔ)（續(xù)）m相同父母的節(jié)點(diǎn)兄弟（sibling）m祖父孫子，祖先后代m葉節(jié)點(diǎn)沒(méi)有孩子的節(jié)點(diǎn)，非葉節(jié)點(diǎn)非終端節(jié)點(diǎn)相關(guān)術(shù)語(yǔ)（續(xù)）m根沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)m層（level）：根1，根的孩子2，.m節(jié)點(diǎn)的度（degree）：孩子數(shù)目，葉0例8-6m公司機(jī)構(gòu)例q公司雇員節(jié)點(diǎn)，總裁根q副總裁總裁的子節(jié)點(diǎn)，總裁副總裁的父節(jié)點(diǎn)q

3、不同副總裁兄弟節(jié)點(diǎn)例8-6 （續(xù)）m政府機(jī)構(gòu)例q聯(lián)邦政府國(guó)防部，教育部，.，稅務(wù)部的父節(jié)點(diǎn)q國(guó)防部的子節(jié)點(diǎn)陸軍、海軍、空軍、海軍陸戰(zhàn)隊(duì)兄弟節(jié)點(diǎn)，葉節(jié)點(diǎn)自由樹(shù)有根樹(shù)有序樹(shù)森林和有序森林m森林（forest）：）：樹(shù)的集合，通常認(rèn)為是有根樹(shù)的集合m有序森林（orchard，ordered forest）：）：有序樹(shù)的有序集合m有根樹(shù)去掉根節(jié)點(diǎn)（有序）森林m（有序）森林添加父節(jié)點(diǎn)有根樹(shù) 森林和有序森林（續(xù)）有根樹(shù)的遞歸定義m有根樹(shù)：包含單一頂點(diǎn)v，稱為樹(shù)的根，和一個(gè)森林F，F(xiàn)的樹(shù)稱為根的子樹(shù)而森林F（可為空）是一個(gè)有根樹(shù)的集合有序樹(shù)的定義m一個(gè)有序樹(shù)T：包含一個(gè)單一節(jié)點(diǎn)v，稱為樹(shù)的根，和一個(gè)有序森林

4、O，O的樹(shù)稱為v的子樹(shù)，表示為T(mén)=v, O有序森林的定義m一個(gè)有序森林O：或者為空集，或包含一個(gè)有序樹(shù)T，稱為有序森林的第一樹(shù)，和另一個(gè)有序森林O（包含有序森林的其它樹(shù)），可表示為O=T, Om有序樹(shù)有序森林：間接遞歸定義有序森林8.2 二叉樹(shù)m定義： 二叉樹(shù)（binary tree）t是有限元素集合：或者為空；或者，有一個(gè)特殊元素根，余下的元素構(gòu)成2個(gè)二叉樹(shù)（可以為空）t的左子樹(shù)和右子樹(shù)二叉樹(shù)和樹(shù)的根本區(qū)別m二叉樹(shù)可以為空樹(shù)不行m二叉樹(shù)每個(gè)節(jié)點(diǎn)都恰好有兩棵子樹(shù)（可以為空）樹(shù)中每個(gè)節(jié)點(diǎn)可有若干子樹(shù)m二叉樹(shù)每個(gè)節(jié)點(diǎn)的子樹(shù)是有序的“左”、“右”樹(shù)的子樹(shù)間是無(wú)序的二叉樹(shù)例遞歸構(gòu)造m空二叉樹(shù)遞歸的停止

5、m單一節(jié)點(diǎn)二叉樹(shù)m兩個(gè)節(jié)點(diǎn)：不同！不能表示為二叉樹(shù)例遞歸構(gòu)造（續(xù)）m三個(gè)節(jié)點(diǎn)q根左子樹(shù)(2)右子樹(shù)(0)、11、02m類(lèi)似方式，可構(gòu)造更大的二叉樹(shù)二叉樹(shù)例：表達(dá)式樹(shù)ma*b + c/dma+b+c+dm(-a+(x+y)/(+b*(c*a)8.3 二叉樹(shù)的特性m特性1 包含n (n0)個(gè)節(jié)點(diǎn)的二叉樹(shù)邊數(shù)為n-1證明二叉樹(shù)中每個(gè)節(jié)點(diǎn)（除根節(jié)點(diǎn)，共n-1個(gè)節(jié)點(diǎn)） 有且只有一個(gè)父節(jié)點(diǎn)每個(gè)子節(jié)點(diǎn)與父節(jié)點(diǎn)間有且只有一條邊邊數(shù)為n-1特性2m二叉樹(shù)的高度（height）（深度，depth）：二叉樹(shù)的層數(shù)m特性2 若二叉樹(shù)的高度為h，h0，則它最少有h個(gè)節(jié)點(diǎn)，最多有2h-1個(gè)節(jié)點(diǎn)特性2的證明證明每層最少要有

6、1個(gè)節(jié)點(diǎn)節(jié)點(diǎn)數(shù)最少為h每個(gè)節(jié)點(diǎn)最多有2個(gè)子節(jié)點(diǎn)則第i層節(jié)點(diǎn)最多為2i-1個(gè)，i0節(jié)點(diǎn)的總數(shù)不會(huì)超過(guò)12211hhii特性3m特性3 包含n個(gè)節(jié)點(diǎn)的二叉樹(shù)的高度最大為n，最小為證明每層至少一個(gè)元素高度不會(huì)超過(guò)n由特性2，可知高度為h，節(jié)點(diǎn)最多2h-1即n2h-1hlog2(n+1)且h是整數(shù)) 1(log2n) 1(log2nh滿二叉樹(shù)（full binary tree ）m高度為h，節(jié)點(diǎn)數(shù)2h-1完全二叉樹(shù)(complete binary tree)m高度為h 的滿二叉樹(shù)中節(jié)點(diǎn)按從上到下，從左到右的順序從1到2h-1進(jìn)行編號(hào)m從中刪除k個(gè)節(jié)點(diǎn)，編號(hào)為2h-i, 1ikm即為完全二叉樹(shù)，深度為)

7、 1(log2n特性4m特性4 設(shè)完全二叉樹(shù)中一節(jié)點(diǎn)的序號(hào)為i, 1in。則有以下關(guān)系成立：m當(dāng)i = 1時(shí)，該元素為二叉樹(shù)的根。若i 1，則該元素父節(jié)點(diǎn)的編號(hào)為1)當(dāng)2in時(shí)，該元素?zé)o左孩子。否則，其左孩子的編號(hào)為2i2/ i特性4（續(xù)）m若2i + 1n，該元素?zé)o右孩子。否則，其右孩子編號(hào)為2i + 1證明通過(guò)對(duì)i 進(jìn)行歸納即可得證8.4 二叉樹(shù)描述m8.4.1 公式化描述利用特性4q普通二叉樹(shù)缺少部分節(jié)點(diǎn)的完全二叉樹(shù)公式化描述m數(shù)組位置節(jié)點(diǎn)編號(hào)m父子節(jié)點(diǎn)關(guān)系特性4公式化描述mn層二叉樹(shù)2n-1數(shù)組保存，可能空間浪費(fèi)！8.4.2 鏈表描述m樹(shù)節(jié)點(diǎn)節(jié)點(diǎn)類(lèi)對(duì)象q數(shù)據(jù)域、LeftChild、Ri

8、ghtChildqn-1條邊2n-(n-1)=n+1個(gè)空指針BinaryTreeNode類(lèi)template class BinaryTreeNode friend void Visit(BinaryTreeNode *); friend void InOrder(BinaryTreeNode *); friend void PreOrder(BinaryTreeNode *); friend void PostOrder(BinaryTreeNode *); friend void LevelOrder(BinaryTreeNode *); friend void main(void); Bi

9、naryTreeNode類(lèi)public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTreeNode(const T& e) data = e; LeftChild = RightChild = 0; BinaryTreeNode(const T& e, BinaryTreeNode *l, BinaryTreeNode *r) data = e; LeftChild = l; RightChild = r; private: T data; BinaryTreeNode *LeftChild, / left subt

10、ree *RightChild; / right subtree;二叉樹(shù)與有序森林的對(duì)應(yīng)關(guān)系m二叉樹(shù)的另一種定義：一個(gè)二叉樹(shù)B或者是空集，或者包含一個(gè)根v和兩個(gè)二叉樹(shù)B1和B2，可表示為B=v, B1, B2m定理11.1：令S為任意頂點(diǎn)集合，則以S為頂點(diǎn)集合的有序森林集合和以S為頂點(diǎn)集合的二叉樹(shù)集合之間存在一一映射f任一有序森林均有任一二叉樹(shù)與之對(duì)應(yīng)證明（數(shù)學(xué)歸納法）對(duì)空集S，有序森林和二叉樹(shù)均為空，映射關(guān)系f()=，命題成立假定對(duì)所有|S|n，命題成立，考慮|S|=n若森林O不為空O=T, O2 ，T第一樹(shù)為有序樹(shù)，O2為另一森林（森林定義）1對(duì)應(yīng)關(guān)系的證明（續(xù)）另有T=v, O1 ，v為

11、頂點(diǎn)，O1為另一森林（有序樹(shù)定義）2由1、2O=v, O1, O2O1和O2節(jié)點(diǎn)數(shù)必然 n存在一一對(duì)應(yīng)的二叉樹(shù)f(O1)和f(O2)定義：f(O)=f(v, O1, O2)=v, f(O1), f(O2)因此，f(O)表示一棵二叉樹(shù)，對(duì)|S|=n命題成立命題得證用二叉樹(shù)類(lèi)型描述樹(shù)（森林）mLeftChild指向第一個(gè)孩子節(jié)點(diǎn)mRightChild指向下一個(gè)兄弟節(jié)點(diǎn)m顯然，遍歷函數(shù)應(yīng)修改用二叉樹(shù)類(lèi)型描述樹(shù)（森林）用二叉樹(shù)類(lèi)型描述樹(shù)（森林）8.5 二叉樹(shù)常用操作m確定高度m確定節(jié)點(diǎn)數(shù)目m復(fù)制m顯示或打印二叉樹(shù)m確定兩棵二叉樹(shù)是否一樣二叉樹(shù)常用操作（續(xù)）m刪除整棵樹(shù)m若為數(shù)學(xué)表達(dá)式樹(shù)，計(jì)算該數(shù)學(xué)表達(dá)

12、式m若為數(shù)學(xué)表達(dá)式樹(shù)，給出對(duì)應(yīng)的帶括號(hào)的表達(dá)式m都可通過(guò)二叉樹(shù)遍歷（按某種順序訪問(wèn)所有節(jié)點(diǎn)，且只訪問(wèn)一次）來(lái)完成8.6 二叉樹(shù)遍歷m遍歷順序q訪問(wèn)根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)的順序q左右子樹(shù)的訪問(wèn)（遍歷）？遞歸！m可能的遍歷順序qV根，L左子樹(shù)，R右子樹(shù)qVLR LVR LRV VRL RVL RLV標(biāo)準(zhǔn)遍歷順序m都是左子樹(shù)先于右子樹(shù)，關(guān)鍵根的訪問(wèn)次序m先序遍歷（preorder）VLRm中序遍歷（inorder）LVRm后序遍歷（postorder）LRV先序遍歷template void PreOrder(BinaryTreeNode *t)/ Preorder traversal of *t.

13、 if (t) Visit(t); / visit tree root PreOrder(t-LeftChild); / do left subtree PreOrder(t-RightChild); / do right subtree 中序遍歷template void InOrder(BinaryTreeNode *t)/ Inorder traversal of *t. if (t) InOrder(t-LeftChild); / do left subtree Visit(t); / visit tree root InOrder(t-RightChild); / do right

14、subtree 后序遍歷template void PostOrder(BinaryTreeNode *t)/ Postorder traversal of *t. if (t) PostOrder(t-LeftChild); / do left subtree PostOrder(t-RightChild); / do right subtree Visit(t); / visit tree root 先序遍歷表達(dá)式樹(shù)+*ab/cd+abcd/+-a+xy*+b*cam前綴表達(dá)式中序遍歷表達(dá)式樹(shù)a*b + c/da+b+c+d-a+x+y/+b*c*am中綴表達(dá)式人類(lèi)習(xí)慣m需加括號(hào)后序遍歷表

15、達(dá)式樹(shù)ab*cd/+ab+c+d+a-xy+b+ca*/m后綴表達(dá)式計(jì)算機(jī)計(jì)算非常方便輸出完全括號(hào)化的中綴表達(dá)式template void Infix(BinaryTreeNode *t)/ Output infix form of expression. if (t) cout LeftChild); / left operand cout data; / operator Infix(t-RightChild); / right operand cout );逐層遍歷（寬度優(yōu)先）m根葉逐層，同層由左至右template void LevelOrder(BinaryTreeNode *t)/

16、 Level-order traversal of *t. LinkedQueueBinaryTreeNode* Q; while (t) Visit(t); / visit t 逐層遍歷（寬度優(yōu)先） / put ts children on queue if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChild) Q.Add(t-RightChild); / get next node to visit try Q.Delete(t); catch (OutOfBounds) return; 最壞情況空間復(fù)雜性O(shè)(n)時(shí)間復(fù)雜性(n)8.7 抽

17、象數(shù)據(jù)類(lèi)型BinaryTree抽象數(shù)據(jù)類(lèi)型BinaryTree實(shí)例元素集合；如果不空，則被劃分為根節(jié)點(diǎn)、左子樹(shù)和右子樹(shù)；每個(gè)子樹(shù)仍是一個(gè)二叉樹(shù)操作Create()：創(chuàng)建一個(gè)空的二叉樹(shù)；IsEmpty：如果二叉樹(shù)為空，則返回true，否則返回falseRoot(x)：取x為根節(jié)點(diǎn)；如果操作失敗，則返回false，否則返回true抽象數(shù)據(jù)類(lèi)型（續(xù)） MakeTree(root，left，right)：創(chuàng)建一個(gè)二叉樹(shù)，root作為根節(jié)點(diǎn)，left作為左子樹(shù)，right作為右子樹(shù)BreakTree(root，left，right)：拆分二叉樹(shù)PreOrder：先序遍歷InOrder：中序遍歷PostO

18、rder：后序遍歷LevelOrder：逐層遍歷8.8 類(lèi)BinaryTreetemplateclass BinaryTree public: BinaryTree() root = 0; BinaryTree(); bool IsEmpty() const return (root) ? false : true); bool Root(T& x) const; void MakeTree(const T& element, BinaryTree& left, BinaryTree& right); void BreakTree(T& element,

19、 BinaryTree& left, BinaryTree& right); void PreOrder(void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root);類(lèi)BinaryTree（續(xù)） void InOrder(void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder(void(*Visit)(BinaryTreeNode *u) PostOrder(Visit, root); void LevelOrder(void(*Visit)(Bin

20、aryTreeNode *u);private: BinaryTreeNode *root; / pointer to root void PreOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void InOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t); void PostOrder(void(*Visit) (BinaryTreeNode *u), BinaryTreeNode *t);獲取根節(jié)點(diǎn)數(shù)據(jù)templatebool BinaryTree:R

21、oot(T& x) const/ Return root data in x. / Return false if no root. if (root) x = root-data; return true; else return false; / no root創(chuàng)建樹(shù)templatevoid BinaryTree:MakeTree(const T& element, BinaryTree& left, BinaryTree& right)/ Combine left, right, and element to make new tree. / left,

22、right, and this must be different trees. / create combined tree root = new BinaryTreeNode (element, left.root, right.root); / deny access from trees left and right left.root = right.root = 0;缺陷：允許MakeTree(e, X, X)且X不為空為什么置為空？不會(huì)造成空懸指針嗎？分裂樹(shù)templatevoid BinaryTree:BreakTree(T& element, BinaryTree&a

23、mp; left, BinaryTree& right)/ left, right, and this must be different trees. / check if empty if (!root) throw BadInput(); / tree empty / break the tree element = root-data; left.root = root-LeftChild; right.root = root-RightChild; delete root; root = 0;與上例相同的道理先序遍歷templatevoid BinaryTree:PreOrd

24、er(void(*Visit)(BinaryTreeNode *u),BinaryTreeNode *t)/ Preorder traversal. if (t) Visit(t); PreOrder(Visit, t-LeftChild); PreOrder(Visit, t-RightChild); 中序遍歷template void BinaryTree:InOrder(void(*Visit)(BinaryTreeNode *u),BinaryTreeNode *t)/ Inorder traversal. if (t) InOrder(Visit, t-LeftChild); Vis

25、it(t); InOrder(Visit, t-RightChild); 后序遍歷template void BinaryTree:PostOrder(void(*Visit)(BinaryTreeNode *u),BinaryTreeNode *t)/ Postorder traversal. if (t) PostOrder(Visit, t-LeftChild); PostOrder(Visit, t-RightChild); Visit(t); 逐層遍歷template void BinaryTree:LevelOrder(void(*Visit)(BinaryTreeNode *u)

26、/ Level-order traversal. LinkedQueueBinaryTreeNode* Q; BinaryTreeNode *t; t = root; while (t) Visit(t); if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChild) Q.Add(t-RightChild); try Q.Delete(t); catch (OutOfBounds) return; 由遍歷順序推導(dǎo)二叉樹(shù)結(jié)構(gòu)m一棵二叉樹(shù)先序遍歷結(jié)果1, 2, 4, 7, 3, 5, 6, 8, 9中序遍歷結(jié)果4, 7, 2, 1, 5, 3, 8,

27、 6, 9能推導(dǎo)出其結(jié)構(gòu)嗎？m可以！第一步1, 2, 4, 7, 3, 5, 6, 8, 94, 7, 2, 1, 5, 3, 8, 6, 9m先序遍歷根左子樹(shù)右子樹(shù)“1”必為根節(jié)點(diǎn)m中序遍歷左子樹(shù)根右子樹(shù)，且1為根節(jié)點(diǎn)4, 7, 2為左子樹(shù)，5, 3, 8, 6, 9為右子樹(shù)下面怎么辦？遞歸！m左子樹(shù)先序遍歷2, 4, 7中序遍歷4, 7, 2m右子樹(shù)先序遍歷3, 5, 6, 8, 9中序?yàn)?, 3, 8, 6, 9m利用相同方法構(gòu)造左、右子樹(shù)，直至列表長(zhǎng)度為0空子樹(shù)，無(wú)需構(gòu)造遍歷順序二叉樹(shù)結(jié)構(gòu)（續(xù)）遍歷順序二叉樹(shù)結(jié)構(gòu)（續(xù)）先序3, 5, 6, 8, 9，中序5, 3, 8, 6, 9遍歷順

28、序二叉樹(shù)結(jié)構(gòu)（續(xù)）先序6, 8, 9中序8, 6, 9使用BinaryTreeint count = 0;BinaryTree a,x,y,z;templatevoid ct(BinaryTreeNode *t) count+;void main(void) y.MakeTree(1,a,a); z.MakeTree(2,a,a); x.MakeTree(3,y,z); y.MakeTree(4,x,a); y.PreOrder(ct); cout count endl;8.9 抽象數(shù)據(jù)類(lèi)型及類(lèi)的擴(kuò)充m增加如下二叉樹(shù)操作：PreOutput()：按前序方式輸出數(shù)據(jù)域InOutput()：按中序

29、方式輸出數(shù)據(jù)域PostOutput()：按后序方式輸出數(shù)據(jù)域LevelOutput()：逐層輸出數(shù)據(jù)域Delete()：刪除一棵二叉樹(shù)，釋放其節(jié)點(diǎn)Height()：返回樹(shù)的高度Size()：返回樹(shù)中節(jié)點(diǎn)數(shù)8.9.1 輸出函數(shù)m私有輔助函數(shù)static void Output(BinaryTreeNode *t) cout data ;m輸出函數(shù) void PreOutput() PreOrder(Output, root); cout endl; void InOutput() InOrder(Output, root); cout endl; void PostOutput() PostOr

30、der(Output, root); cout endl; void LevelOutput() LevelOrder(Output); cout endl;8.9.2 銷(xiāo)毀二叉樹(shù)m刪除所有節(jié)點(diǎn)m后序遍歷：刪除左子樹(shù)、刪除右子樹(shù)、刪除根m輔助函數(shù)刪除單個(gè)節(jié)點(diǎn) static void Free(BinaryTreeNode *t) delete t;m刪除二叉樹(shù)void Delete() PostOrder(Free, root); root = 0;8.9.3 計(jì)算高度m后序遍歷q左子樹(shù)高度、右子樹(shù)高度較大者+1（根節(jié)點(diǎn)）樹(shù)的高度q遞歸公式：h=maxhl, hr + 1遞歸函數(shù)m公共接口in

31、t Height() const return Height(root);計(jì)算高度的遞歸函數(shù)Heighttemplate int BinaryTree:Height(BinaryTreeNode *t) const/ Return height of tree *t. if (!t) return 0; / empty tree int hl = Height(t-LeftChild); / height of left int hr = Height(t-RightChild); / height of right if (hl hr) return +hl; else return +hr

32、;8.9.4 統(tǒng)計(jì)節(jié)點(diǎn)數(shù)目m任意一種遍歷方法，每個(gè)節(jié)點(diǎn)將統(tǒng)計(jì)計(jì)數(shù)加1m私有輔助函數(shù)Add1static void Add1(BinaryTreeNode *t) _count+;m節(jié)點(diǎn)數(shù)統(tǒng)計(jì)函數(shù)int Size() _count = 0; PreOrder(Add1, root); return _count;統(tǒng)計(jì)節(jié)點(diǎn)數(shù)目方法二m利用遞歸公式：s=sl+sr+1template int BinaryTree:Size(BinaryTreeNode *t) const if (!t) return 0; else return Size(t-LeftChild)+Size(t-RightChil

33、d)+1;8.10 應(yīng)用m中綴表達(dá)式后綴表達(dá)式表達(dá)式樹(shù)m后綴（postfix），逆波蘭（reverse Polish）m不需要括號(hào)、優(yōu)先級(jí)，運(yùn)算符順序體現(xiàn)計(jì)算順序m計(jì)算機(jī)運(yùn)算非常方便棧q遇到運(yùn)算數(shù)pushq遇到運(yùn)算符pop棧頂兩個(gè)運(yùn)算數(shù)，運(yùn)算結(jié)果pushq最終，棧中的數(shù)即為最終計(jì)算結(jié)果利用棧計(jì)算后綴表達(dá)式m6*(5+(2+3)*8+3)6 5 2 3 + 8 * + 3 + *m6、5、2、3壓棧($ 6 5 2 3 $)m+：2、3彈出，5壓棧($ 6 5 5 $)m8壓棧： ($ 6 5 5 8 $)m*：5、8彈出，40壓棧 ($ 6 5 40 $)利用棧計(jì)算后綴表達(dá)式（續(xù)）m6 5 2

34、 3 + 8 * + 3 + *m+：5、40彈出，45壓棧 ($ 6 45 $)m3壓棧： ($ 6 45 3 $)m+：45、3彈出，48壓棧($ 6 48 $)m*：6、48彈出，288壓棧($ 288 $)中綴后綴m先看個(gè)例子，a+b*c+(d*e+f)*gm由左至右掃描，利用棧qa，一個(gè)運(yùn)算數(shù)，怎么做？無(wú)論中綴、后綴還是前綴，運(yùn)算對(duì)象的順序都是一樣的，輸出即可($ $)，O: aq+，一個(gè)運(yùn)算符，直接輸出可以嗎？運(yùn)算符應(yīng)在兩個(gè)運(yùn)算對(duì)象之后，顯然不行壓棧：($ + $)，O: aa+b*c+(d*e+f)*g（續(xù)）qb，輸出已輸出兩個(gè)運(yùn)算對(duì)象了，能輸出棧中的“+”嗎？運(yùn)算順序還不確定，

35、或者說(shuō)，“+”的兩個(gè)運(yùn)算對(duì)象是否a、b還不確定，應(yīng)分析后面運(yùn)算符后確定q*如前所述，應(yīng)考慮是否輸出“+” ？不應(yīng)該！ *的優(yōu)先級(jí)高于+ +的運(yùn)算對(duì)象不是a、b，而是a、b*c，未輸出完若*在前（棧頂），+在后，顯然應(yīng)該輸出*因此應(yīng)該壓棧：($ + * $)，O: a b a+b*c+(d*e+f)*g（續(xù)）q第二個(gè)+優(yōu)先級(jí)比*低，*彈出棧，輸出 ($ + $)，O: a b c *兩個(gè)+優(yōu)先級(jí)相等，怎么辦？看結(jié)合順序！左結(jié)合第一個(gè)+先計(jì)算，出棧，輸出 ($ + $)，O: a b c * a+b*c+(d*e+f)*g（續(xù)）q(括號(hào)內(nèi)子表達(dá)式先進(jìn)行計(jì)算前面的運(yùn)算符不應(yīng)該再輸出了，處理完括號(hào)中內(nèi)

36、容再說(shuō)怎么體現(xiàn)出來(lái)？壓棧，把前面運(yùn)算符屏蔽 ($ + ( $)，O: a b c * 完全可以從優(yōu)先級(jí)角度描述，(的優(yōu)先級(jí)最高，)的優(yōu)先級(jí)最低a+b*c+(d*e+f)*g（續(xù)）q*前面是(，相當(dāng)于遇到棧底，壓棧 ($ + ( * $)，O: a b c * + dq+：*輸出，+壓棧 ($ + ( + $)，O: a b c * + d e *q)：括號(hào)內(nèi)剩余運(yùn)算都給執(zhí)行了，不斷出棧輸出，直到遇到( ($ + $)，O: a b c * + d e * f +a+b*c+(d*e+f)*g（續(xù)）q*：壓棧 ($ + * $)，O: a b c * + d e * f +q符號(hào)串處理完畢：不斷

37、出棧輸出，直至?？?($ $)，O: a b c * + d e * f + g * +中綴后綴算法描述m由左至右掃描表達(dá)式，利用一個(gè)棧q遇到運(yùn)算數(shù)：輸出q遇到運(yùn)算符op：與棧頂運(yùn)算符op比較?？?、op=(、op優(yōu)先級(jí)高、優(yōu)先級(jí)相等但是右結(jié)合運(yùn)算：op壓棧op優(yōu)先級(jí)低、優(yōu)先級(jí)相等左結(jié)合：op出棧，輸出，重復(fù)此步驟op為)：棧中(之后的所有運(yùn)算符依次出棧，輸出，(也彈出q表達(dá)式處理完，棧中剩余運(yùn)算符依次出棧、輸出后綴表達(dá)式表達(dá)式樹(shù)m表達(dá)式樹(shù)運(yùn)算順序、運(yùn)算符與運(yùn)算對(duì)象的父子關(guān)系m掃描后綴表達(dá)式，就像是計(jì)算后綴表達(dá)式一樣的方式，但計(jì)算結(jié)果不是一個(gè)值，而是一棵表達(dá)式樹(shù)q運(yùn)算對(duì)象：構(gòu)造單節(jié)點(diǎn)樹(shù)，壓棧q運(yùn)

38、算符：出棧兩棵樹(shù)，作為左右子樹(shù)，運(yùn)算符作為根節(jié)點(diǎn)，構(gòu)造一棵新樹(shù)，壓棧q最終棧中的唯一一棵樹(shù)即為最后結(jié)果后綴表達(dá)式表達(dá)式樹(shù)例ma b + c d e + * *qa、b構(gòu)造單節(jié)點(diǎn)樹(shù)，壓棧后綴表達(dá)式表達(dá)式樹(shù)例（續(xù)）m+ c d e + * *q+：a、b兩棵樹(shù)出棧，作為左右子樹(shù)，+作為根，構(gòu)造新樹(shù)，壓棧后綴表達(dá)式表達(dá)式樹(shù)例（續(xù)）mc d e + * *qc、d、e構(gòu)造單節(jié)點(diǎn)樹(shù)，壓棧后綴表達(dá)式表達(dá)式樹(shù)例（續(xù)）m+ * *q+：子樹(shù)d、e構(gòu)造“+”樹(shù)，壓棧后綴表達(dá)式表達(dá)式樹(shù)例（續(xù)）m* *q*后綴表達(dá)式表達(dá)式樹(shù)例（續(xù)）m*q*8.10.1 設(shè)置信號(hào)放大器*q資源，生產(chǎn)地使用地，通過(guò)輸送網(wǎng)絡(luò)qsigna

39、l資源q傳輸過(guò)程中，性能損失、衰減，噪聲增加q信號(hào)衰減不超過(guò)閾值信號(hào)放大器q信號(hào)放大器放置在何處？數(shù)量最少且信號(hào)衰減不超過(guò)給定閾值問(wèn)題詳細(xì)描述m傳輸網(wǎng)絡(luò)樹(shù)形，源根節(jié)點(diǎn)m信號(hào)流向，節(jié)點(diǎn)孩子節(jié)點(diǎn)m邊標(biāo)記信號(hào)衰減量m除根外的節(jié)點(diǎn)可放置放大器問(wèn)題詳細(xì)描述（續(xù)）md(i)父節(jié)點(diǎn)節(jié)點(diǎn)i的信號(hào)衰減量md(i)閾值無(wú)解mD(i)qii為根的子樹(shù)的任一節(jié)點(diǎn)的衰減量和的最大值qi為葉節(jié)點(diǎn)D(i)=0q其他節(jié)點(diǎn)q后序遍歷計(jì)算)()()(maxijdjDiDj的孩子節(jié)點(diǎn)為放大器放置算法m節(jié)點(diǎn)i，子節(jié)點(diǎn)j，D(j)+d(j)閾值m不在j仿真放大器i葉的衰減閾值m應(yīng)在j放置放大器，D(i)=d(j)m偽代碼：D(i)=0

40、;for (i的每個(gè)孩子j)if (D(j)+d(j)tolerance)在j放置放大器;elseD(i)=maxD(i)，D(j)+d(j);定理8.1m定理8.1 上述算法所需放大器數(shù)目最少證明對(duì)樹(shù)的節(jié)點(diǎn)數(shù)n 進(jìn)行歸納當(dāng)n=1時(shí)，定理顯然成立設(shè)nm時(shí)，定理成立，m為任意的自然數(shù)tm+1個(gè)節(jié)點(diǎn)的樹(shù)，X上述算法所確定的放置放大器的節(jié)點(diǎn)的集合，W最少節(jié)點(diǎn)集合，只需證明|X|=|W|若|X|=0，顯然|X|=|W|考慮|X|0定理8.1考慮|X|0，設(shè)z為上述算法放置放大器的第一個(gè)節(jié)點(diǎn)，tz為以z為根的子樹(shù)D(z)+d(z)閾值W至少包含tz中某個(gè)節(jié)點(diǎn)u若W還包含其它節(jié)點(diǎn)，則W-類(lèi)似u的節(jié)點(diǎn)+z也

41、滿足要求W不是最優(yōu)方案因此W中包含的tz中節(jié)點(diǎn)只有u令W=W-u，t=t-tzW是t的最優(yōu)方案X=X-z也是t的一個(gè)方案，且|t|m+1|X|=|W|X|=|X| + 1=|W| + 1=|W|類(lèi)Boosterclass Booster / 作為二叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域 friend void main(void); friend void PlaceBoosters(BinaryTreeNode *); public: void Output(ostream& out) const out boost D d ; private: int D, / degradation to leaf

42、d; / degradation from parent bool boost; / true iff booster here;/ overload ostream& operator(ostream& out, Booster x) x.Output(out); return out;計(jì)算D值、放置放大器函數(shù)/ 作為PostOrder的參數(shù)void PlaceBoosters(BinaryTreeNode *x)/ Compute degradation at *x. Place booster / here if degradation exceeds tolerance

43、. BinaryTreeNode *y = x-LeftChild; int degradation; x-data.D = 0; / initialize degradation at x if (y) / compute from left child degradation = y-data.D + y-data.d; if (degradation tolerance) y-data.boost = true; x-data.D = y-data.d; else x-data.D = degradation; PlaceBoosters函數(shù)（續(xù)） y = x-RightChild; i

44、f (y) / compute from right child degradation = y-data.D + y-data.d; if (degradation tolerance) y-data.boost = true; degradation = y-data.d; if (x-data.D data.D = degradation; 8.10.2 在線等價(jià)類(lèi)問(wèn)題m合并/搜索（union-find）問(wèn)題m等價(jià)類(lèi)樹(shù)指針，孩子父樹(shù)的描述m模擬指針m節(jié)點(diǎn)索引元素值，parent域操作實(shí)現(xiàn)int *parent;void Initialize(int n)/ One element per

45、 set/class/tree. parent = new intn+1; for (int e = 1; e um每次合并Q(1)，每次查找由樹(shù)高決定m最壞情況，樹(shù)高=元素?cái)?shù)目Union(2, 1), Union(3, 2), Union(4,3), .m每次查找Q(q)，q為之前合并操作次數(shù)性能改進(jìn)m定義重量規(guī)則：若樹(shù)i 節(jié)點(diǎn)數(shù)少于樹(shù)j 節(jié)點(diǎn)數(shù)，則將j 作為i 的父節(jié)點(diǎn)，否則將i 作為j 的父節(jié)點(diǎn)m定義高度規(guī)則：若樹(shù)i 的高度小于樹(shù)j 的高度，則將j 作為i 的父節(jié)點(diǎn)，否則將i 作為j 的父節(jié)點(diǎn)重量規(guī)則實(shí)現(xiàn)mroot：標(biāo)記根，根的parent保存節(jié)點(diǎn)數(shù)目int *parent;bool *root;void