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

1、講師：尹成 QQ:77025077 博客:http:/ 微博:http:/ Mail: 網(wǎng)址:http:/ C/C+ 算法算法+實(shí)戰(zhàn)實(shí)戰(zhàn) 傳智播客傳智播客 http:/ 高薪就業(yè)高薪就業(yè) 第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-2 m公司結(jié)構(gòu) 例8-3 m政府機(jī)構(gòu) 例8-4 m軟件工程 數(shù)據(jù)結(jié)構(gòu)“樹(shù)” m定義： 樹(shù)（tree）t是一個(gè)非空的有限元素的集合， 一個(gè)特殊的元素

2、稱為根（root）， 余下的元素（如果有的話）組成t的若干 子樹(shù)（subtree） m遞歸！ 例8-6 家庭關(guān)系例樹(shù)的描述 m數(shù)據(jù)集合 Joe，Ann，Mary，Mark，Sue，John， Chris mn=7，根為Joe 家庭關(guān)系例樹(shù)的描述（續(xù)） 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)兄弟（si

3、bling） 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-6 m公司機(jī)構(gòu)例 q公司雇員節(jié)點(diǎn)，總裁根 q副總裁總裁的子節(jié)點(diǎn)，總裁副總裁的 父節(jié)點(diǎn) q不同副總裁兄弟節(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，or

4、dered 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è)有序森林O，O的樹(shù)稱為v的子樹(shù)， 表示為T=v, O 有序森林的定義 m一個(gè)有序森林O： 或者為空集， 或包含一個(gè)有序樹(shù)T，稱為有序森林的第 一樹(shù)， 和另一個(gè)有序森林O（包含有序森林的 其它樹(shù)），可表示為O=T, O m有序樹(shù)有序森林：間接遞歸定義 有序森林

5、 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ù)遞歸的停止 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、02 m類似方式，可構(gòu)造更大的二叉樹(shù) 二叉樹(shù)例：表達(dá)式樹(shù) a)a*b +

6、 c/d b)a+b+c+d c)(-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 特性2 m二叉樹(shù)的高度（height）（深度，depth）： 二叉樹(shù)的層數(shù) m特性2 若二叉樹(shù)的高度為h，h0，則它 最少有h個(gè)節(jié)點(diǎn)，最多有2h-1個(gè)節(jié)點(diǎn) 特性2的證明 證明 每層最少要有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ò)122 1 1 h h i i

7、特性3 m特性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, 1ik m即為完全二叉樹(shù)，深度為 ) 1(log2n 特性4 m特性4 設(shè)完全二叉樹(shù)中一節(jié)點(diǎn)的序號(hào)為 i, 1in。則

8、有以下關(guān)系成立： 1)當(dāng)i = 1時(shí)，該元素為二叉樹(shù)的根。若i 1，則該元素父節(jié)點(diǎn)的編號(hào)為 2)當(dāng)2in時(shí)，該元素?zé)o左孩子。否則，其 左孩子的編號(hào)為2i 2/ i 特性4（續(xù)） 3)若2i + 1n，該元素?zé)o右孩子。否則， 其右孩子編號(hào)為2i + 1 證明 通過(guò)對(duì)i 進(jìn)行歸納即可得證 8.4 二叉樹(shù)描述 m8.4.1 公式化描述利用特性4 q普通二叉樹(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)類對(duì)象 q數(shù)據(jù)域、LeftChild、RightChild qn-1條邊2

9、n-(n-1)=n+1個(gè)空指針 BinaryTreeNode類 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); BinaryTreeNode類

10、 public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTreeNode(const T LeftChild = RightChild = 0; BinaryTreeNode(const T LeftChild = l; RightChild = r; private: T data; BinaryTreeNode *LeftChild, / left subtree *RightChild; / right subtree ; 二叉樹(shù)與有序森林的對(duì)應(yīng)關(guān)系 m二叉樹(shù)的另一種定義：一個(gè)二叉樹(shù)B 或者是空集， 或者包含一個(gè)根v和兩個(gè)二

11、叉樹(shù)B1和B2， 可表示為B=v, B1, B2 m定理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為頂點(diǎn)，O1為另一森 林（有序樹(shù)定義）2 由1、2O=v, O1, O2 O1和O2節(jié)點(diǎn)數(shù)必然 n存在一一對(duì)應(yīng)的 二叉樹(shù)f(O1)和f(

12、O2) 定義：f(O)=f(v, O1, O2)=v, f(O1), f(O2) 因此，f(O)表示一棵二叉樹(shù)，對(duì)|S|=n命題 成立 命題得證 用二叉樹(shù)類型描述樹(shù)（森林） mLeftChild指向第一個(gè)孩子節(jié)點(diǎn) mRightChild指向下一個(gè)兄弟節(jié)點(diǎn) m顯然，遍歷函數(shù)應(yīng)修改 用二叉樹(shù)類型描述樹(shù)（森林） 用二叉樹(shù)類型描述樹(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á)式 m若為數(shù)學(xué)表達(dá)式樹(shù)，給出對(duì)應(yīng)的帶括號(hào) 的表達(dá)式 m都可通過(guò)二叉樹(shù)遍歷（按某種順序訪問(wèn)

13、 所有節(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）VLR m中序遍歷（inorder）LVR m后序遍歷（postorder）LRV 先序遍歷 template void PreOrder(BinaryTreeNode *t) / Preorder traversal of *t. if (t) Visit(t); / visi

14、t 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 subtree 后序遍歷 template

15、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ù) a)+*ab/cd b)+abcd c)/+-a+xy*+b*ca m前綴表達(dá)式 中序遍歷表達(dá)式樹(shù) a)a*b + c/d b)a+b+c+d c)-a+x+y/+b*c*a m中綴表達(dá)式 人類習(xí)慣 m需加括號(hào) 后

