數(shù)據(jù)結(jié)構(gòu)樹和二叉樹課件

1、數(shù)據(jù)結(jié)構(gòu)樹和二叉樹第六章第六章樹和二叉樹樹和二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。前面幾數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。前面幾章主要研究的是線性結(jié)構(gòu)。一般的，線性結(jié)構(gòu)只能用來描章主要研究的是線性結(jié)構(gòu)。一般的，線性結(jié)構(gòu)只能用來描述數(shù)據(jù)元素之間的線性順序關(guān)系，而很難反映元素之間的述數(shù)據(jù)元素之間的線性順序關(guān)系，而很難反映元素之間的層次層次( (分支分支) )關(guān)系。本章將要討論一種非線性數(shù)據(jù)結(jié)構(gòu)，所關(guān)系。本章將要討論一種非線性數(shù)據(jù)結(jié)構(gòu)，所謂非線性結(jié)構(gòu)是指在結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，它具謂非線性結(jié)構(gòu)是指在結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，它具有兩個(gè)或兩個(gè)以上的直接后繼或

2、直接前驅(qū)。有兩個(gè)或兩個(gè)以上的直接后繼或直接前驅(qū)。樹形結(jié)構(gòu)，是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，它用于樹形結(jié)構(gòu)，是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，它用于描述數(shù)據(jù)元素之間的層次關(guān)系。樹形結(jié)構(gòu)在客觀世界中廣描述數(shù)據(jù)元素之間的層次關(guān)系。樹形結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹來形象表示。經(jīng)常用到的兩種結(jié)構(gòu)是樹和二叉樹。來形象表示。經(jīng)常用到的兩種結(jié)構(gòu)是樹和二叉樹。本章先介紹樹、二叉樹的定義、性質(zhì)及存儲(chǔ)結(jié)構(gòu)，重點(diǎn)本章先介紹樹、二叉樹的定義、性質(zhì)及存儲(chǔ)結(jié)構(gòu)，重點(diǎn)討論二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作，并研究樹和森林與討論二叉樹的存儲(chǔ)結(jié)構(gòu)及

3、其各種操作，并研究樹和森林與二叉樹之間的轉(zhuǎn)換關(guān)系，最后介紹樹的應(yīng)用。二叉樹之間的轉(zhuǎn)換關(guān)系，最后介紹樹的應(yīng)用。 引 言數(shù)據(jù)結(jié)構(gòu)樹和二叉樹內(nèi)容提要 6.1 樹的定義和基本術(shù)語(yǔ)樹的定義和基本術(shù)語(yǔ) 6.2 二叉樹二叉樹 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 6.4 樹和森林樹和森林 6.6 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用 小結(jié)小結(jié)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.1 樹的定義樹的定義 和基本術(shù)語(yǔ)和基本術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 樹樹(Tree)(Tree)是包含是包含n(nn(n0)0)個(gè)結(jié)點(diǎn)的有限集。在任意個(gè)結(jié)點(diǎn)的有限集。在任意一棵一棵非空非空樹中：樹中： （1 1） 有且僅有一個(gè)特定的稱為有且僅

4、有一個(gè)特定的稱為根根(Root)(Root)的結(jié)點(diǎn)；的結(jié)點(diǎn)； (2) (2) 當(dāng)當(dāng)n1n1時(shí)，其余的結(jié)點(diǎn)可分為時(shí)，其余的結(jié)點(diǎn)可分為m(mm(m0)0)個(gè)個(gè)互不相交的子互不相交的子集集T T1 1,T,T2 2,T,T3 3T Tm m，其中每個(gè)子集又是一棵樹，并稱其為，其中每個(gè)子集又是一棵樹，并稱其為子子樹樹( (SubtreeSubtree) )。 樹也可以這樣定義：樹也可以這樣定義： 樹是由根結(jié)點(diǎn)和若干棵子樹構(gòu)成的。樹是由根結(jié)點(diǎn)和若干棵子樹構(gòu)成的?？梢钥闯?，在樹的定義中用了遞歸的概念，即在樹的定義可以看出，在樹的定義中用了遞歸的概念，即在樹的定義中又用到樹的定義，它道出了樹的固有特性，因此

