數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷

1、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷二叉樹(shù)的遍歷二叉樹(shù)的遍歷二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)小結(jié)和作業(yè)小結(jié)和作業(yè)順序存儲(chǔ)順序存儲(chǔ)二叉鏈表二叉鏈表三叉鏈表三叉鏈表鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)問(wèn)題的提出問(wèn)題的提出遞歸遍歷算法遞歸遍歷算法遍歷的應(yīng)用實(shí)例遍歷的應(yīng)用實(shí)例二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)順序存儲(chǔ)是用一組連續(xù)的存儲(chǔ)單元存放數(shù)據(jù)順序存儲(chǔ)要求數(shù)據(jù)是線性結(jié)構(gòu)二叉樹(shù)是非線性結(jié)構(gòu)如何把二叉樹(shù)轉(zhuǎn)換為線性結(jié)構(gòu)，而且保持結(jié)點(diǎn)之間的父/子關(guān)系?二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)ACGBDEFK LHJIM NO123456789101112131415滿二叉樹(shù)：從上到下，從左往右依次編號(hào)二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序

2、存儲(chǔ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15數(shù)組的下標(biāo)，也是結(jié)點(diǎn)的編號(hào) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B CEFDGH IJK LM N O二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)ACGBDEFHJI12345678910完全二叉樹(shù)：從上到下，從左往右依次編號(hào) 0 1 2 3 4 5 6 7 8 9 10 A B CEFDGH IJ二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)ABDCEF一般的二叉樹(shù)：想象成一個(gè)完全二叉樹(shù)一般的二叉樹(shù)：想象成一個(gè)完全二叉樹(shù)ABDCEF00000000二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)ABDCEF000

3、000001234567891011121314二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)ABDCEF1253714 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B CDEF 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 11110010000001如何知道有無(wú)數(shù)據(jù)？#define MAX_TREE_SIZE 100 / 二叉樹(shù)的最大結(jié)點(diǎn)數(shù)二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE; / 1號(hào)單元存儲(chǔ)根結(jié)點(diǎn)號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTree bt;二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)#define MA

4、X_TREE_SIZE 100 / 二叉樹(shù)的最大結(jié)點(diǎn)數(shù)二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef struct TElemType dataMAX_TREE_SIZE; char flagMAX_TREE_SIZE; SqBiTree;二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)適用于一般的二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)二叉鏈表二叉鏈表lchild data rchild二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu): :左指針域，指向當(dāng)左指針域，指向當(dāng)前結(jié)點(diǎn)的左子樹(shù)前結(jié)點(diǎn)的左子樹(shù)數(shù)據(jù)域，存儲(chǔ)當(dāng)前數(shù)據(jù)域，存儲(chǔ)當(dāng)前結(jié)點(diǎn)的取值信息結(jié)點(diǎn)的取值信息右指針域，指向當(dāng)右指針域，指向當(dāng)前結(jié)點(diǎn)的右子樹(shù)前結(jié)點(diǎn)的右子樹(shù)指向二叉樹(shù)根結(jié)點(diǎn)指向二叉樹(shù)根結(jié)點(diǎn)頭

5、指針：頭指針：前述二叉樹(shù)的二叉鏈表如下所示：前述二叉樹(shù)的二叉鏈表如下所示：AFECDBroot鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)二叉鏈表二叉鏈表a1a2a3LABDCEF1253714typedef 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 C 語(yǔ)言類型描述如下語(yǔ)言類型描述如下: :左指針域左指針域數(shù)據(jù)域數(shù)據(jù)域右指針域右指針域鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)二叉鏈表二叉鏈表pa

6、rent lchild data rchild三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu): :指向雙親結(jié)指向雙親結(jié)點(diǎn)的指針域點(diǎn)的指針域左指針域左指針域數(shù)據(jù)域數(shù)據(jù)域右指針域右指針域鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)三叉鏈表三叉鏈表rootAEFDCB二叉樹(shù)的三叉鏈表表示：二叉樹(shù)的三叉鏈表表示：鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)三叉鏈表三叉鏈表 typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild; struct TriTNode *parent; TriTNode, *TriTree;三叉鏈表的三叉鏈表的C C 語(yǔ)言類型描述如下語(yǔ)言類型描述如下:

7、 :parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): :/ 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)/ 左右孩子指針左右孩子指針/雙親指針雙親指針鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)三叉鏈表三叉鏈表問(wèn)題的提出問(wèn)題的提出 在實(shí)際應(yīng)用中，經(jīng)常需要在二叉樹(shù)中查找具有某些特征的結(jié)點(diǎn)，或者對(duì)樹(shù)中的全部結(jié)點(diǎn)逐一進(jìn)行某種處理，這就提出了二叉樹(shù)的遍歷的問(wèn)題。問(wèn)題的提出問(wèn)題的提出 定義：定義：順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。作用：作用： 遍歷的目的是線性化，使二叉樹(shù)中的結(jié)點(diǎn)能夠按照某種次序排列在一個(gè)線性隊(duì)列上，便于處理。問(wèn)題的提出問(wèn)題的提出 線性結(jié)構(gòu)的遍歷：因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼，

8、所以只有一條搜索路徑。二叉樹(shù)的遍歷：二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑進(jìn)行遍歷的問(wèn)題。問(wèn)題的提出問(wèn)題的提出二叉樹(shù)存在下述三條搜索路徑：二叉樹(shù)存在下述三條搜索路徑：n1先上后下先上后下的按層次遍歷；n2先左先左（子樹(shù)）后右后右（子樹(shù)）的遍歷；nDLR，LDR，LRDn3先右先右（子樹(shù)）后左后左（子樹(shù)）的遍歷。nDRL，RDL，RLD先序（根）遍歷先序（根）遍歷左子樹(shù)右子樹(shù)根根根根左左子樹(shù)子樹(shù)右右子樹(shù)子樹(shù) 若二叉樹(shù)為空樹(shù)，則空操作；若二叉樹(shù)為空樹(shù)，則空操作；否則，否則，（1 1）訪問(wèn)根結(jié)點(diǎn)）訪問(wèn)根結(jié)點(diǎn)（2 2）先序遍歷左子樹(shù)）先序遍歷左子樹(shù)（3 3）先序遍歷

