第五章樹和二叉樹PPT課件

1、5-1 樹的提出v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社文件系統(tǒng)文件系統(tǒng)許多問題抽象出的數據模型具有層次關系例 1 操作系統(tǒng)的文件目錄結構。數據結構（從概念到實現） 清華大學出版社表達式樹表達式樹例 2 一個算術表達式可以用表達式樹來表示，并且具有以下兩個特點（1）葉子結點是操作數；（2）分支結點是運算符。進行后序遍歷轉換為逆波蘭式：a b c d - * + e f / -aefbcd-+/*-表達式：a + b * (c d) e / f數據結構（從概念到實現） 清華大學出版社隨處可見的樹結構隨處可見的樹結構例 3 計算機系統(tǒng)上隨處可見的樹結構。數據結構（從概念到實現）

2、 清華大學出版社隨處可見的樹結構隨處可見的樹結構例 3 計算機系統(tǒng)上隨處可見的樹結構。數據結構（從概念到實現） 清華大學出版社隨處可見的樹結構隨處可見的樹結構例 4 日常生活中隨處可見的樹結構。數據結構（從概念到實現） 清華大學出版社隨處可見的樹結構隨處可見的樹結構例 4 日常生活中隨處可見的樹結構。吉林省市區(qū)街道朝陽南關二道高新寬城綠園雙陽九臺湖西桂林永昌紅旗清和吉林長春四平通化遼源松原白城白山延邊數據結構（從概念到實現） 清華大學出版社知識樹知識樹數據結構（從概念到實現） 清華大學出版社思維導圖思維導圖數據結構（從概念到實現） 清華大學出版社關于樹結構關于樹結構什么是樹？在邏輯上有什么特點

3、？有哪些基本術語？如何存儲樹結構？什么是二叉樹？在邏輯上有什么特點？有哪些基本性質？如何存儲二叉樹？如何實現二叉樹的遍歷操作？最優(yōu)二叉樹及應用樹與森林5-2-1 樹的定義和基本術語v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社12樹和森林的概念樹和森林的概念兩種樹：自由樹與有根樹。兩種樹：自由樹與有根樹。自由樹自由樹：一棵自由樹一棵自由樹 Tf 可定義為一個二元組可定義為一個二元組 Tf = (V, E) 其中其中V = v1, ., vn 是由是由 n (n0) 個元素組成個元素組成的有限非空集合，稱為頂點集合。的有限非空集合，稱為頂點集合。E = (vi, vj) | vi,

4、 vj V, 1i, jn 是是n-1個序對的集合，稱個序對的集合，稱為邊集合，為邊集合，E 中的元素中的元素 (vi, vj）稱為邊或分支。）稱為邊或分支。數據結構（從概念到實現） 清華大學出版社13自由樹有根樹有根樹：一棵有根樹一棵有根樹 T，簡稱為樹，它是，簡稱為樹，它是n (n0) 個結個結點的有限集合。當點的有限集合。當n = 0時，時，T 稱為空樹；否稱為空樹；否則，則，T 是非空樹，記作是非空樹，記作 數據結構（從概念到實現） 清華大學出版社樹的定義樹的定義樹：n（n0）個結點的有限集合數據元素樹的定義是采用遞歸方法 ，當 n0 時，稱為空樹；任意一棵非空樹 T 滿足以下條件：（

5、1）有且僅有一個特定的稱為根的結點；（2）當 n1 時，除根結點之外的其余結點被分成 m（m 0）個互不相交的有限集合 T1,T2, , Tm，其中每個集合又是一棵樹，并稱為這個根結點的子樹。數據結構（從概念到實現） 清華大學出版社ACBGFEDHIACBGFDACBGFDE互不相交的具體含義是什么？結點：結點不能屬于多個子樹邊：子樹之間不能有關系互不相交沒有回路樹的邏輯特征樹的邏輯特征樹結構具有層次性數據結構（從概念到實現） 清華大學出版社16樹的基本術語樹的基本術語子女子女：若結點的子樹非空，結點子樹的根即：若結點的子樹非空，結點子樹的根即為該結點的子女。為該結點的子女。雙親雙親：若結點有

6、子女，該結點是子女雙親。：若結點有子女，該結點是子女雙親。1層2層4層3層depth= 4DACBIJHGFEMLKheight= 4數據結構（從概念到實現） 清華大學出版社17兄弟兄弟：同一結點的子女互稱為兄弟。：同一結點的子女互稱為兄弟。度度：結點的子女個數即為該結點的度；樹中：結點的子女個數即為該結點的度；樹中各個結點的度的最大值稱為各個結點的度的最大值稱為樹的度樹的度。分支結點分支結點：度不為：度不為0的結點即為分支結點，的結點即為分支結點，亦稱為非終端結點。亦稱為非終端結點。葉結點葉結點：度為：度為0的結點即為葉結點，亦稱為的結點即為葉結點，亦稱為終端結點。終端結點。祖先祖先：某結點

7、到根結點的路徑上的各個結點：某結點到根結點的路徑上的各個結點都是該結點的祖先。都是該結點的祖先。子孫子孫：某結點的所有下屬結點，都是該結點：某結點的所有下屬結點，都是該結點的子孫。的子孫。數據結構（從概念到實現） 清華大學出版社18結點的層次結點的層次：規(guī)定根結點在第一層，其子女：規(guī)定根結點在第一層，其子女結點的層次等于它的層次加一。以下類推。結點的層次等于它的層次加一。以下類推。深度深度：結點的深度即為結點的層次；離根最：結點的深度即為結點的層次；離根最遠結點的層次即為遠結點的層次即為樹的深度樹的深度。1層2層4層3層depth= 4DACBIJHGFEMLKheight= 4數據結構（從概

8、念到實現） 清華大學出版社19高度高度：規(guī)定葉結點的高度為：規(guī)定葉結點的高度為1，其雙親結點，其雙親結點的高度等于它的高度加一。的高度等于它的高度加一。樹的高度樹的高度：等于根結點的高度，即根結點所：等于根結點的高度，即根結點所有子女高度的最大值加一。有子女高度的最大值加一。有序樹有序樹：樹中結點的各棵子樹：樹中結點的各棵子樹 T0, T1, 是有是有次序的，即為有序樹。次序的，即為有序樹。無序樹無序樹：樹中結點的各棵子樹之間的次序是：樹中結點的各棵子樹之間的次序是不重要的，可以互相交換位置。不重要的，可以互相交換位置。森林森林：森林是：森林是m（m0）棵樹的集合。）棵樹的集合。 數據結構（從

9、概念到實現） 清華大學出版社樹的基本術語樹的基本術語ACBGFEDHI雙親：這個結點稱為它孩子結點的雙親結點孩子：樹中某結點子樹的根結點稱為這個結點的孩子結點兄弟：具有同一個雙親的孩子結點互稱為兄弟a1ana2ai-1ai在線性結構中，邏輯關系表現為前驅后繼在樹結構中，邏輯關系表現為雙親孩子數據結構（從概念到實現） 清華大學出版社樹的基本術語樹的基本術語ACBGFEDHI路徑：結點序列 n1, n2, , nk 稱為一條由 n1 至 nk 的路徑，當且僅當滿足如下關系：結點 ni 是 ni+1 的雙親（1=ik）路徑長度：路徑上經過的邊的個數在樹結構中，路徑是唯一的在線性結構中，邏輯關系表現為

10、前驅后繼在樹結構中，邏輯關系表現為雙親孩子數據結構（從概念到實現） 清華大學出版社樹的基本術語樹的基本術語ACBGFEDHI樹的寬度：樹中每一層結點個數的最大值深度=4寬度=4數據結構（從概念到實現） 清華大學出版社線性結構和樹結構的比較線性結構和樹結構的比較開始結點（只有一個）:無前驅根結點（只有一個）:無雙親終端結點（只有一個）:無后繼葉子結點(可以有多個):無孩子其它元素：一個前驅,一個后繼其它結點：一個雙親,多個孩子一對一 一對多ACBGFEDHIa1ana2ai-1ai線性結構樹結構5-2-2 樹的抽象數據類型定義v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社樹的抽象數

11、據類型定義樹的抽象數據類型定義樹的應用很廣泛，在不同的實際應用中，樹的基本操作不盡相同ADT TreeDataModel 樹由一個根結點和若干棵子樹構成，樹中結點具有層次關系Operation InitTree：初始化一棵樹 DestroyTree：銷毀一棵樹 PreOrder：前序遍歷樹 PostOrder：后序遍歷樹 LeverOrder：層序遍歷樹endADT簡單起見，只討論樹的遍歷數據結構（從概念到實現） 清華大學出版社26樹的抽象數據類型樹的抽象數據類型template class Tree /對象對象: 樹是由樹是由n (0) 個結點組成的有限集合。在個結點組成的有限集合。在/類界

12、面中的類界面中的 position 是樹中結點的地址。在順序是樹中結點的地址。在順序/存儲方式下是下標型存儲方式下是下標型, 在鏈表存儲方式下是指針在鏈表存儲方式下是指針/型。型。T 是樹結點中存放數據的類型是樹結點中存放數據的類型, 要求所有結要求所有結/點的數據類型都是一致的。點的數據類型都是一致的。public: Tree (); Tree (); 27 BuildRoot (const T& value); /建立樹的根結點 position FirstChild(position p); /返回 p 第一個子女地址, 無子女返回 0 position NextSibling(

13、position p); /返回 p 下一兄弟地址, 若無下一兄弟返回 0 position Parent(position p); /返回 p 雙親結點地址, 若 p 為根返回 0 T getData(position p); /返回結點 p 中存放的值 bool InsertChild(position p, T& value); /在結點 p 下插入值為 value 的新子女, 若插 /入失敗, 函數返回false, 否則返回true28 bool DeleteChild (position p, int i); /刪除結點 p 的第 i 個子女及其全部子孫結 /點, 若刪除失敗

14、, 則返回false, 否則返回true void DeleteSubTree (position t); /刪除以 t 為根結點的子樹 bool IsEmpty (); /判樹空否, 若空則返回true, 否則返回false void Traversal (void (*visit)(position p); /遍歷以 p 為根的子樹; 5-4-1 二叉樹的定義v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社二叉樹的定義二叉樹的定義二叉樹： n（n0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

15、二叉樹是度為 2 的樹嗎？AB二叉樹是度小于等于 2 的樹嗎？ABACBDEFG數據結構（從概念到實現） 清華大學出版社31LLRR二叉樹二叉樹 (Binary Tree)(Binary Tree)二叉樹的定義二叉樹的定義一棵二叉樹是結點的一個有限集合，該集合一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根結點加上兩棵分或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉別稱為左子樹和右子樹的、互不相交的二叉樹組成。樹組成。數據結構（從概念到實現） 清華大學出版社二叉樹的特點二叉樹的特點ACBDEFG二叉樹有什么特點？（1）每個結點最多有兩棵子樹（2）二叉

16、樹是有序的，其次序不能任意顛倒 為什么要研究二叉樹？（1）二叉樹是最簡單的樹結構（2）將樹轉換為二叉樹， 從而利用二叉樹解決樹的有關問題數據結構（從概念到實現） 清華大學出版社斜樹斜樹斜樹：左斜樹和右斜樹的統(tǒng)稱左斜樹：所有結點都只有左子樹的二叉樹ABD右斜樹：所有結點都只有右子樹的二叉樹ABD斜樹有什么特點呢？（1）每一層只有一個結點（2）結點個數與其深度相同斜樹是樹結構的特例，是從樹結構退化成了線性結構數據結構（從概念到實現） 清華大學出版社滿二叉樹滿二叉樹滿二叉樹：所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上的二叉樹ABCDEFHIJKLMNOGABCDEFLMG所有分支結點

17、都有左右子樹，但葉子不在同一層上數據結構（從概念到實現） 清華大學出版社滿二叉樹滿二叉樹滿二叉樹：所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上的二叉樹滿二叉樹有什么特點呢？（1）葉子只能出現在最下一層滿二叉樹是樹結構的特例，是最豐滿的二叉樹ABCDEFHIJKLMNOG（4）在同樣深度的二叉樹中葉子結點個數最多（2）只有度為 0 和度為 2 的結點（3）在同樣深度的二叉樹中結點個數最多數據結構（從概念到實現） 清華大學出版社L完全二叉樹完全二叉樹完全二叉樹：在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點得到的二叉樹ABCDEFHIJKMNOGABCDEFHIJKMG5-4-

18、2 二叉樹的基本性質v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社二叉樹的性質二叉樹的性質性質 5-1：在一棵二叉樹中，如果葉子結點數為 n0，度為 2 的結點數為 n2，則有: n0n21ACBE證明: 設 n 為二叉樹的結點總數，n1 為二叉樹中度為 1 的結點數，則有： nn0n1n2 在二叉樹中，除了根結點外，其余結點都有唯一的一個分枝進入，一個度為 1 的結點射出一個分枝，一個度為 2 的結點射出兩個分枝，所以有： nn12n21因此可以得到： n0n21 數據結構（從概念到實現） 清華大學出版社二叉樹的性質二叉樹的性質性質 5-2：二叉樹的第 i 層上最多有2i-1個

19、結點（i1）證明：采用歸納法證明。當 i = 1時，只有一個根結點，而 2i-1 = 20 =1，結論成立。假設 i = k 時結論成立，即第 k 層上最多有 2k -1 個結點?？紤] i = k+1 時的情形。由于第 k+1 層上的結點是第 k 層上結點的孩子，而二叉樹中每個結點最多有兩個孩子，故在第 k+1 層上的最多大結點個數有 22k-12k 個結點，則在 i = k+1時結論也成立。由此，結論成立。數據結構（從概念到實現） 清華大學出版社二叉樹的性質二叉樹的性質性質 5-3：一棵深度為 k 的二叉樹中，最多有 2k -1個結點證明：設深度為 k 的二叉樹中結點個數最多為 n，則深度為

20、 k 且具有 2k-1個結點的二叉樹一定是滿二叉樹數據結構（從概念到實現） 清華大學出版社二叉樹的性質二叉樹的性質性質 5-4：具有 n 個結點的完全二叉樹的深度為 log2n +1證明：設具有 n 個結點的完全二叉樹的深度為 k，則2k-1-12k-12k-1第k層第k-1層層對不等式取對數，有： k-1 log2nk即： log2nk log2n+1由于 k 是整數，故必有 k log2n +1數據結構（從概念到實現） 清華大學出版社二叉樹的性質二叉樹的性質性質 5-5：對一棵具有 n 個結點的完全二叉樹中從 1 開始按層序編號，對于任意的序號為 i（1in）的結點（簡稱結點 i），有：

21、（1）如果 i1，則結點 i 的雙親結點的序號為 i/2，否則結點 i 無雙親結點（2）如果 2in，則結點 i 的左孩子的序號為 2i，否則結點 i 無左孩子（3）如果 2i+1n，則結點 i 的右孩子的序號為2i+1，否則結點 i 無右孩子123456891075-4-3 二叉樹的抽象數據類型定義v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社二叉樹的抽象數據類型定義二叉樹的抽象數據類型定義ADT BiTreeDataModel 二叉樹由一個根結點和兩棵互不相交的左右子樹構成，結點具有層次關系Operation InitBiTree：初始化一棵空的二叉樹 CreatBiTree

22、：建立一棵二叉樹 DestroyBiTree：銷毀一棵二叉樹 PreOrder：前序遍歷二叉樹 InOrder：中序遍歷二叉樹 PostOrder：后序遍歷二叉樹 LeverOrder：層序遍歷二叉樹endADT簡單起見，只討論二叉樹的遍歷數據結構（從概念到實現） 清華大學出版社45二叉樹的抽象數據類型二叉樹的抽象數據類型template class BinaryTree /對象: 結點的有限集合, 二叉樹是有序樹public: BinaryTree ();/構造函數 BinaryTree (BinTreeNode *lch, BinTreeNode *rch, T item); /構造函數,

23、 以item為根, lch和rch為左、右子 /樹構造一棵二叉樹 int Height ();/求樹深度或高度 int Size ();/求樹中結點個數數據結構（從概念到實現） 清華大學出版社46 bool IsEmpty ();/判二叉樹空否？ BinTreeNode *Parent (BinTreeNode *t);/求結點 t 的雙親 BinTreeNode *LeftChild (BinTreeNode *t); /求結點 t 的左子女 BinTreeNode *RightChild (BinTreeNode *t);/求結點 t 的右子女 bool Insert (T item);/

24、在樹中插入新元素 bool Remove (T item);/在樹中刪除元素 bool Find (T& item);/判斷item是否在樹中 bool getData (T& item);/取得結點數據數據結構（從概念到實現） 清華大學出版社47 BinTreeNode *getRoot ();/取根 void preOrder (void (*visit) (BinTreeNode *t);/前序遍歷, visit是訪問函數 void inOrder (void (*visit) (BinTreeNode *t);/中序遍歷, visit是訪問函數 void postOrd

25、er (void (*visit) (BinTreeNode *t);/后序遍歷, (*visit)是訪問函數 void levelOrder (void (*visit)(BinTreeNode *t);/層次序遍歷, visit是訪問函數;數據結構（從概念到實現） 清華大學出版社二叉樹的遍歷二叉樹的遍歷二叉樹的遍歷：從根結點出發(fā)，按照某種次序訪問樹中所有結點，并且每個結點僅被訪問一次 抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數據限定先左后右：前序、中序、后序根結點D左子樹L右子樹R二叉樹按照什么次序對二叉樹進行遍歷呢？二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RD

26、L、RLD 層序遍歷：按二叉樹的層序編號的次序訪問各結點 數據結構（從概念到實現） 清華大學出版社中序遍歷中序遍歷若二叉樹為空，則空操作返回；否則：（1）中序遍歷根結點的左子樹（2）訪問根結點（3）中序遍歷根結點的右子樹ACBDEFG中序遍歷序列：D G B A E C F數據結構（從概念到實現） 清華大學出版社前序遍歷前序遍歷若二叉樹為空，則空操作返回；否則：（1）訪問根結點（2）前序遍歷根結點的左子樹（3）前序遍歷根結點的右子樹ACBDEFG前序遍歷序列：A B D G C E F數據結構（從概念到實現） 清華大學出版社后序遍歷后序遍歷若二叉樹為空，則空操作返回；否則：（1）后序遍歷根結點

27、的左子樹（2）后序遍歷根結點的右子樹（3）訪問根結點ACBDEFG后序遍歷序列：G D B E F C A數據結構（從概念到實現） 清華大學出版社層序遍歷層序遍歷從二叉樹的根結點開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問ACBDEFG層序遍歷序列：A B C D E F G數據結構（從概念到實現） 清華大學出版社53寫出右樹的前序、中序和后序序列寫出右樹的前序、中序和后序序列前序：前序：- + a b * - c d / e f中序：中序：a+b * c-d e/f后序：后序：a b c d - * + e f / -隨堂練習隨堂練習數據結構（從概念到實現） 清華大學

28、出版社54二叉樹遞歸的中序遍歷算法二叉樹遞歸的中序遍歷算法template void BinaryTree:InOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍歷左子樹 visit (subTree);/訪問根結點 InOrder (subTree-rightChild, visit); /遍歷右子樹 ;數據結構（從概念到實現） 清華大學出版社55二叉樹遞歸的前序遍歷算法二叉樹遞歸的前序遍歷算法templ

29、ate void BinaryTree:PreOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree);/訪問根結點PreOrder (subTree-leftChild, visit); /遍歷左子樹PreOrder (subTree-rightChild, visit); /遍歷右子樹 ;數據結構（從概念到實現） 清華大學出版社56二叉樹遞歸的后序遍歷算法二叉樹遞歸的后序遍歷算法template void BinaryTree:PostOrder (Bi

30、nTreeNode * subTree, void (*visit) (BinTreeNode *t ) if (subTree != NULL ) PostOrder (subTree-leftChild, visit); /遍歷左子樹PostOrder (subTree-rightChild, visit); /遍歷右子樹visit (subTree); /訪問根結點 ;數據結構（從概念到實現） 清華大學出版社57訪問樹中的結點的數據域訪問樹中的結點的數據域實際等于實際等于visit（t-data）根據實際需要，可以在根據實際需要，可以在visit中，將每個結點的中，將每個結點的data值

31、返回值返回visit函數數據結構（從概念到實現） 清華大學出版社58層次序遍歷的（非遞歸）算法層次序遍歷的（非遞歸）算法template void BinaryTree:levelOrder (void (*visit) (BinTreeNode *t) if (root = NULL) return; QueueBinTreeNode * Q; BinTreeNode *p = root; visit (p); Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if (p-leftChild != NULL) 數據結構（從概念到實現） 清華

32、大學出版社59 visit (p-leftChild); Q.EnQueue (p-leftChild); if (p-rightChild != NULL) visit (p-rightChild); Q.EnQueue (p-rightChild); ;數據結構（從概念到實現） 清華大學出版社二叉樹的前序遍歷二叉樹的前序遍歷- -課后閱讀課后閱讀template void BiTree : PreOrder(BiNode *bt) if (bt = nullptr) return; /遞歸調用的結束條件 else cout data; /訪問根結點bt的數據域 PreOrder(bt-lc

33、hild); /前序遞歸遍歷bt的左子樹 PreOrder(bt-rchild); /前序遞歸遍歷bt的右子樹 按照先左后右的方式掃描二叉樹，區(qū)別僅在于訪問結點的時機LR數據結構（從概念到實現） 清華大學出版社ACBDPre(*A) （1）A Pre(A-lchild); Pre(*B) （2）B Pre(B-lchild); Pre() Pre(*D) （3）D Pre(D-lchild); Pre() Pre() Pre(B-rchild); Pre(D-rchild); 約定：*A 表示根指針指向結點 Aif (bt = nullptr) return; else cout data;

34、PreOrder(bt-lchild); PreOrder(bt-rchild); 二叉樹的中序遍歷二叉樹的中序遍歷- -課后閱讀課后閱讀數據結構（從概念到實現） 清華大學出版社ACBDPre(*A) （1）A Pre(A-lchild); Pre(*B) （2）B Pre(B-lchild); Pre() Pre(*D) （3）D Pre(D-lchild); Pre() Pre() Pre(B-rchild); Pre(D-rchild); Pre() Pre() Pre(*C) （4）C Pre(C-lchild); Pre(A-rchild); Pre(C-rchild); 得到前序序

35、列：A B D Cif (bt = nullptr) return; else cout data; PreOrder(bt-lchild); PreOrder(bt-rchild); 二叉樹的前序遍歷二叉樹的前序遍歷- -課后閱讀課后閱讀數據結構（從概念到實現） 清華大學出版社遍歷序列：遍歷序列：AAB CBDCE F GD E F GACBDEFG1. 隊列 Q 初始化；2. 如果二叉樹非空，將根指針入隊；入隊入隊出隊出隊 3.3 若結點 q 存在左孩子，則將左孩子指針入隊； 3.4 若結點 q 存在右孩子，則將右孩子指針入隊；3. 循環(huán)直到隊列 Q 為空 3.1 q = 隊列 Q 的隊頭

36、元素出隊； 3.2 訪問結點 q 的數據域； 二叉樹的層序遍歷二叉樹的層序遍歷- -課后閱讀課后閱讀數據結構（從概念到實現） 清華大學出版社template void BiTree : LeverOrder( ) BiNode *Q100, *q = nullptr; int front = -1, rear = -1; if (root = nullptr) return; Q+rear = root; while (front != rear) q = Q+front; cout data; if (q-lchild != nullptr) Q+rear = q-lchild; if (q

37、-rchild != nullptr) Q+rear = q-rchild; 時間復雜度？每個結點進隊出隊一次O(n)O(n)二叉樹的層序遍歷二叉樹的層序遍歷- -課后閱讀課后閱讀數據結構（從概念到實現） 清華大學出版社#include #include #include #include using namespace std; templatestruct BiNode /二叉樹結點 T value; BiNode *pLeft; BiNode *pRight; BiNode() : pLeft(NULL), pRight(NULL) ; templatestruct BiNodeAux

38、BiNode *pNode; bool hasVisited; BiNodeAux(BiNode *_node, bool _vis) : pNode(_node), hasVisited(_vis) ; templatevoid PreOrderRecursively(BiNode *pRoot) if (pRoot = NULL) return; cout value pLeft); PreOrder(pRoot-pRight); templatevoid PreOrder(BiNode *pRoot) if (pRoot = NULL) return; stackBiNodeAux s;

39、 BiNode *pCur = pRoot; while (pCur != NULL | !s.empty() if (pCur != NULL) cout value t; s.push(BiNodeAux(pCur, false); pCur = pCur-pLeft; else if (s.top().hasVisited = true) s.pop(); else s.top().hasVisited = true; pCur = s.top().pNode-pRight; templatevoid InOrderRecursively(BiNode *pRoot) if (pRoot

40、 != NULL) InOrderRecursively(pRoot-pLeft); cout value pRight); templatevoid InOrder(BiNode *pRoot) if (pRoot = NULL) return; stackBiNode* s; BiNode *pCur = pRoot; while (pCur != NULL | !s.empty() if (pCur != NULL) s.push(pCur); pCur = pCur-pLeft; else cout value pRight; s.pop(); templatevoid PostOrd

41、erRecursively(BiNode *pRoot) if (pRoot != NULL) PostOrderRecursively(pRoot-pLeft); PostOrderRecursively(pRoot-pRight); cout value t; templatevoid PostOrder(BiNode *pRoot) if (pRoot = NULL) return; stackBiNodeAux s; BiNode *pCur = pRoot; while (pCur != NULL | !s.empty() if (pCur != NULL) s.push(BiNod

42、eAux(pCur, false); pCur = pCur-pLeft; else if (s.top().hasVisited = false) s.top().hasVisited = true; pCur = s.top().pNode-pRight; else cout value t; s.pop(); templatevoid LevelOrder(BiNode *pRoot) if (pRoot = NULL) return; queueBiNode* q; BiNode *pCur = pRoot; q.push(pCur); while (!q.empty() pCur =

43、 q.front(); cout value pLeft != NULL) q.push(pCur-pLeft); if (pCur-pRight != NULL) q.push(pCur-pRight); int main() BiNode nodes7; for (int i = 0; i 7; +i) nodesi.value = i + 1; nodes0.pLeft = &nodes1; nodes0.pRight = &nodes2; nodes1.pLeft = &nodes3; nodes1.pRight = &nodes4; nodes2.pL

44、eft = &nodes5; nodes2.pRight = &nodes6; cout 建立一個三層滿二叉樹成功! endl endl; cout 遞歸前序遍歷該二叉樹的結果為：endl; PreOrderRecursively(&nodes0); cout endl; cout 非遞歸前序遍歷該二叉樹的結果為：endl; PreOrder(&nodes0); cout endl endl; cout 遞歸中序遍歷該二叉樹的結果為：endl; InOrderRecursively(&nodes0); cout endl; cout 非遞歸中序遍歷該二叉

45、樹的結果為：endl; InOrder(&nodes0); cout endl endl; cout 遞歸后序遍歷該二叉樹的結果為：endl; PostOrderRecursively(&nodes0); cout endl; cout 非遞歸后序遍歷該二叉樹的結果為：endl; PostOrder(&nodes0); cout endl endl; cout 層序遍歷該二叉樹的結果為：endl; LevelOrder(&nodes0); cout endl ; system(pause); return 0;二叉樹的遍歷二叉樹的遍歷- -代碼示意代碼示意數據結

46、構（從概念到實現） 清華大學出版社遍歷與二叉樹遍歷與二叉樹若已知一棵二叉樹的前序（或中序，或后序，或層序）序列，能否唯一確定這棵二叉樹呢？ABCABC前序遍歷序列：A B C若已知一棵二叉樹的前序序列和后序序列，能否唯一確定這棵二叉樹呢？后序遍歷序列：C B A數據結構（從概念到實現） 清華大學出版社由先序序列和中序序列恢復二叉樹：由先序序列和中序序列恢復二叉樹：（1）由先序序列得到二叉樹的根結點；）由先序序列得到二叉樹的根結點；（2）由上述（）由上述（1）的根結點把中序序列分為左子樹）的根結點把中序序列分為左子樹的中序序列和右子樹的中序序列兩個部分；的中序序列和右子樹的中序序列兩個部分；（3

47、）根據上述左子樹的中序序列個數找到對應的左）根據上述左子樹的中序序列個數找到對應的左子樹先序序列和右子樹的先序序列；子樹先序序列和右子樹的先序序列；（4）按上述（）按上述（1）、（）、（2）、（）、（3）同樣的方法依次）同樣的方法依次類推，直到所得左、右子樹只含一個結點為止。類推，直到所得左、右子樹只含一個結點為止。數據結構（從概念到實現） 清華大學出版社示例：由先序序列示例：由先序序列ABCDEFGH和中序序列和中序序列CBEDAGHF恢復二叉樹：恢復二叉樹：方法：先序序列ABCDEFGH（注：A是根）中序序列CBEDAGHF左子樹左子樹右子樹右子樹ABCDEFGH以以A為根的左、為根的左、

48、右子樹先序序列右子樹先序序列示意圖示意圖數據結構（從概念到實現） 清華大學出版社由左子樹先序序列：由左子樹先序序列：BCDE和左子樹中序序列：和左子樹中序序列：CBED構造構造A的左子樹的左子樹同理，由右子樹先序序列：同理，由右子樹先序序列：FGH和右子樹中和右子樹中序序列序序列GHF構造構造A的右子樹：的右子樹： DABFC DEGHABFCEGH數據結構（從概念到實現） 清華大學出版社隨堂練習練習： 已知一棵二叉樹的中序序列為GDJHKBEACFMI，后序序列為GJKHDEBMIFCA，試畫出該二叉樹 已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，試畫出該二叉樹 數據

49、結構（從概念到實現） 清華大學出版社隨堂練習練習-重構二叉樹：1. DJGBAHECKIMLF（中序） JGDBHEKMLIFCA（后序）2.ABCDEFGHI（層序）BFDGAEHIC（中序）數據結構（從概念到實現） 清華大學出版社l若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；l若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；l左、右子樹也分別為二叉排序樹；l沒有鍵值相等的結點。二叉排序樹二叉排序樹數據結構（從概念到實現） 清華大學出版社二叉排序樹二叉排序樹lBSTBinary Search Treel若根結點的關鍵字值等于查找的關鍵字，成功。l否則，若小于根結點的關

50、鍵字值，遞歸查左子樹。l若大于根結點的關鍵字值，遞歸查右子樹。l若子樹為空，查找不成功。數據結構（從概念到實現） 清華大學出版社二叉排序樹二叉排序樹l新插入的結點一定是一個新添加的葉子結點l并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。數據結構（從概念到實現） 清華大學出版社二叉排序樹二叉排序樹l要刪除的結點不存在，刪除失敗l待刪除結點為葉子節(jié)點，直接刪除l待刪除結點左孩子或右孩子為空，用非空孩子代替被刪除結點l待刪除結點有左、右孩子，找到待刪結點待刪結點的右子樹中的最小結點的右子樹中的最小結點，將最小結點的值賦給要刪除的結點，然后刪除最小結點第四種情況 刪除25數據結構

51、（從概念到實現） 清華大學出版社二叉排序樹二叉排序樹l中序序列有什么特征？ 8 6 10 4 7 6 4 8 7 10數據結構（從概念到實現） 清華大學出版社平衡二叉樹平衡二叉樹 1 2 3 4 5 5 4 3 2 1 3 2 4 1 5 數據結構（從概念到實現） 清華大學出版社平衡二叉樹平衡二叉樹 理論上，當二叉搜索樹是一顆完全二叉樹時，查找最高效刻意構造BST為完全二叉樹，代價太高引入平衡因子任意結點的左右子樹的高度差任意節(jié)點的平衡因子滿足|rightchild=rc-liftchild;P-liftchild=g;G-parent-left/right child=p;G-parent=

52、PT1-parent=g;數據結構（從概念到實現） 清華大學出版社平衡二叉樹平衡二叉樹rc=p;g-liftchild=p-rightchild；p-rightchild=g;G-parent-left/right child=p;G-parent=p;g-liftchild-parent=g;數據結構（從概念到實現） 清華大學出版社平衡二叉樹平衡二叉樹5-5-1 二叉樹的順序存儲結構v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社二叉樹的順序存儲結構二叉樹的順序存儲結構順序存儲結構的要求是什么？用一組連續(xù)的存儲單元依次存儲數據元素，由存儲位置表示元素之間的邏輯關系如何利用數組下標

53、來反映結點之間的邏輯關系?完全二叉樹中結點的編號可以唯一地反映結點之間的邏輯關系 二叉樹的順序存儲結構是用一維數組存儲二叉樹的結點，結點的存儲位置（下標）應能體現結點之間的邏輯關系父子關系 數據結構（從概念到實現） 清華大學出版社二叉樹的順序存儲結構二叉樹的順序存儲結構ABCDEFHIJ編號為下標 A1 2 3 4 5 6 7 8 9 10 B C D E F G H I Jconst MaxSize = 100;template struct SeqBiTree DataType dataMaxSize; int biTreeNum; ;如何定義二叉樹的順序存儲結構

54、呢？數據結構（從概念到實現） 清華大學出版社二叉樹的順序存儲結構二叉樹的順序存儲結構ABCDFEG152361310以編號為下標 A1 2 3 4 5 6 7 8 9 10 11 12 13 B C D F E G將二叉樹按完全二叉樹編號：（1）根結點的編號為 1（2）若某結點 i 有左孩子，則其左孩子的編號為 2i（3）若某結點 i 有右孩子，則其右孩子的編號為 2i+1對于普通的二叉樹，如何順序存儲呢？數據結構（從概念到實現） 清華大學出版社二叉樹的順序存儲結構二叉樹的順序存儲結構二叉樹的順序存儲結構一般僅存儲完全二叉樹順序存儲一棵右斜樹會發(fā)生什么情況？ACOG缺點：浪費存儲空間5-5-2

55、 二叉鏈表v第五章 樹和二叉樹數據結構（從概念到實現） 清華大學出版社如何用鏈接存儲方式存儲二叉樹呢？ACBDEFGfirsta1a2an二叉鏈表：二叉樹的每個結點對應一個鏈表結點，鏈表結點存放結點的數據信息和指示左右孩子的指針二叉鏈表的存儲方法二叉鏈表的存儲方法 lchild data rchild數據結構（從概念到實現） 清華大學出版社二叉鏈表的存儲方法二叉鏈表的存儲方法ACBDEFGGFEDBCAroot數據結構（從概念到實現） 清華大學出版社二叉鏈表的存儲結構定義二叉鏈表的存儲結構定義GFEDBACtemplate struct BiNode DataType data; BiNode

56、 *lchild, *rchild;葉子結點的標志？左右孩子指針均為空root數據結構（從概念到實現） 清華大學出版社二叉鏈表的存儲結構定義二叉鏈表的存儲結構定義GFEDBACn 個結點的二叉鏈表有多少個空指針？2n-(n-1) = n+1 個空指針roottemplate struct BiNode DataType data; BiNode *lchild, *rchild;數據結構（從概念到實現） 清華大學出版社三叉鏈表的存儲方法三叉鏈表的存儲方法GFEDBAC如何查找雙親？時間性能？O(n)在二叉鏈表中增加一個指向雙親的指針域 lchild data parent rchildroot

57、數據結構（從概念到實現） 清華大學出版社三叉鏈表的存儲方法三叉鏈表的存儲方法A BDEFCGACBDEFGroot數據結構（從概念到實現） 清華大學出版社二叉鏈表的類定義二叉鏈表的類定義二叉樹的抽象數據類型定義？template class BiTreepublic: BiTree( )root = Creat(root); BiTree( )Release(root); void PreOrder( )PreOrder(root); void InOrder( )InOrder(root); void PostOrder( )PostOrder(root); void LeverOrder(

58、 ); private: BiNode *Creat(BiNode *bt); void Release(BiNode *bt); void PreOrder(BiNode *bt); void InOrder(BiNode *bt); void PostOrder(BiNode *bt); BiNode *root; ;InitBiTree：初始化一棵空的二叉樹 CreatBiTree：建立一棵二叉樹 DestroyBiTree：銷毀一棵二叉樹PreOrder：前序遍歷二叉樹InOrder：中序遍歷二叉樹PostOrder：后序遍歷二叉樹LeverOrder：層序遍歷二叉樹數據結構（從概念到

59、實現） 清華大學出版社雙親表示法雙親表示法如何定義樹的雙親表示法?012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parenttemplate struct PNode DataType data; int parent; ;數據結構（從概念到實現） 清華大學出版社遍歷將二叉樹審視一遍，將非線性結構轉換為線性結構遍歷是二叉樹各種操作的基礎，可以在遍歷的過程中建立一棵二叉樹LR在內存中建立一棵二叉鏈表，如何輸入二叉樹的信息？二叉鏈表的建立二叉鏈表的建立數據結構（從概念到實現） 清華大學出版社如何由一種遍歷序列生成該二叉樹？ACBD擴展二

60、叉樹的前序遍歷序列：A B # D # # C # #擴展二叉樹：將二叉樹中每個結點的空指針引出一個虛結點，其值為一特定值如 #ACBD#二叉鏈表的建立二叉鏈表的建立數據結構（從概念到實現） 清華大學出版社二叉鏈表的建立二叉鏈表的建立template BiNode *BiTree : Creat(BiNode *bt) char ch; cin ch; /輸入結點的數據信息，假設為字符 if (ch = #) bt = nullptr; /建立一棵空樹 else bt = new BiNode; bt-data = ch; bt-lchild = Creat(bt-lchild); /遞歸建立左子樹 bt-rchild = Creat(bt-rchild); /遞歸建立右子樹 return bt;數據結構（從概念到實現）