5、遞歸算中又用到樹的定義，它道出了樹的固有特性，因此遞歸算法是樹結(jié)構(gòu)算法的顯著特點(diǎn)。法是樹結(jié)構(gòu)算法的顯著特點(diǎn)。 樹的定義數(shù)據(jù)結(jié)構(gòu)樹和二叉樹上圖上圖(a)(a)是只有一個(gè)根結(jié)點(diǎn)的樹；圖是只有一個(gè)根結(jié)點(diǎn)的樹；圖(b)(b)是有是有1313個(gè)結(jié)點(diǎn)的樹，個(gè)結(jié)點(diǎn)的樹，其中其中A A是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集：是根，其余結(jié)點(diǎn)分成三個(gè)互不相交的子集： T1=BT1=B，E E，F(xiàn) F，K K，LL，T2=CT2=C，GG，T3=DT3=D，H H，I I，J J，MM；T1T1、T2T2和和T3T3都是根都是根A A的子樹，且本身也是一棵樹。例如的子樹，且本身也是一棵樹。例如T1T1，其根為，其根為

6、B B，其，其余結(jié)點(diǎn)分為兩個(gè)互不相交的子集；余結(jié)點(diǎn)分為兩個(gè)互不相交的子集；T11=ET11=E，K K，LL，T12=FT12=F。T11T11和和T12T12都是都是B B的子樹。而的子樹。而T11T11中中E E是根結(jié)點(diǎn)，是根結(jié)點(diǎn)，KK和和LL是是E E的的兩棵互不相交的子樹，其本身又是只有一個(gè)根結(jié)點(diǎn)的樹。兩棵互不相交的子樹，其本身又是只有一個(gè)根結(jié)點(diǎn)的樹。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素

7、root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互個(gè)互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根root的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：ADT Tree數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(jié)點(diǎn) 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)

8、的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷數(shù)據(jù)結(jié)構(gòu)樹和二叉樹InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e

9、, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹插入為結(jié)點(diǎn)為根的樹插入為結(jié)點(diǎn)p的第的第i棵子樹棵子樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹棵子樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹樹的表示方法有四種，各用于不同的目的。樹的表示方法有四種，各用于不同的目的。(1) (1) 直觀表示法：就是一棵樹的直觀表

10、示。直觀表示法：就是一棵樹的直觀表示。(2) (2) 廣義表示法：下圖廣義表示法：下圖 (a)(a)是以廣義表的形式表示的，根作為是以廣義表的形式表示的，根作為由子樹森林組成的表的名字寫在表的左邊。樹的形式化表示法由子樹森林組成的表的名字寫在表的左邊。樹的形式化表示法主要用于樹的理論描述。主要用于樹的理論描述。(3) (3) 凹入表示法：下圖凹入表示法：下圖(b)(b)用的是凹入表示法用的是凹入表示法( (類似書的編目類似書的編目) )。樹的凹入表示法主要用于樹的屏幕和打印顯示。樹的凹入表示法主要用于樹的屏幕和打印顯示。(4(4）嵌套集合表示法：參見）嵌套集合表示法：參見P120P120圖圖6

11、.26.2。表示方法的多樣性，正說明了樹結(jié)構(gòu)在日常生活中及計(jì)算機(jī)表示方法的多樣性，正說明了樹結(jié)構(gòu)在日常生活中及計(jì)算機(jī)程序設(shè)計(jì)中的重要性。一般來說，分等級(jí)的分類方案都可用層程序設(shè)計(jì)中的重要性。一般來說，分等級(jí)的分類方案都可用層次結(jié)構(gòu)來表示，也就是說，都可產(chǎn)生一個(gè)樹結(jié)構(gòu)。次結(jié)構(gòu)來表示，也就是說，都可產(chǎn)生一個(gè)樹結(jié)構(gòu)。 樹的表示形式樹的表示形式數(shù)據(jù)結(jié)構(gòu)樹和二叉樹ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹根例如例如: :數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹基基 本本 術(shù)術(shù) 語(yǔ)語(yǔ)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹結(jié)點(diǎn)結(jié)點(diǎn): :結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :樹

12、的度樹的度: :葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :分支結(jié)點(diǎn)分支結(jié)點(diǎn): :數(shù)據(jù)元素及若干指向子樹的分支擁有的子樹數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM數(shù)據(jù)結(jié)構(gòu)樹和二叉樹(從根到結(jié)點(diǎn)的)路徑：路徑：結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :樹的深度：樹的深度： 由從根根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l 層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次孩子結(jié)點(diǎn)：結(jié)點(diǎn)子樹的根雙親結(jié)點(diǎn)：孩子結(jié)點(diǎn)的直接前驅(qū)兄弟結(jié)點(diǎn)：同一雙親的孩子間堂兄弟：雙親在同一層的結(jié)點(diǎn)祖先結(jié)點(diǎn)：從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)樹和二叉

13、樹() 有確定的根；() 樹根和子樹根之間為有向關(guān)系。有向樹：有向樹：有序樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：無序樹：子樹之間不存在確定的次序關(guān)系。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹任何一棵非空樹是一個(gè)二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點(diǎn) F 被稱為子樹森林森林：森林：是m（m0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF數(shù)據(jù)結(jié)構(gòu)樹和二叉樹對(duì)比對(duì)比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)

