第8章 二叉樹和其他樹

1、計算機與控制工程學院第第8 8章章 二叉樹和其他樹二叉樹和其他樹-一種具有分支層次關系的數(shù)據(jù)結構一種具有分支層次關系的數(shù)據(jù)結構計算機與控制工程學院主要內(nèi)容主要內(nèi)容 樹的一般定義樹的一般定義 二叉樹的定義和操作二叉樹的定義和操作 二叉樹的遍歷二叉樹的遍歷2計算機與控制工程學院樹樹 線性表、表：不適合描述線性表、表：不適合描述層次結構層次結構數(shù)據(jù)數(shù)據(jù) 祖先后代、上級下屬、整體部分祖先后代、上級下屬、整體部分3計算機與控制工程學院4計算機與控制工程學院例例8-18-1：家庭關系：家庭關系5計算機與控制工程學院例例8-28-2 公司結構公司結構6計算機與控制工程學院例例8-38-3 政府機構政府機構7

2、計算機與控制工程學院例例8-48-4 軟件工程軟件工程8計算機與控制工程學院9計算機與控制工程學院數(shù)據(jù)結構數(shù)據(jù)結構“樹樹” 定義定義：樹樹（treetree）t t是一個非空的有限元素的集合，是一個非空的有限元素的集合，一個特殊的元素稱為一個特殊的元素稱為根根（rootroot），），余下的元素（如果有的話）組成余下的元素（如果有的話）組成t t的若干的若干子樹子樹（subtreesubtree） 遞歸！遞歸！10計算機與控制工程學院例例8-6 8-6 家庭關系例樹的描述家庭關系例樹的描述 數(shù)據(jù)集合數(shù)據(jù)集合JoeJoe，AnnAnn，MaryMary，MarkMark，SueSue，JohnJ

3、ohn，ChrisChris n=7n=7，根為，根為JoeJoe11計算機與控制工程學院家庭關系例樹的描述（續(xù)）家庭關系例樹的描述（續(xù)） 余下的元素余下的元素 AnnAnn單一元素子樹單一元素子樹 MaryMary，MarkMark，SueSue，根為，根為MaryMary的子樹的子樹 MarkMark和和SueSue，均為單元素的子樹，均為單元素的子樹 JohnJohn，ChrisChris，根為，根為JohnJohn的子樹的子樹 Chris Chris 也為單元素子樹也為單元素子樹12計算機與控制工程學院相關術語相關術語 元素元素節(jié)點節(jié)點 根節(jié)點與子樹的根節(jié)點的關系根節(jié)點與子樹的根節(jié)點的

4、關系邊邊 邊的兩端邊的兩端父母父母（parentparent）和）和孩子孩子（childrenchildren）13計算機與控制工程學院相關術語（續(xù)）相關術語（續(xù)） 相同父母的節(jié)點相同父母的節(jié)點兄弟兄弟（siblingsibling） 祖父祖父孫子孫子，祖先祖先后代后代 葉葉節(jié)點節(jié)點沒有孩子的節(jié)點，非葉節(jié)點沒有孩子的節(jié)點，非葉節(jié)點非非終端節(jié)點終端節(jié)點14計算機與控制工程學院相關術語（續(xù)）相關術語（續(xù)） 根根沒有父節(jié)點的節(jié)點沒有父節(jié)點的節(jié)點 層層（levellevel）：根）：根11，根的孩子，根的孩子22，. 節(jié)點的節(jié)點的度度（degreedegree）：孩子數(shù)目，葉）：孩子數(shù)目，葉0015計

5、算機與控制工程學院例例8-68-6 公司機構例公司機構例 公司雇員公司雇員節(jié)點，總裁節(jié)點，總裁根根 副總裁副總裁總裁的子節(jié)點，總裁總裁的子節(jié)點，總裁副總裁的父節(jié)點副總裁的父節(jié)點 不同副總裁不同副總裁兄弟節(jié)點兄弟節(jié)點16計算機與控制工程學院例例8-6 8-6 （續(xù)）（續(xù)） 政府機構例政府機構例 聯(lián)邦政府聯(lián)邦政府國防部，教育部，國防部，教育部，.，稅務部的父節(jié)點，稅務部的父節(jié)點 國防部的子節(jié)點國防部的子節(jié)點陸軍、海軍、空軍、海軍陸戰(zhàn)陸軍、海軍、空軍、海軍陸戰(zhàn)隊隊兄弟節(jié)點，葉節(jié)點兄弟節(jié)點，葉節(jié)點17計算機與控制工程學院樹的相關概念樹的相關概念 樹、子樹樹、子樹 根、分支節(jié)點、葉子節(jié)點根、分支節(jié)點、葉