9、右子樹(shù)）先序遍歷右子樹(shù)先序（根）遍歷先序（根）遍歷ABCDEFGHKABCDEFGHKA B C D E F G H K課堂練習(xí)課堂練習(xí)ABDCEFABC寫(xiě)出先序遍歷的結(jié)果寫(xiě)出先序遍歷的結(jié)果void Preorder (BiTree T,void( *visit)(TElemType& e) / 先序遍歷二叉樹(shù) 1 if (!T) return; 2 visit(T-data); / 訪問(wèn)根結(jié)點(diǎn) 3 Preorder(T-lchild, visit); / 遍歷左子樹(shù) 4 Preorder(T-rchild, visit); / 遍歷右子樹(shù) 先序遍歷先序遍歷中序（根）遍歷中序（根）遍歷

10、左子樹(shù)右子樹(shù)根根根根左左子樹(shù)子樹(shù)右右子樹(shù)子樹(shù) 若二叉樹(shù)為空樹(shù)，則空操作；否則，（1 1）中序遍歷左子樹(shù)；）中序遍歷左子樹(shù)；（2 2）訪問(wèn)根結(jié)點(diǎn)；）訪問(wèn)根結(jié)點(diǎn)；（3 3）中序遍歷右子樹(shù)）中序遍歷右子樹(shù)中序（根）遍歷中序（根）遍歷ABCDEFGHKABCDEFGHKAB D CE H G K F中序遍歷中序遍歷void Inorder (BiTree T, void( *visit)(TElemType& e) / 中序遍歷二叉樹(shù)二叉樹(shù) 1 if (!T) return;2 Inorder(T-lchild, visit); / 遍歷左子樹(shù)3 visit(T-data); / 訪問(wèn)結(jié)點(diǎn)4

11、Inorder(T-rchild, visit); / 遍歷右子樹(shù)后序（根）遍歷后序（根）遍歷左子樹(shù)右子樹(shù)根根根根左左子樹(shù)子樹(shù)右右子樹(shù)子樹(shù) 若二叉樹(shù)為空樹(shù)，則空操作；否則，（1 1）后序遍歷左子樹(shù)；）后序遍歷左子樹(shù)；（2 2）后序遍歷右子樹(shù)；）后序遍歷右子樹(shù)；（3 3）訪問(wèn)根結(jié)點(diǎn)。）訪問(wèn)根結(jié)點(diǎn)。后序（根）遍歷后序（根）遍歷ABCDEFGHKABCDEFGHKAD C B H K G F Evoid Postorder (BiTree T, void( *visit)(TElemType& e) / 后序遍歷二叉樹(shù) 1 if (!T) return;2 Postorder(T-lchil

12、d, visit); / 遍歷左子樹(shù)3 Postorder(T-rchild, visit); / 遍歷右子樹(shù)4 visit(T-data); / 訪問(wèn)結(jié)點(diǎn)后序遍歷后序遍歷課堂練習(xí)課堂練習(xí)寫(xiě)出三種遍歷的結(jié)果ABECDABCDEFGHK先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A三種遍歷的比較三種遍歷的比較1、如果不考慮visit，三種遍歷的算法在結(jié)構(gòu)上是一樣的，因此，壓棧和出棧的過(guò)程相同。 三種遍歷的比較三種遍歷的比較2、三種遍歷的執(zhí)行過(guò)程是不一樣的（visit的位置不一樣）。

13、3、由前序序列和中序序列，或者后序和中序序列可以唯一確定一顆二叉樹(shù)ABCDEFGHK先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A三種遍歷的比較三種遍歷的比較3、復(fù)制二叉樹(shù)、復(fù)制二叉樹(shù)4、建立二叉樹(shù)、建立二叉樹(shù)2、查詢二叉樹(shù)中某個(gè)結(jié)點(diǎn)、查詢二叉樹(shù)中某個(gè)結(jié)點(diǎn)應(yīng)用舉例應(yīng)用舉例1、統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)遍歷訪問(wèn)了每個(gè)結(jié)點(diǎn)一次且僅一次遍歷訪問(wèn)了每個(gè)結(jié)點(diǎn)一次且僅一次設(shè)置一個(gè)全局變量設(shè)置一個(gè)全局變量count=0count=0統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)

14、數(shù)將將visitvisit改為改為:count+:count+統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)void PreOrder (BiTree T)if (! T ) return;count+;Preorder( T-lchild); Preorder( T-rchild);void Preorder (BiTree T,void( *visit)(TElemType& e) / 先序遍歷二叉樹(shù) 1 if (!T) return; 2 visit(T-data); / 訪問(wèn)結(jié)點(diǎn) 3 Preorder(T-lchild, visit); / 遍歷左子樹(shù) 4 Preorder(T-

15、rchild, visit);/ 遍歷右子樹(shù) 統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)int count=0;main()PreOrder(T);printf(”%d”,count);遞歸思想遞歸思想: :如果是空樹(shù)，返回如果是空樹(shù)，返回0 0統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)求出左子樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)求出左子樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)m求出右子樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)求出右子樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)n返回返回m+n+1統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)int CountNode (BiTree T)/返回指針T所指二叉樹(shù)中所有葉子結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0;/空樹(shù)空樹(shù)m = Count

16、Node( T-lchild); n = CountNode( T-rchild); return (m+n+1);求二叉樹(shù)的深度求二叉樹(shù)的深度課堂練習(xí)：課堂練習(xí)：空樹(shù)的深度為空樹(shù)的深度為0，求二叉樹(shù)的深度求二叉樹(shù)的深度int Depth (BiTree T )/ 返回二叉樹(shù)的深度if ( !T ) return (0);depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild );depthval = 1 + (depthLeft depthRight ? depthLeft :depthRight);return depthval

17、;查詢二叉樹(shù)中的某個(gè)結(jié)點(diǎn)查詢二叉樹(shù)中的某個(gè)結(jié)點(diǎn)給定指向二叉樹(shù)的根結(jié)點(diǎn)的指針給定指向二叉樹(shù)的根結(jié)點(diǎn)的指針T T和和x x，在，在T T中查找中查找數(shù)據(jù)元素的值等于數(shù)據(jù)元素的值等于x x的結(jié)點(diǎn)，如果找到，則返回一的結(jié)點(diǎn)，如果找到，則返回一個(gè)指針，指向這個(gè)結(jié)點(diǎn)，否則，返回空指針。個(gè)指針，指向這個(gè)結(jié)點(diǎn)，否則，返回空指針。ABECDTX= C查詢二叉樹(shù)中的某個(gè)結(jié)點(diǎn)查詢二叉樹(shù)中的某個(gè)結(jié)點(diǎn)1. 1. 在二叉樹(shù)不空的前提下在二叉樹(shù)不空的前提下, ,和根結(jié)點(diǎn)的元素進(jìn)和根結(jié)點(diǎn)的元素進(jìn)行比較行比較, ,若相等若相等, ,則找到返回則找到返回指向根結(jié)點(diǎn)的指針指向根結(jié)點(diǎn)的指針2. 2. 否則在左子樹(shù)中進(jìn)行查找否則在左子