14、據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼)多個(gè)葉子結(jié)點(diǎn)多個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.2 二二 叉叉 樹樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.2.1 二叉樹的定義二叉樹的定義 二叉樹（二叉樹（Binary Tree）或?yàn)榭諛?，或是由一個(gè)）或?yàn)榭諛洌蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分別稱為根結(jié)點(diǎn)加上兩棵分別稱為左子樹左子樹和和右子樹右子樹的、的、互不相交的互不相交的二叉樹組成。二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹二叉

15、樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空樹只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹抽象數(shù)據(jù)類型二叉數(shù)定義ADT BinaryTree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 若若D = ，則，則R= ，稱稱BinaryTree為空二叉樹為空二叉樹; 若若D ，則，則R=H，H是如下二元關(guān)系：是如下二元關(guān)系： （1）在）在D中存在唯一的稱為中存在唯一的稱為根根的數(shù)據(jù)元素的數(shù)據(jù)元素root，它在關(guān)系，它在關(guān)系H下下無前驅(qū)無前

16、驅(qū)； (2)若若Droot，則存在，則存在Droot=DL，Dr, DLDr= ， (3)若若DL ,則則DL存在唯一的數(shù)據(jù)元素存在唯一的數(shù)據(jù)元素xL，有，有 H;H;且存在且存在DL上的關(guān)系上的關(guān)系HL H；若；若Dr，則，則D Dr r存在唯一的數(shù)據(jù)元存在唯一的數(shù)據(jù)元素素xr，有，有 H;H;且存在且存在Dr上的關(guān)系上的關(guān)系Hr H,H=，,HL,Hr; (4)（DL ,HL）是一棵符合本定義的二叉樹，稱為根）是一棵符合本定義的二叉樹，稱為根root的的左左子樹子樹，（，（Dr ,Hr）是一棵符合本定義的二叉樹，稱為根）是一棵符合本定義的二叉樹，稱為根root的的右子樹右子樹，數(shù)據(jù)結(jié)構(gòu)樹和

17、二叉樹二叉樹的主要基本操作二叉樹的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTra

18、verse(T, Visit();數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);數(shù)據(jù)結(jié)構(gòu)樹和二叉樹ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.2.2 二叉樹二叉樹 的性質(zhì)的性質(zhì)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 性質(zhì)性質(zhì)1 ： 在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。 (i1)用歸納法證明用歸納法證明： 歸納基歸納基

19、： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1；假設(shè)對(duì)所有的 j，1 j i，命題成立；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹性質(zhì)性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）。證明：證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 性質(zhì)性質(zhì) 3 ： 對(duì)任何一棵二叉樹，若它含有n0 個(gè)葉子結(jié)點(diǎn)、n2 個(gè)度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：n0 = n2+1。證明：證明：設(shè)設(shè)

20、 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹兩類兩類特殊特殊的二叉樹：的二叉樹：滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)編號(hào)為為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789 10 11 12 13 14 15abcdefghij數(shù)據(jù)結(jié)構(gòu)樹和二叉樹性質(zhì)性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度深度為 log2n +1 。證明：證明：

21、設(shè)設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 n 2k 即 k-1 log2 n n，則該結(jié)點(diǎn)無左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；(3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)蕉?、二叉樹的鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)一、一、 二叉樹的順序二叉樹的順序 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_

22、TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTree bt;一、一、 二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹按照順序存儲(chǔ)結(jié)構(gòu)的定義，在此約定，用一按照順序存儲(chǔ)結(jié)構(gòu)的定義，在此約定，用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)二叉樹上的結(jié)點(diǎn)元素。因此，必須把結(jié)右存儲(chǔ)二叉樹上的結(jié)點(diǎn)元素。因此，必須把結(jié)點(diǎn)安排成一個(gè)適當(dāng)?shù)木€性序列，使得結(jié)點(diǎn)在這點(diǎn)安排成一個(gè)適當(dāng)?shù)木€性序列，使得結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。關(guān)系。在一棵有在一棵有n n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，個(gè)

23、結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左到右地給結(jié)點(diǎn)編號(hào)，自上層到下層，每層從左到右地給結(jié)點(diǎn)編號(hào)，就能得到一個(gè)足以反映整個(gè)二叉樹結(jié)構(gòu)的線性就能得到一個(gè)足以反映整個(gè)二叉樹結(jié)構(gòu)的線性序列，如下圖所示。序列，如下圖所示。二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹練習(xí)練習(xí):ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326數(shù)據(jù)結(jié)構(gòu)樹和二叉樹二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線