6、子節(jié)點 父節(jié)點、孩子節(jié)點、兄弟節(jié)點父節(jié)點、孩子節(jié)點、兄弟節(jié)點 祖父、孫子、祖先、后代祖父、孫子、祖先、后代 邊邊 級、深度、高度級、深度、高度 度度18計算機與控制工程學院自由樹自由樹19計算機與控制工程學院有根樹有根樹20計算機與控制工程學院有序樹有序樹21計算機與控制工程學院森林和有序森林森林和有序森林 森林森林（forestforest）：）：樹的集合，通常認為是有樹的集合，通常認為是有根樹的集合根樹的集合 有序森林有序森林（orchardorchard，ordered forestordered forest）：）：有序樹的有序集合有序樹的有序集合 有根（有序）樹去掉根節(jié)點有根（有序）

7、樹去掉根節(jié)點（有序）森林（有序）森林 （有序）森林添加父節(jié)點（有序）森林添加父節(jié)點有根（有序）樹有根（有序）樹 22計算機與控制工程學院森林和有序森林（續(xù)）森林和有序森林（續(xù)）23計算機與控制工程學院有根樹的遞歸定義有根樹的遞歸定義 有根樹有根樹：包含單一頂點包含單一頂點v v，稱為樹的，稱為樹的根根，和一個森林和一個森林F F，F(xiàn) F的樹稱為的樹稱為根的子樹根的子樹而而森林森林F F（可為空）是一個有根樹的集合（可為空）是一個有根樹的集合24計算機與控制工程學院有序樹的定義有序樹的定義 一個一個有序樹有序樹T T：包含一個單一節(jié)點包含一個單一節(jié)點v v，稱為樹的，稱為樹的根根，和一個和一個有

8、序森林有序森林O O，O O的樹稱為的樹稱為v v的子樹，表示為的子樹，表示為T=v, OT=v, O25計算機與控制工程學院有序森林的定義有序森林的定義 一個一個有序森林有序森林O O：或者為空集或者為空集，或包含一個有序樹或包含一個有序樹T T，稱為有序森林的，稱為有序森林的第一樹第一樹，和另一個有序森林和另一個有序森林OO（包含有序森林的其它（包含有序森林的其它樹），可表示為樹），可表示為O=T, OO=T, O 有序樹有序森林：間接遞歸定義有序樹有序森林：間接遞歸定義26計算機與控制工程學院有序森林有序森林27計算機與控制工程學院課堂練習課堂練習 一棵有一棵有n n個結點的樹的所有結點

9、的度數(shù)之和個結點的樹的所有結點的度數(shù)之和是多少？是多少？28n-1計算機與控制工程學院課堂練習課堂練習 如果一棵樹有如果一棵樹有n n1 1個度為個度為1 1的節(jié)點，有的節(jié)點，有n n2 2個度為個度為2 2的節(jié)點，的節(jié)點，n nm m個度為個度為m m的節(jié)點，試問有的節(jié)點，試問有多少個度為多少個度為0 0的節(jié)點？的節(jié)點？29miimiinnin1101計算機與控制工程學院主要內(nèi)容主要內(nèi)容 樹的一般定義樹的一般定義 二叉樹的定義和操作二叉樹的定義和操作 二叉樹的遍歷二叉樹的遍歷30計算機與控制工程學院二叉樹二叉樹 定義定義： 二叉樹二叉樹（binary treebinary tree）t t是