16、序遍歷表達(dá)式樹(shù) a)ab*cd/+ b)ab+c+d+ c)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 LevelOrd

17、er(BinaryTreeNode *t) / 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; 最壞情

18、況空間復(fù)雜性O(shè)(n) 時(shí)間復(fù)雜性(n) 8.7 抽象數(shù)據(jù)類型BinaryTree 抽象數(shù)據(jù)類型BinaryTree 實(shí)例 元素集合；如果不空，則被劃分為根節(jié)點(diǎn)、左 子樹(shù)和右子樹(shù)；每個(gè)子樹(shù)仍是一個(gè)二叉樹(shù) 操作 Create()：創(chuàng)建一個(gè)空的二叉樹(shù)； IsEmpty：如果二叉樹(shù)為空，則返回true，否則 返回false Root(x)：取x為根節(jié)點(diǎn)；如果操作失敗，則返 回false，否則返回true 抽象數(shù)據(jù)類型（續(xù)） MakeTree(root，left，right)：創(chuàng)建一個(gè)二叉樹(shù)， root作為根節(jié)點(diǎn)，left作為左子樹(shù)，right作 為右子樹(shù) BreakTree(root，left，rig

19、ht)：拆分二叉樹(shù) PreOrder：先序遍歷 InOrder：中序遍歷 PostOrder：后序遍歷 LevelOrder：逐層遍歷 8.8 類BinaryTree template class BinaryTree public: BinaryTree() root = 0; BinaryTree(); bool IsEmpty() const return (root) ? false : true); bool Root(T void MakeTree(const T void BreakTree(T void PreOrder(void(*Visit)(BinaryTreeNode

20、*u) PreOrder(Visit, root); 類BinaryTree（續(xù)） void InOrder(void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder(void(*Visit)(BinaryTreeNode *u) PostOrder(Visit, root); void LevelOrder(void(*Visit)(BinaryTreeNode *u); private: BinaryTreeNode *root; / pointer to root void PreOrder(void(*Vi

21、sit) (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ù) template bool BinaryTree:Root(T return true; else return false; / no root 創(chuàng)建樹(shù) template void BinaryTree:MakeT

22、ree(const T / deny access from trees left and right left.root = right.root = 0; 缺陷：允許 MakeTree(e, X, X)且X 不為空 為什么置為空？不會(huì)造成空 懸指針嗎？ 分裂樹(shù) template void BinaryTree:BreakTree(T / tree empty / break the tree element = root-data; left.root = root-LeftChild; right.root = root-RightChild; delete root; root = 0

23、; 與上例相同的道理 先序遍歷 template void BinaryTree:PreOrder(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) / Inorde

24、r traversal. if (t) InOrder(Visit, t-LeftChild); Visit(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 vo

25、id BinaryTree:LevelOrder(void(*Visit)(BinaryTreeNode *u) / 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一棵二叉

26、樹(shù) 先序遍歷結(jié)果1, 2, 4, 7, 3, 5, 6, 8, 9 中序遍歷結(jié)果4, 7, 2, 1, 5, 3, 8, 6, 9 能推導(dǎo)出其結(jié)構(gòu)嗎？ m可以！ 第一步 1, 2, 4, 7, 3, 5, 6, 8, 9 4, 7, 2, 1, 5, 3, 8, 6, 9 m先序遍歷 根左子樹(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, 2 m右子樹(shù) 先序遍歷3, 5, 6, 8, 9 中序?yàn)?, 3, 8, 6, 9 m利用相同方法構(gòu)造左、

27、右子樹(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 遍歷順序二叉樹(shù)結(jié)構(gòu)（續(xù)） 先序6, 8, 9 中序8, 6, 9 使用BinaryTree int count = 0; BinaryTree a,x,y,z; template void 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.

28、PreOrder(ct); cout count endl; 8.9 抽象數(shù)據(jù)類型及類的擴(kuò)充 m增加如下二叉樹(shù)操作： PreOutput()：按前序方式輸出數(shù)據(jù)域 InOutput()：按中序方式輸出數(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() PreO

29、rder(Output, root); cout endl; void InOutput() InOrder(Output, root); cout endl; void PostOutput() PostOrder(Output, root); cout endl; void LevelOutput() LevelOrder(Output); cout endl; 8.9.2 銷毀二叉樹(shù) m刪除所有節(jié)點(diǎn) m后序遍歷：刪除左子樹(shù)、刪除右子樹(shù)、 刪除根 m輔助函數(shù)刪除單個(gè)節(jié)點(diǎn) static void Free(BinaryTreeNode *t) delete t; m刪除二叉樹(shù) void De

30、lete() 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公共接口 int Height() const return Height(root); 計(jì)算高度的遞歸函數(shù)Height template int BinaryTree:Height(BinaryTreeNode *t) const / Return height of tree *t. if (!t) return 0; / empty tree int hl = Hei

31、ght(t-LeftChild); / height of left int hr = Height(t-RightChild); / height of right if (hl hr) return +hl; else return +hr; 8.9.4 統(tǒng)計(jì)節(jié)點(diǎn)數(shù)目 m任意一種遍歷方法，每個(gè)節(jié)點(diǎn)將統(tǒng)計(jì)計(jì) 數(shù)加1 m私有輔助函數(shù)Add1 static 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利用遞

32、歸公式：s=sl+sr+1 template int BinaryTree:Size(BinaryTreeNode *t) const if (!t) return 0; else return Size(t-LeftChild)+Size(t-RightChild)+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ù)push q遇到運(yùn)算符pop棧頂兩個(gè)運(yùn)算數(shù)，運(yùn)算 結(jié)果push q最終，棧中的數(shù)即為最終計(jì)算結(jié)果 利用棧計(jì)算后綴表達(dá)式 m6*

33、(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 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)*g m由左至右掃描，利

34、用棧 qa，一個(gè)運(yùn)算數(shù)，怎么做？ 無(wú)論中綴、后綴還是前綴，運(yùn)算對(duì)象的順序都是 一樣的，輸出即可 ($ $)，O: a q+，一個(gè)運(yùn)算符，直接輸出可以嗎？ 運(yùn)算符應(yīng)在兩個(gè)運(yùn)算對(duì)象之后，顯然不行 壓棧：($ + $)，O: a a+b*c+(d*e+f)*g（續(xù)） qb，輸出 已輸出兩個(gè)運(yùn)算對(duì)象了，能輸出棧中的“+”嗎？ 運(yùn)算順序還不確定，或者說(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)該壓棧：($ + *

35、$)，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)容再說(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)于遇到棧底，壓棧 ($ + (

36、* $)，O: a b c * + d q+：*輸出，+壓棧 ($ + ( + $)，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)串處理完畢：不斷出棧輸出，直至棧 空 ($ $)，O: a b c * + d e * f + g * + 中綴后綴算法描述 m由左至右掃描表達(dá)式，利用一個(gè)棧 q遇到運(yùn)算數(shù)：輸出 q遇到運(yùn)算符op：與棧頂運(yùn)算符op比較 ?？?、op=

37、(、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)算符：出棧兩棵樹(shù)，作為左右子樹(shù)，運(yùn)算 符作為根節(jié)點(diǎn)，構(gòu)造一棵新樹(shù)，壓棧 q最終棧中的唯一一棵樹(shù)即為最后結(jié)果 后綴表達(dá)式表達(dá)式樹(shù)例 ma b + c d e + * * qa、

38、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ò) qsignal資源 q傳輸過(guò)程中，性能損失、衰減，噪聲增加 q信號(hào)衰減不超過(guò)閾值信號(hào)放大器 q信號(hào)放大器放置在何處？ 數(shù)量最少 且信號(hào)衰減

39、不超過(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)=0 q其他節(jié)點(diǎn) q后序遍歷計(jì)算 )()()( max i jdjDiD j 的孩子節(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; for (i的每個(gè)孩子j) if (D(j)+d(j)tol

40、erance) 在j放置放大器; else D(i)=maxD(i)，D(j)+d(j); 定理8.1 m定理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-類似u的節(jié)點(diǎn)+z 也滿足要求W不是最優(yōu)方

41、案 因此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| 類Booster class Booster / 作為二叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域 friend void main(void); friend void PlaceBoosters(BinaryTreeNode *); public: void Output(ostream private: int D, / degradation to leaf d; / degradation from parent bool

42、boost; / true iff booster here ; / overload ostream return out; 計(jì)算D值、放置放大器函數(shù) / 作為PostOrder的參數(shù) void PlaceBoosters(BinaryTreeNode *x) / Compute degradation at *x. Place booster / here if degradation exceeds tolerance. BinaryTreeNode *y = x-LeftChild; int degradation; x-data.D = 0; / initialize degrada

43、tion 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; if (y) / compute from right child degradation = y-data.D + y-data.d; if (degradation to

44、lerance) y-data.boost = true; degradation = y-data.d; if (x-data.D data.D = degradation; 8.10.2 在線等價(jià)類問(wèn)題 m合并/搜索（union-find）問(wèn)題 m等價(jià)類樹(shù)指針，孩子父 樹(shù)的描述 m模擬指針 m節(jié)點(diǎn)索引元素值，parent域 操作實(shí)現(xiàn) int *parent; void Initialize(int n) / One element per set/class/tree. parent = new intn+1; for (int e = 1; e u m每次合并Q(1)，每次查找由樹(shù)高決定

45、 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 Initialize(int n) / One element per set/class/tree. root = new booln+1; parent = new intn