24、索鏈表線索鏈表數(shù)據(jù)結(jié)構(gòu)樹和二叉樹ADEBCF rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):1. 1. 二叉鏈表二叉鏈表二叉鏈表二叉鏈表數(shù)據(jù)結(jié)構(gòu)樹和二叉樹ABCDEF二叉樹二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語(yǔ)言的類型描述如下語(yǔ)言的類型描述如下: :數(shù)據(jù)結(jié)構(gòu)樹和二叉樹ADEBCF root 2三叉鏈表三叉鏈表paren

25、t lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 typedef struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語(yǔ)言的類型描述如下語(yǔ)言的類型描述如下: :數(shù)據(jù)結(jié)構(gòu)樹和二叉樹0123456B2C0A -1D2E3F4 data parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):3 3雙親鏈表雙親

26、鏈表LRTagLRRRL數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodesMAX_TREE_SIZE; int num_node; / 結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置 BPTree數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.3.1二叉樹的遍歷二叉樹的遍歷6.3 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹數(shù)據(jù)結(jié)構(gòu)樹和二叉樹一、問題的提出一

27、、問題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 如何按著某條搜索路徑如何按著某條搜索路徑巡訪巡訪二叉二叉樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被均被訪問一次訪問一次，而且，而且僅被訪問一次僅被訪問一次。一、問題的提出一、問題的提出“訪問訪問”的含義可以很廣，如：輸出結(jié)的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。點(diǎn)的信息等。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 “遍歷遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)

28、均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索搜索路徑路徑遍歷的問題。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹二叉樹的遍歷方法二叉樹的遍歷方法 二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：令：L L：遍歷左子樹 D D：訪問根結(jié)點(diǎn) R R：遍歷右子樹 有六種遍歷方法： D DL LR R，L LD DR R，L LR RD D， D DR RL L，R RD DL L，R RL LD D 約定先左后右,有三種遍歷方法： D DL LR R、L LD DR R、L LR R

29、D D ，分別稱為 先序遍歷、中序遍歷、后序遍歷 A A F F G G E E D D C C B B數(shù)據(jù)結(jié)構(gòu)樹和二叉樹58 先序遍歷（先序遍歷（ D DL LR R ） 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹）先序遍歷右子樹； 先序遍歷序列：先序遍歷序列： A A F F G G E E D D C C B B例：先序遍歷右圖所示的二叉樹例：先序遍歷右圖所示的二叉樹 （1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A A （2 2）先序遍歷左子樹：即按先序遍歷左子樹：即按D DL LR R的順序遍歷的順序遍歷左

30、子樹左子樹 （3 3）先序遍歷右子樹：即按）先序遍歷右子樹：即按D DL LR R的順序遍歷的順序遍歷右子樹右子樹A BCDFGE二、先左后右的遍歷算法二、先左后右的遍歷算法數(shù)據(jù)結(jié)構(gòu)樹和二叉樹59中序遍歷（中序遍歷（ L LD DR R ）若二叉樹非空若二叉樹非空（1 1）中序遍歷左子樹）中序遍歷左子樹（2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)（3 3）中序遍歷右子樹）中序遍歷右子樹 中序遍歷序列： A A F F G G E E D D C C B B例：中序遍歷右圖所示的二叉樹例：中序遍歷右圖所示的二叉樹 （1 1）中序遍歷左子樹：即按）中序遍歷左子樹：即按L LD DR R的順序遍歷的順序遍歷左子

31、樹左子樹 （2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) A A （3 3）中序遍歷右子樹：即按中序遍歷右子樹：即按L LD DR R的順序遍歷的順序遍歷右子樹右子樹D BCGFAE數(shù)據(jù)結(jié)構(gòu)樹和二叉樹60后序遍歷（后序遍歷（L LR RD D）若二叉樹非空若二叉樹非空（1 1）后序遍歷左子樹）后序遍歷左子樹（2 2）后序遍歷右子樹）后序遍歷右子樹（3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) 后序遍歷序列：例：后序遍歷右圖所示的二叉樹例：后序遍歷右圖所示的二叉樹 （1 1）后序遍歷左子樹：即按）后序遍歷左子樹：即按L LR RD D的順序遍歷的順序遍歷左子樹左子樹 （2 2）后序遍歷右子樹：即按）后序遍歷右子樹：即按L