10、有限元素集合：是有限元素集合：或者為空；或者為空；或者，有一個特殊元素或者，有一個特殊元素根根，余下的元素構成，余下的元素構成2 2個個二叉樹（可以為空）二叉樹（可以為空）tt的的左子樹左子樹和和右子樹右子樹31計算機與控制工程學院二叉樹和樹的根本區(qū)別二叉樹和樹的根本區(qū)別 二叉樹可以為空二叉樹可以為空樹不行樹不行 二叉樹每個節(jié)點都恰好有兩棵子樹（可以為空）二叉樹每個節(jié)點都恰好有兩棵子樹（可以為空）樹中每個節(jié)點可有若干子樹樹中每個節(jié)點可有若干子樹 二叉樹每個節(jié)點的子樹是有序的二叉樹每個節(jié)點的子樹是有序的“左左”、“右右”樹的子樹間是無序的樹的子樹間是無序的32計算機與控制工程學院二叉樹例二叉樹例

11、遞歸構造遞歸構造 空二叉樹空二叉樹遞歸的停止遞歸的停止 單一節(jié)點二叉樹單一節(jié)點二叉樹 兩個節(jié)點：兩個節(jié)點：不同！不能表示為不同！不能表示為33計算機與控制工程學院二叉樹例二叉樹例遞歸構造（續(xù)）遞歸構造（續(xù)） 三個節(jié)點三個節(jié)點 根左子樹根左子樹(2)(2)右子樹右子樹(0)(0)、1 11 1、0 02 2 類似方式，可構造更大的二叉樹類似方式，可構造更大的二叉樹34計算機與控制工程學院二叉樹例：表達式樹二叉樹例：表達式樹a)a)a a* *b + c/db + c/db)b)a+b+c+da+b+c+dc)c)(-a+(x+y)/(+b(-a+(x+y)/(+b* *(c(c* *a)a)35

12、計算機與控制工程學院二叉樹的特性二叉樹的特性 特性特性1 1 包含包含n n ( (n n0)0)個節(jié)點的二叉樹邊數(shù)為個節(jié)點的二叉樹邊數(shù)為n n-1-1證明證明二叉樹中每個節(jié)點（除根節(jié)點，共二叉樹中每個節(jié)點（除根節(jié)點，共n-1n-1個節(jié)個節(jié)點）點） 有且只有一個父節(jié)點有且只有一個父節(jié)點每個子節(jié)點與父節(jié)點間有且只有一條邊每個子節(jié)點與父節(jié)點間有且只有一條邊邊數(shù)為邊數(shù)為n n-1-136計算機與控制工程學院特性特性2 2 二叉樹的二叉樹的高度高度（heightheight）（）（深度深度，depthdepth）：）：二叉樹的層數(shù)二叉樹的層數(shù) 特性特性2 2 若二叉樹的高度為若二叉樹的高度為h h，h

13、 h00，則它最，則它最少有少有h h個節(jié)點，最多有個節(jié)點，最多有2 2h h-1-1個節(jié)點個節(jié)點37計算機與控制工程學院特性特性2 2的證明的證明證明證明每層最少要有每層最少要有1 1個節(jié)點個節(jié)點節(jié)點數(shù)最少為節(jié)點數(shù)最少為h h每個節(jié)點最多有每個節(jié)點最多有2 2個子節(jié)點個子節(jié)點則第則第i i層節(jié)點最層節(jié)點最多為多為2 2i i-1-1個，個，i i11節(jié)點的總數(shù)不會超過節(jié)點的總數(shù)不會超過12222211011hhhii38計算機與控制工程學院特性特性2 2說明說明深度深度該層最多節(jié)點數(shù)該層最多節(jié)點數(shù)二叉樹的最多節(jié)點總數(shù)二叉樹的最多節(jié)點總數(shù)120=11221=23322=47423=815524

14、=1631625=326339計算機與控制工程學院特性特性3 3 特性特性3 3 包含包含n n個節(jié)點的二叉樹的高度最大為個節(jié)點的二叉樹的高度最大為n n，最小為，最小為證明證明每層至少一個元素每層至少一個元素高度不會超過高度不會超過n n由特性由特性2 2，可知高度為，可知高度為h h，節(jié)點最多，節(jié)點最多2 2h h-1-1即即n n22h h-1-1h hloglog2 2( (n n+1)+1)且且h h是整數(shù)是整數(shù)) 1(log2n) 1(log2nh40計算機與控制工程學院滿二叉樹（滿二叉樹（full binary tree full binary tree ） 高度為高度為h h，

15、節(jié)點數(shù)，節(jié)點數(shù)2 2h h-1-141計算機與控制工程學院完全二叉樹完全二叉樹 高度為高度為h h 的滿二叉樹中節(jié)點按從上到下，從的滿二叉樹中節(jié)點按從上到下，從左到右的順序從左到右的順序從1 1到到2 2h h-1-1進行編號進行編號 從中刪除從中刪除k k個節(jié)點，編號為個節(jié)點，編號為2 2h h- -i i, 1, 1i ik k 即為即為完全二叉樹，深度為完全二叉樹，深度為) 1(log2n42計算機與控制工程學院另一種定義方法另一種定義方法 設二叉樹設二叉樹T T有有n n個節(jié)點，令個節(jié)點，令則則k k代表最下一層，也就是二叉樹的深度，代表最下一層，也就是二叉樹的深度，r r代代表第表第

16、k k層的節(jié)點數(shù)，其中層的節(jié)點數(shù)，其中2 2k-1k-1個節(jié)點放滿第個節(jié)點放滿第1 1到到第第k-1k-1層，則：層，則：若若0r=20r 1 1，則該元素父節(jié)點的編號為則該元素父節(jié)點的編號為2)2) 當當2 2i i n n時，該元素無左孩子。否則，其左孩時，該元素無左孩子。否則，其左孩子的編號為子的編號為2 2i i3)3) 若若2 2i i + 1+ 1n n，該元素無右孩子。否則，其右，該元素無右孩子。否則，其右孩子編號為孩子編號為2 2i i + 1+ 12/ i44計算機與控制工程學院特性特性4 4（續(xù)）（續(xù)）證明證明通過對通過對i i 進行歸納即可得證進行歸納即可得證45計算機與