18、樹(shù)中進(jìn)行查找, ,若找到若找到, ,則返回則返回指針指針3. 3. 否則繼續(xù)在右子樹(shù)中進(jìn)行查找否則繼續(xù)在右子樹(shù)中進(jìn)行查找, ,若找到若找到, ,則返則返回指針回指針, ,否則返回否則返回空指針空指針查詢二叉樹(shù)中的某個(gè)結(jié)點(diǎn)查詢二叉樹(shù)中的某個(gè)結(jié)點(diǎn)BiTree Search (BiTree T, TElemType x) if (!T) return(NULL);if (T-data=x) return (T)； if(p) /返回值不是空指針，則表示返回值不是空指針，則表示x在左子樹(shù)中在左子樹(shù)中return(p); else return(Search(T-rchild, x) ;p=Search

19、(T-lchild, x);復(fù)制二叉樹(shù)復(fù)制二叉樹(shù)( (練習(xí)練習(xí)) )給定一棵二叉樹(shù)，給定一棵二叉樹(shù)，T指向其根結(jié)點(diǎn)，復(fù)制一棵二叉樹(shù)，指向其根結(jié)點(diǎn)，復(fù)制一棵二叉樹(shù)，返回一個(gè)指向新樹(shù)根結(jié)點(diǎn)的指針?lè)祷匾粋€(gè)指向新樹(shù)根結(jié)點(diǎn)的指針根元素根元素T右子樹(shù)右子樹(shù)根元素根元素NEWT左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)左子樹(shù)左子樹(shù)復(fù)制二叉樹(shù)復(fù)制二叉樹(shù)1、如果、如果T為空，則返回空指針為空，則返回空指針2、復(fù)制根結(jié)點(diǎn)，、復(fù)制根結(jié)點(diǎn)，p指向新結(jié)點(diǎn)指向新結(jié)點(diǎn)3、復(fù)制左子樹(shù)，、復(fù)制左子樹(shù)，pl指向左子樹(shù)的根指向左子樹(shù)的根4、復(fù)制右子樹(shù)，、復(fù)制右子樹(shù)，pr指向右子樹(shù)的根指向右子樹(shù)的根5、p-lchid = pl，p-rchild =

20、pr6、返回、返回p復(fù)制二叉樹(shù)復(fù)制二叉樹(shù)Bitree Copy(BitTree T)if(!T) return(NULL);p = new BiNode; p-data = T-datapl = Copy(T-lchild);pr = Copy(T-rchild);p-lchild = pl; p-rchild =pr;return(p);以下列字符串表示以下列字符串表示AB C D 建立二叉樹(shù)建立二叉樹(shù)以字符串的形式以字符串的形式“根左子樹(shù)右子樹(shù)根左子樹(shù)右子樹(shù)”定義定義一棵二叉樹(shù)一棵二叉樹(shù)以空白字符以空白字符“ ”“ ”表示表示1）空樹(shù)）空樹(shù)2）只含一個(gè)根）只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)結(jié)點(diǎn)的二叉樹(shù)A以字符串以字符串“A ” ”表示表示ABCD3）建立二叉樹(shù)建立二叉樹(shù)A B C D A BCDATBCD建立二叉樹(shù)建立二叉樹(shù)Status CreateBiTree(BiTree &T) / CopyTreescanf(&ch);else T-data = ch; / 生成根結(jié)點(diǎn)return OK;if (!(T = new BiTNode) exit(OVERFLOW);if (ch = = ) T = NULL; CreateBiTree(T-lchild); / 構(gòu)造左子樹(shù) CreateBiTree(T-rchild)