32、LR RD D的順序遍歷的順序遍歷右子樹右子樹 （3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) A A A A F F G G E E D D C C B BD GCEAFB數(shù)據(jù)結(jié)構(gòu)樹和二叉樹61 e e d d c c b b f f a a + + * * / / - - - - 后序遍歷序列： 中序遍歷序列： 先序遍歷序列：例：先例：先中序遍歷序遍歷、中序遍歷、中序遍歷序遍歷、中序遍歷、后后序遍歷下圖所示的二叉樹序遍歷下圖所示的二叉樹前綴表達(dá)式前綴表達(dá)式中綴表達(dá)式中綴表達(dá)式后綴表達(dá)式后綴表達(dá)式- + a * b - c d /e fa + b * c - d - e /fa b c d - * + e

33、 f /-數(shù)據(jù)結(jié)構(gòu)樹和二叉樹R A DE C HF GBK練習(xí)：求下列二叉鏈表和二叉樹的三種遍歷次序練習(xí)：求下列二叉鏈表和二叉樹的三種遍歷次序ABCDEFGHK數(shù)據(jù)結(jié)構(gòu)樹和二叉樹這實(shí)際上是這實(shí)際上是先序遍歷的遞歸定義，先序遍歷的遞歸定義，我們知道遞歸定義包括兩個(gè)部分我們知道遞歸定義包括兩個(gè)部分：1 1）基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）；（也叫終止項(xiàng)）； 2 2）遞歸項(xiàng)遞歸項(xiàng) 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；先序遍歷遞歸定義先序遍歷遞歸定義遞歸項(xiàng)遞歸項(xiàng)上面介紹了三種遍歷方法，顯然是用遞

34、歸的方式給出的三種遍歷方上面介紹了三種遍歷方法，顯然是用遞歸的方式給出的三種遍歷方法，以先序?yàn)槔悍?，以先序?yàn)槔合刃虮闅v（先序遍歷（D DL LR R）的定義：）的定義：該定義隱含著該定義隱含著若二叉若二叉樹為空，結(jié)束樹為空，結(jié)束 三、算法的遞歸描述三、算法的遞歸描述數(shù)據(jù)結(jié)構(gòu)樹和二叉樹上面先序遍歷的定義等價(jià)于：上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束若二叉樹為空，結(jié)束 基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）（也叫終止項(xiàng)）若二叉樹非空若二叉樹非空 遞歸項(xiàng)遞歸項(xiàng) （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹； 下面給出下面給出

35、先序、中序、后序遍歷遞歸算法，為了增加算法的可先序、中序、后序遍歷遞歸算法，為了增加算法的可讀性，這里對(duì)書上算法作了簡(jiǎn)化，沒有考慮訪問結(jié)點(diǎn)出錯(cuò)的情況讀性，這里對(duì)書上算法作了簡(jiǎn)化，沒有考慮訪問結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)（即我們假設(shè)調(diào)用函數(shù)visit( )visit( )訪問結(jié)點(diǎn)總是成功的。訪問結(jié)點(diǎn)總是成功的。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹先序遍歷遞歸算法先序遍歷遞歸算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的函數(shù)。本算是訪問結(jié)點(diǎn)的函數(shù)。本算

36、法法/先序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函先序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)數(shù)/Visit( ) if (T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 / 若二叉樹不為空，訪問根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹若二叉樹不為空，訪問根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse最簡(jiǎn)單的最簡(jiǎn)單的Visit函數(shù)是：函數(shù)是： Status PrintElement(TElem

37、Type e) /輸出元素輸出元素e的值的值 printf(e); return OK; D D A A B B C C E E FFT T數(shù)據(jù)結(jié)構(gòu)樹和二叉樹2 中序遍歷遞歸算法中序遍歷遞歸算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的函數(shù)。本算法中是訪問結(jié)點(diǎn)的函數(shù)。本算法中序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit( ) if (T) /若二叉樹為空，結(jié)束返回若二叉

38、樹為空，結(jié)束返回 / 若二叉樹不為空，遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹若二叉樹不為空，遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse 你能寫出你能寫出后序遍歷遞歸算法了吧后序遍歷遞歸算法了吧?數(shù)據(jù)結(jié)構(gòu)樹和二叉樹3 后序遍歷遞歸算法后序遍歷遞歸算法 void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈

39、表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的函數(shù)。本算法中是訪問結(jié)點(diǎn)的函數(shù)。本算法中序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit( ) if (T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 / 若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn)若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn) PostOrderTraverse(T-lchild, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse 數(shù)據(jù)結(jié)構(gòu)樹和二

40、叉樹 任何一棵二叉樹都可以將它的外部輪廓用一條任何一棵二叉樹都可以將它的外部輪廓用一條線繪制出來，我們將它稱為二叉樹的包線，這線繪制出來，我們將它稱為二叉樹的包線，這條包線對(duì)于理解二叉樹的遍歷過程很有用。條包線對(duì)于理解二叉樹的遍歷過程很有用。G HD E FB CA數(shù)據(jù)結(jié)構(gòu)樹和二叉樹四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用是對(duì)數(shù)據(jù)元素操作的應(yīng)用/函數(shù)函數(shù).中序遍歷二叉樹中序遍歷二叉樹

41、T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)/用函數(shù)用函數(shù)Visit。 InitStack(S); Push(S, T); / 根指針進(jìn)棧根指針進(jìn)棧 while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); / 向左走到盡頭向左走到盡頭 Pop(S, p); / 空指針退?？罩羔樛藯?if (!StackEmpty(S) / 訪問結(jié)點(diǎn)，向右一步訪問結(jié)點(diǎn)，向右一步 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); retu