17、控制工程學院特性特性5 5 設二叉樹中度為設二叉樹中度為2 2的節(jié)點有的節(jié)點有n n2 2個，度為個，度為1 1的節(jié)的節(jié)點有點有n n1 1個，度為個，度為0 0的節(jié)點有的節(jié)點有n n0 0個，則個，則n n0 0=n=n2 2+1+1 一棵二叉樹有一棵二叉樹有10241024個節(jié)點，其中個節(jié)點，其中465465個是葉個是葉節(jié)點，那么樹中度為節(jié)點，那么樹中度為2 2和度為和度為1 1的節(jié)點各有多的節(jié)點各有多少？少？461110miinin464,95計算機與控制工程學院思考思考 一棵二叉樹有一棵二叉樹有1919個節(jié)點，其中個節(jié)點，其中6 6個是葉節(jié)點個是葉節(jié)點，那么樹中度為，那么樹中度為2 2

18、和度為和度為1 1的節(jié)點各有多少？的節(jié)點各有多少？ 能否構造一棵符合條件的能否構造一棵符合條件的二叉樹二叉樹？ 能否構造一棵符合條件的能否構造一棵符合條件的完全二叉樹完全二叉樹？475,8計算機與控制工程學院思考思考 有有m m個葉子的個葉子的二叉樹二叉樹最多有多少個節(jié)點？最多有多少個節(jié)點？ 有有m m個葉子的個葉子的完全二叉樹完全二叉樹最多有多少個節(jié)點？最多有多少個節(jié)點？48無窮無窮計算機與控制工程學院課堂練習課堂練習 設高度為設高度為h h的二叉樹中只有度為的二叉樹中只有度為0 0和度為和度為2 2的的節(jié)點，則此類二叉樹所包含的節(jié)點數(shù)至少為節(jié)點，則此類二叉樹所包含的節(jié)點數(shù)至少為_，至多為，

19、至多為_。492h-12h-1計算機與控制工程學院課堂練習課堂練習 設完全二叉樹的第設完全二叉樹的第6 6層有層有2424個葉節(jié)點，則此個葉節(jié)點，則此樹最多有樹最多有_個節(jié)點個節(jié)點A. 55A. 55B. 79B. 79C. 81C. 81D. 127D. 12750B計算機與控制工程學院二叉樹描述二叉樹描述 公式化描述公式化描述利用特性利用特性4 4 普通二叉樹普通二叉樹缺少部分節(jié)點的完全二叉樹缺少部分節(jié)點的完全二叉樹51計算機與控制工程學院公式化描述公式化描述 數(shù)組位置數(shù)組位置節(jié)點編號節(jié)點編號 父子節(jié)點關系父子節(jié)點關系特性特性4 452計算機與控制工程學院公式化描述公式化描述 n n層二叉