42、rn OK; / InOrderTraverse數(shù)據(jù)結(jié)構(gòu)樹和二叉樹Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用是對(duì)數(shù)據(jù)元素操作的應(yīng)用/函數(shù)。中序遍歷二叉樹函數(shù)。中序遍歷二叉樹T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)/用函數(shù)用函數(shù)Visit。 InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; / 非空指針進(jìn)棧，繼續(xù)

43、左進(jìn)非空指針進(jìn)棧，繼續(xù)左進(jìn) else /上層指針退棧，訪問其所指結(jié)點(diǎn)，再向右進(jìn)上層指針退棧，訪問其所指結(jié)點(diǎn)，再向右進(jìn) Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse數(shù)據(jù)結(jié)構(gòu)樹和二叉樹中序遍歷遍歷二叉樹的非遞歸算法示意圖C B D F A G EABCDGEFABCNULLSGetToplchild)& (!T-rchild) count+; / 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, c

44、ount); / if / CountLeaf數(shù)據(jù)結(jié)構(gòu)樹和二叉樹2、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的二叉樹的深度應(yīng)為其左、右子樹深度的最大值加深度應(yīng)為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、求得左、右子樹深度的最大值，然后加右子樹深度的最大值，然后加 1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右子右子樹深度樹深度之間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)樹和二叉樹int Depth (BiTree T ) / 返回二叉樹的深度

45、 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;數(shù)據(jù)結(jié)構(gòu)樹和二叉樹3、復(fù)制二叉樹、復(fù)制二叉樹其基本操作為：生成一個(gè)結(jié)點(diǎn)。其基本操作為：生成一個(gè)結(jié)點(diǎn)。根元素根元素T左子樹左子樹右子樹右子樹根元素根元素NEWT左子樹左子樹右子樹右子樹左子樹左子樹右子樹右子樹(后序遍歷后序遍歷)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹BiTNod

46、e *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一個(gè)二叉樹的結(jié)點(diǎn)生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)槠鋽?shù)據(jù)域?yàn)閕tem,左指針域?yàn)樽笾羔樣驗(yàn)閘ptr,右指針域?yàn)橛抑羔樣驗(yàn)閞ptr)數(shù)據(jù)結(jié)構(gòu)樹和二叉樹BiTNode *CopyTree(BiTNode *T) if (!T ) re

47、turn NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/復(fù)制左子樹 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/復(fù)制右子樹 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTree數(shù)據(jù)結(jié)構(gòu)樹和二叉樹ABCDEFGHK D C B H K G F E A例如：下列二叉樹例如：下列二叉樹的復(fù)制過程如下：的復(fù)制過程如下：newT數(shù)據(jù)結(jié)構(gòu)

48、樹和二叉樹4 4、建立二叉樹的存儲(chǔ)、建立二叉樹的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu) 為二叉樹建立二叉鏈表為二叉樹建立二叉鏈表 輸入：輸入：二叉樹的先序序列二叉樹的先序序列 結(jié)果：結(jié)果：二叉樹的二叉鏈表二叉樹的二叉鏈表 遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。是否可在利用。是否可在利用遍歷，建立遍歷，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接？的鏈接？基本思想基本思想：輸入（輸入（在空子樹處添加在空子樹處添加* *的二叉樹的）先序序列（設(shè)每的二叉樹的）先序序列（設(shè)每個(gè)元素是個(gè)元素是一個(gè)字符）按先序遍歷的順序，建立二叉