20、樹層二叉樹22n n-1-1數(shù)組保存，可能空間浪費！數(shù)組保存，可能空間浪費！53計算機與控制工程學院鏈表描述鏈表描述 樹節(jié)點樹節(jié)點節(jié)點類對象節(jié)點類對象 數(shù)據(jù)域、數(shù)據(jù)域、LeftChildLeftChild、RightChildRightChild n-1n-1條邊條邊2n-(n-1)=n+12n-(n-1)=n+1個空指針個空指針54計算機與控制工程學院BinaryTreeNodeBinaryTreeNode類類template class BinaryTreeNode public: BinaryTreeNode() LeftChild = RightChild = 0; BinaryTre

21、eNode(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 subtree *RightChild; / right subtree;55計算機與控制工程學院抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型BinaryTreeBinaryTre

22、e抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型BinaryTreeBinaryTree 實例實例元素集合；如果不空，則被劃分為根節(jié)點、左子樹和右子樹；元素集合；如果不空，則被劃分為根節(jié)點、左子樹和右子樹；每個子樹仍是一個二叉樹每個子樹仍是一個二叉樹操作操作CreateCreate()()：創(chuàng)建一個空的二叉樹；：創(chuàng)建一個空的二叉樹；IsEmptyIsEmpty：如果二叉樹為空，則返回：如果二叉樹為空，則返回truetrue，否則返回，否則返回falsefalseRootRoot( (x x) )：取：取x x為根節(jié)點；如果操作失敗，則返為根節(jié)點；如果操作失敗，則返回回falsefalse，否則返回，否則返回true

23、true56計算機與控制工程學院抽象數(shù)據(jù)類型（續(xù)）抽象數(shù)據(jù)類型（續(xù)）MakeTreeMakeTree( (rootroot，leftleft，rightright) )：創(chuàng)建一個二叉樹，：創(chuàng)建一個二叉樹，rootroot作為作為根節(jié)點，根節(jié)點，leftleft作為左子樹，作為左子樹，rightright作作為右子樹為右子樹BreakTreeBreakTree( (rootroot，leftleft，rightright) )：拆分二叉樹：拆分二叉樹PreOrderPreOrder：先序遍歷：先序遍歷InOrderInOrder：中序遍歷：中序遍歷PostOrderPostOrder：后序遍歷：

24、后序遍歷LevelOrderLevelOrder：逐層遍歷：逐層遍歷 57計算機與控制工程學院類類BinaryTreeBinaryTreetemplateclass 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);