49、鏈表的所有結(jié)點(diǎn)一個(gè)字符）按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接并完成相應(yīng)結(jié)點(diǎn)的鏈接數(shù)據(jù)結(jié)構(gòu)樹和二叉樹 D D A A B B C C E E F F T T 先序序列：A B D F C E（在空子樹處添加（在空子樹處添加* *的二叉樹的）先序序列：的二叉樹的）先序序列： A B D A B D * * F F * * * * * *C E C E * * * * * * A A F F E E D D C C B B* A A F F E E D D C C B B數(shù)據(jù)結(jié)構(gòu)樹和二叉樹Status CreateBiTree(BiTree &T) /輸入（在空子樹處

50、添加*的二叉樹的）先序序列（設(shè)每個(gè)元/素是一個(gè)字 符）按先序遍歷的順序，建立二叉鏈表，并將/該二叉鏈表根結(jié)點(diǎn)指針賦給T scanf (&ch); if (ch= = * )T=NULL; / 若ch= = * 則T=NULL返回 else / 若ch! = * if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（根）結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹 return OK;/CreateBiT

51、ree數(shù)據(jù)結(jié)構(gòu)樹和二叉樹84分析：若二叉樹的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。另外，由前序序列和中序序列的定義可知，前序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序列中，根結(jié)點(diǎn)剛好是左、右子樹的分界點(diǎn)，因此，可按如下方法建立二叉樹：由二叉樹的先序和中序序列建立二叉樹由二叉樹的先序和中序序列建立二叉樹二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根數(shù)據(jù)結(jié)構(gòu)樹和二叉樹851.1.用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn); ;2.2.在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序在中序序列中查找根

52、結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列列劃分為左、右兩個(gè)序列( (左、右子樹左、右子樹););3.3.根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹的前序序列右子樹的前序序列; ;4.4.對(duì)左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方對(duì)左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹為空。法，直到所得左、右子樹為空。假設(shè)前序序列為假設(shè)前序序列為ABDGHCEFIABDGHCEFI，中序序列為中序序

53、列為GDHBAECIFGDHBAECIF， 則得到的二叉樹如下頁(yè)所示則得到的二叉樹如下頁(yè)所示數(shù)據(jù)結(jié)構(gòu)樹和二叉樹861. 1. A A為根結(jié)點(diǎn)為根結(jié)點(diǎn)A BDGH CEFI GDHB A ECIF BDGHCEFIA2. 2. B B為左子樹的根結(jié)點(diǎn)為左子樹的根結(jié)點(diǎn)B DGHGDH BCEFIDHGBA3. 3. D D為左子樹的左子樹為左子樹的左子樹的根結(jié)點(diǎn)的根結(jié)點(diǎn) A B G H D C E F I 數(shù)據(jù)結(jié)構(gòu)樹和二叉樹87 A B G H D C FI E 4. 4. C C為右子樹的根結(jié)點(diǎn)為右子樹的根結(jié)點(diǎn) A B G H D C F I E 5. 5. F F為右子樹的右為右子樹的右子樹的

54、根結(jié)點(diǎn)子樹的根結(jié)點(diǎn)C E FIE C IF數(shù)據(jù)結(jié)構(gòu)樹和二叉樹a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列數(shù)據(jù)結(jié)構(gòu)樹和二叉樹練習(xí)： 已知結(jié)點(diǎn)的先序序列和中序序列，求整棵二叉樹。先序序列：A B C D E F G中序序列：C B E D A F GACBEDFGABCDEFGABCFDEG數(shù)據(jù)結(jié)構(gòu)樹和二叉樹6.3.2線索二叉樹線索二叉樹 線索二叉樹的定義線索二叉樹的定義 線索的描述線索的描述 建立線索二叉樹建立線索二叉樹 線索二叉樹上的運(yùn)算線索二叉樹上的運(yùn)算數(shù)據(jù)結(jié)構(gòu)樹和二叉樹遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性

55、序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A一、一、線索二叉樹的定義線索二叉樹的定義數(shù)據(jù)結(jié)構(gòu)樹和二叉樹在這樣的線性序列中，很容易求得某個(gè)結(jié)點(diǎn)在某種遍在這樣的線性序列中，很容易求得某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。然而，有時(shí)我們希望不進(jìn)行遍歷歷下的直接前驅(qū)和后繼。然而，有時(shí)我們希望不進(jìn)行遍歷就能快速找到某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼，就能快速找到某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼記錄下來。這樣，就應(yīng)該把每個(gè)