25、void BreakTree(T& element, BinaryTree& left, BinaryTree& right); void PreOrder(void(*Visit)(BinaryTreeNode *u) PreOrder(Visit, root);58計算機與控制工程學院類類BinaryTreeBinaryTree（續(xù)）（續(xù)） void InOrder(void(*Visit)(BinaryTreeNode *u) InOrder(Visit, root); void PostOrder(void(*Visit)(BinaryTreeNode *u)

26、PostOrder(Visit, root); void LevelOrder(void(*Visit)(BinaryTreeNode *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

27、*u), BinaryTreeNode *t);59計算機與控制工程學院獲取根節(jié)點數(shù)據(jù)獲取根節(jié)點數(shù)據(jù)templatebool BinaryTree:Root(T& x) const/ Return root data in x. / Return false if no root. if (root) x = root-data; return true; else return false; / no root60計算機與控制工程學院創(chuàng)建樹創(chuàng)建樹templatevoid BinaryTree:MakeTree(const T& element, BinaryTree&

28、 left, BinaryTree& right)/ Combine left, right, and element to make new tree. / left, 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,

29、 X)且X不為空61計算機與控制工程學院分裂樹分裂樹templatevoid BinaryTree:BreakTree(T& element, BinaryTree& 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.

30、root = root-RightChild; delete root; root = 0;62計算機與控制工程學院思考思考 在上述存儲方式下，尋找某一節(jié)點孩子的復在上述存儲方式下，尋找某一節(jié)點孩子的復雜度是雜度是O(1)O(1)，尋找其父親的復雜度是，尋找其父親的復雜度是O(n)O(n)，為什么？為什么？ 如果希望將尋找父節(jié)點的效率提高到如果希望將尋找父節(jié)點的效率提高到O(1)O(1)，如何做？如何做？63計算機與控制工程學院主要內(nèi)容主要內(nèi)容 樹的一般定義樹的一般定義 二叉樹的定義和操作二叉樹的定義和操作 二叉樹的遍歷二叉樹的遍歷64計算機與控制工程學院二叉樹遍歷二叉樹遍歷 按照某種順序訪問

31、樹中的每個節(jié)點，按照某種順序訪問樹中的每個節(jié)點， 要求每個節(jié)點被訪問一次且僅被訪問一次要求每個節(jié)點被訪問一次且僅被訪問一次 這就是這就是二叉樹遍歷問題二叉樹遍歷問題65計算機與控制工程學院二叉樹遍歷二叉樹遍歷 遍歷順序遍歷順序【關鍵關鍵】 訪問根節(jié)點、左子樹、右子樹的順序訪問根節(jié)點、左子樹、右子樹的順序 左右子樹的訪問（遍歷）？左右子樹的訪問（遍歷）？遞歸！遞歸！ 可能的遍歷順序可能的遍歷順序 V V根，根，L L左子樹，左子樹，R R右子樹右子樹 VLR LVR LRV VRL RVL RLVVLR LVR LRV VRL RVL RLV66計算機與控制工程學院標準遍歷順序標準遍歷順序 都是

32、左子樹先于右子樹，關鍵都是左子樹先于右子樹，關鍵根的訪問次根的訪問次序序 先序遍歷（先序遍歷（preorderpreorder）VLRVLR 中序遍歷（中序遍歷（inorderinorder）LVRLVR 后序遍歷（后序遍歷（postorderpostorder）LRVLRVVLR67計算機與控制工程學院先序遍歷先序遍歷template void PreOrder(BinaryTreeNode *t)/ Preorder traversal of *t. if (t) Visit(t); / visit tree root PreOrder(t-LeftChild); / do left su

33、btree PreOrder(t-RightChild); / do right subtree 68計算機與控制工程學院中序遍歷中序遍歷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 69計算機與控制工程學院后序遍歷后序遍歷template void PostOrder(Bin

34、aryTreeNode *t)/ Postorder traversal of *t. if (t) PostOrder(t-LeftChild); / do left subtree PostOrder(t-RightChild); / do right subtree Visit(t); / visit tree root 70計算機與控制工程學院先序遍歷表達式樹先序遍歷表達式樹a)+*ab/cdb)+abcdc)/+-a+xy*+b*cam前綴表達式71計算機與控制工程學院中序遍歷表達式樹中序遍歷表達式樹a)a*b + c/db)a+b+c+dc)-a+x+y/+b*c*am中綴表達式人

35、類習慣m需加括號72計算機與控制工程學院后序遍歷表達式樹后序遍歷表達式樹a)ab*cd/+b)ab+c+d+c)a-xy+b+ca*/m后綴表達式計算機計算非常方便73計算機與控制工程學院輸出完全括號化的中綴表達式輸出完全括號化的中綴表達式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 );74

36、計算機與控制工程學院逐層遍歷（寬度優(yōu)先）逐層遍歷（寬度優(yōu)先） 根根葉逐層，同層由左至右葉逐層，同層由左至右template void LevelOrder(BinaryTreeNode *t)/ Level-order traversal of *t. LinkedQueueBinaryTreeNode* Q; while (t) Visit(t); / visit t 75計算機與控制工程學院逐層遍歷（寬度優(yōu)先）逐層遍歷（寬度優(yōu)先） / put ts children on queue if (t-LeftChild) Q.Add(t-LeftChild); if (t-RightChild

37、) Q.Add(t-RightChild); / get next node to visit try Q.Delete(t); catch (OutOfBounds) return; 出隊次序即是遍歷次序；同時控制t移向下一節(jié)點。76計算機與控制工程學院由遍歷順序推導二叉樹結構由遍歷順序推導二叉樹結構 一棵二叉樹一棵二叉樹先序遍歷結果先序遍歷結果1, 2, 4, 7, 3, 5, 6, 8, 91, 2, 4, 7, 3, 5, 6, 8, 9中序遍歷結果中序遍歷結果4, 7, 2, 1, 5, 3, 8, 6, 94, 7, 2, 1, 5, 3, 8, 6, 9能推導出其結構嗎？能推導出

38、其結構嗎？ 可以！可以！77計算機與控制工程學院第一步第一步1, 2, 4, 7, 3, 5, 6, 8, 91, 2, 4, 7, 3, 5, 6, 8, 94, 7, 2, 1, 5, 3, 8, 6, 94, 7, 2, 1, 5, 3, 8, 6, 9 先序遍歷先序遍歷根左子樹右子樹根左子樹右子樹“1”1”必為根節(jié)點必為根節(jié)點 中序遍歷中序遍歷左子樹根右子樹，且左子樹根右子樹，且1 1為根節(jié)點為根節(jié)點4, 7, 24, 7, 2為左子樹，為左子樹，5, 3, 8, 6, 95, 3, 8, 6, 9為右子樹為右子樹78計算機與控制工程學院下面怎么辦？遞歸！下面怎么辦？遞歸！ 左子樹左子

39、樹先序遍歷先序遍歷2, 4, 72, 4, 7中序遍歷中序遍歷4, 7, 24, 7, 2 右子樹右子樹先序遍歷先序遍歷3, 5, 6, 8, 93, 5, 6, 8, 9中序為中序為5, 3, 8, 6, 95, 3, 8, 6, 9 利用相同方法構造左、右子樹，直至列表長度利用相同方法構造左、右子樹，直至列表長度為為00空子樹，無需構造空子樹，無需構造79計算機與控制工程學院遍歷順序遍歷順序二叉樹結構（續(xù)）二叉樹結構（續(xù)）80計算機與控制工程學院遍歷順序遍歷順序二叉樹結構（續(xù)）二叉樹結構（續(xù)）先序3, 5, 6, 8, 9，中序5, 3, 8, 6, 981計算機與控制工程學院遍歷順序遍歷

40、順序二叉樹結構（續(xù)）二叉樹結構（續(xù)）先序6, 8, 9中序8, 6, 982計算機與控制工程學院抽象數(shù)據(jù)類型及類的擴充抽象數(shù)據(jù)類型及類的擴充 增加如下二叉樹操作：增加如下二叉樹操作：PreOutputPreOutput()()：按前序方式輸出數(shù)據(jù)域：按前序方式輸出數(shù)據(jù)域InOutputInOutput()()：按中序方式輸出數(shù)據(jù)域：按中序方式輸出數(shù)據(jù)域PostOutputPostOutput()()：按后序方式輸出數(shù)據(jù)域：按后序方式輸出數(shù)據(jù)域LevelOutputLevelOutput()()：逐層輸出數(shù)據(jù)域：逐層輸出數(shù)據(jù)域DeleteDelete()()：刪除一棵二叉樹，釋放其節(jié)點：刪除一棵

41、二叉樹，釋放其節(jié)點HeightHeight()()：返回樹的高度：返回樹的高度SizeSize()()：返回樹中節(jié)點數(shù)：返回樹中節(jié)點數(shù)83計算機與控制工程學院銷毀二叉樹銷毀二叉樹 刪除所有節(jié)點刪除所有節(jié)點 后序遍歷后序遍歷：刪除左子樹、刪除右子樹、刪除：刪除左子樹、刪除右子樹、刪除根根 輔助函數(shù)輔助函數(shù)刪除單個節(jié)點刪除單個節(jié)點 static void Free(BinaryTreeNode *t) delete t; 刪除二叉樹刪除二叉樹void Delete() PostOrder(Free, root); root = 0;84計算機與控制工程學院計算高度計算高度 后序遍歷后序遍歷 左子樹

42、高度、右子樹高度較大者左子樹高度、右子樹高度較大者+1+1（根節(jié)點）（根節(jié)點）樹的高度樹的高度 遞歸公式：遞歸公式：h=maxhl, hr + 1h=maxhl, hr + 1遞歸函數(shù)遞歸函數(shù) 公共接口公共接口int Height() const return Height(root);85計算機與控制工程學院計算高度的遞歸函數(shù)計算高度的遞歸函數(shù)HeightHeighttemplate 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;86計算機與控制工程學院統(tǒng)