56、結(jié)點(diǎn)的直接前驅(qū)和直接后繼記錄下來。為了做到這一點(diǎn)，可以在原來的二叉鏈表結(jié)點(diǎn)中，再增加為了做到這一點(diǎn)，可以在原來的二叉鏈表結(jié)點(diǎn)中，再增加兩個(gè)指針域，一個(gè)指向前驅(qū)，一個(gè)指向后繼，但這樣做將兩個(gè)指針域，一個(gè)指向前驅(qū)，一個(gè)指向后繼，但這樣做將會(huì)浪費(fèi)大量存貯單元，存貯空間的利用率相當(dāng)?shù)蜁?huì)浪費(fèi)大量存貯單元，存貯空間的利用率相當(dāng)?shù)? (一個(gè)結(jié)一個(gè)結(jié)點(diǎn)中有點(diǎn)中有4 4個(gè)指針，個(gè)指針，1 1個(gè)指左孩子，個(gè)指左孩子，1 1個(gè)指右孩子，個(gè)指右孩子，1 1個(gè)指前驅(qū)，個(gè)指前驅(qū)，1 1個(gè)指后繼個(gè)指后繼) )，而原來的左、右孩子域有許多空指針又沒有，而原來的左、右孩子域有許多空指針又沒有利用起來。為了不浪費(fèi)存貯空間，我們利

57、用原有的孩子指利用起來。為了不浪費(fèi)存貯空間，我們利用原有的孩子指針為空時(shí)來存放直接前驅(qū)和后繼，這樣的指針稱為針為空時(shí)來存放直接前驅(qū)和后繼，這樣的指針稱為“線線索索”，加線索的過程稱為，加線索的過程稱為線索化線索化，加了線索的二叉樹，稱，加了線索的二叉樹，稱為為線索二叉樹線索二叉樹，對(duì)應(yīng)的二叉鏈表稱為，對(duì)應(yīng)的二叉鏈表稱為線索二叉鏈表線索二叉鏈表。一、一、線索二叉樹的定義線索二叉樹的定義數(shù)據(jù)結(jié)構(gòu)樹和二叉樹指向該線性序列中的“前驅(qū)”和 “后繼” 的指針指針，稱作“線索線索”加了線索的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的二叉鏈表，稱作 “線索鏈線索鏈表表”A B C D E F G

58、 H K D C B E 數(shù)據(jù)結(jié)構(gòu)樹和二叉樹在線索二叉樹中，由于有了線索，無需遍歷二叉在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后樹就可以得到任一結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。但是，我們?cè)鯓觼韰^(qū)分孩子指針域中存放的是左、繼。但是，我們?cè)鯓觼韰^(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢右孩子信息還是直接前驅(qū)或直接后繼信息呢? ?為此，在為此，在二叉鏈表結(jié)點(diǎn)中，還必須增加兩個(gè)標(biāo)志域二叉鏈表結(jié)點(diǎn)中，還必須增加兩個(gè)標(biāo)志域ltagltag、rtagrtag。 ltag和rtag定義如下： 0 lchild域指向結(jié)點(diǎn)的左孩子域指向結(jié)點(diǎn)的

59、左孩子 ltag= 1 lchild域指向結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)域指向結(jié)點(diǎn)在某種遍歷下的直接前驅(qū) 0 rchild域指向結(jié)點(diǎn)的右孩子域指向結(jié)點(diǎn)的右孩子 rtag= 1 rchild域指向結(jié)點(diǎn)在某種遍歷下的直接后繼域指向結(jié)點(diǎn)在某種遍歷下的直接后繼 數(shù)據(jù)結(jié)構(gòu)樹和二叉樹這樣，二叉鏈表中每個(gè)結(jié)點(diǎn)還是有這樣，二叉鏈表中每個(gè)結(jié)點(diǎn)還是有5個(gè)個(gè)域，但其中只有域，但其中只有2個(gè)指針，較原來的個(gè)指針，較原來的4個(gè)指?jìng)€(gè)指針要方便。增加線索后的二叉鏈表結(jié)點(diǎn)結(jié)針要方便。增加線索后的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)可描述如下：構(gòu)可描述如下： lchild ltag data rtag rchild 數(shù)據(jù)結(jié)構(gòu)樹和二叉樹typedef

60、struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;二、線索的描述：1、類型定義：、類型定義： typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索數(shù)據(jù)結(jié)構(gòu)樹和二叉樹2線索的畫法線索的畫法在二叉樹或二叉鏈表中，若左孩子為空，則在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅(qū)，右孩子為空時(shí)，則畫出它的畫出它的直接前驅(qū)，右孩子為空時(shí)，則畫出它的直接后繼，左右孩子不為空時(shí)，不需畫前驅(qū)和后直接后繼，左右孩子不為空時(shí)，不需畫前驅(qū)和后繼。這樣就得到了線索二叉樹或