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

1、二叉樹的存儲結(jié)構(gòu)和遍歷二叉樹的存儲結(jié)構(gòu)和遍歷 二叉樹的遍歷二叉樹的遍歷 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 小結(jié)和作業(yè)小結(jié)和作業(yè) 順序存儲順序存儲 二叉鏈表二叉鏈表 三叉鏈表三叉鏈表 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?問題的提出問題的提出 遞歸遍歷算法遞歸遍歷算法 遍歷的應(yīng)用實(shí)例遍歷的應(yīng)用實(shí)例 二叉樹的順序存儲二叉樹的順序存儲 順序存儲是用一組連續(xù)的存儲單元存放數(shù)據(jù) 順序存儲要求數(shù)據(jù)是線性結(jié)構(gòu) 二叉樹是非線性結(jié)構(gòu) 如何把二叉樹轉(zhuǎn)換為線性結(jié)構(gòu)，而且保持 結(jié)點(diǎn)之間的父/子關(guān)系? 二叉樹的順序存儲二叉樹的順序存儲 A C G B DEF K LHJIM NO 1 23 4567 89101112131415 滿二叉樹

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

3、樹：想象成一個(gè)完全二叉樹 A B D C E F 0 0 00 0 0 00 二叉樹的順序存儲二叉樹的順序存儲 A B D C E F 0 0 00 0 0 00 1 23 4567 891011121314 二叉樹的順序存儲二叉樹的順序存儲 A B D C E F 1 2 5 3 7 14 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 如何知道有無數(shù)據(jù)？ #define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù) ty

4、pedef TElemType SqBiTreeMAX_TREE_SIZE; / 1號單元存儲根結(jié)點(diǎn)號單元存儲根結(jié)點(diǎn) SqBiTree bt; 二叉樹的順序存儲二叉樹的順序存儲 #define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù) typedef struct TElemType dataMAX_TREE_SIZE; char flagMAX_TREE_SIZE; SqBiTree; 二叉樹的順序存儲二叉樹的順序存儲 適用于一般的二叉樹 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Χ骀湵矶骀湵?lchild data rchild 二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu): : 左

5、指針域，指向當(dāng)左指針域，指向當(dāng) 前結(jié)點(diǎn)的左子樹前結(jié)點(diǎn)的左子樹 數(shù)據(jù)域，存儲當(dāng)前數(shù)據(jù)域，存儲當(dāng)前 結(jié)點(diǎn)的取值信息結(jié)點(diǎn)的取值信息 右指針域，指向當(dāng)右指針域，指向當(dāng) 前結(jié)點(diǎn)的右子樹前結(jié)點(diǎn)的右子樹 指向二叉樹根結(jié)點(diǎn)指向二叉樹根結(jié)點(diǎn)頭指針：頭指針： 前述二叉樹的二叉鏈表如下所示：前述二叉樹的二叉鏈表如下所示： A F E C D B root 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Χ骀湵矶骀湵?a1a2a3 L A B D C E F 1 2 5 3 7 14 typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild

6、; / 左右孩子指針左右孩子指針 BiTNode, *BiTree; lchild data rchild 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu): : 二叉鏈表的二叉鏈表的C C 語言類型描述如下語言類型描述如下: : 左指針域左指針域數(shù)據(jù)域數(shù)據(jù)域 右指針域右指針域 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Χ骀湵矶骀湵?parent 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)酱鎯︽準(zhǔn)酱鎯θ骀湵砣骀湵?root A E F D C B 二叉樹的三叉鏈表表示：二叉樹的三叉鏈表表示： 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?/p>

7、三叉鏈表三叉鏈表 typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild; struct TriTNode *parent; TriTNode, *TriTree; 三叉鏈表的三叉鏈表的C C 語言類型描述如下語言類型描述如下: : 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)酱鎯︽準(zhǔn)酱鎯θ骀湵砣骀湵?問題的提出問題的提出 在實(shí)際應(yīng)用中，經(jīng)常需要在二叉樹中查找 具有某些特征的結(jié)點(diǎn)，或者對樹中的全

8、部結(jié)點(diǎn) 逐一進(jìn)行某種處理，這就提出了二叉樹的遍歷 的問題。 問題的提出問題的提出 定義：定義：順著某一條搜索路徑巡訪二叉樹中的結(jié) 點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪 問一次。 作用：作用： 遍歷的目的是線性化，使二叉樹中的 結(jié)點(diǎn)能夠按照某種次序排列在一個(gè)線性隊(duì)列上， 便于處理。 問題的提出問題的提出 線性結(jié)構(gòu)的遍歷：因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后 繼，所以只有一條搜索路徑。 二叉樹的遍歷：二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié) 點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的 搜索路徑進(jìn)行遍歷的問題。 問題的提出問題的提出 二叉樹存在下述三條搜索路徑：二叉樹存在下述三條搜索路徑： n1先上后下先上后下的按層次遍歷

9、； n2先左先左（子樹）后右后右（子樹）的遍歷； nDLR，LDR，LRD n3先右先右（子樹）后左后左（子樹）的遍歷。 nDRL，RDL，RLD 先序（根）遍歷先序（根）遍歷 左 子樹 右 子樹 根根根根 左左 子樹子樹 右右 子樹子樹 若二叉樹為空樹，則空操作；若二叉樹為空樹，則空操作； 否則，否則， （1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹）先序遍歷右子樹 先序（根）遍歷先序（根）遍歷 A B C D E F G HK A B C D E F G HK A B C D E F G H K 課堂練習(xí)課堂練習(xí) A B D CE F

10、A B C 寫出先序遍歷的結(jié)果寫出先序遍歷的結(jié)果 void Preorder (BiTree T,void( *visit)(TElemType 2 visit(T-data); / 訪問根結(jié)點(diǎn) 3 Preorder(T-lchild, visit); / 遍歷左子樹 4 Preorder(T-rchild, visit); / 遍歷右子樹 先序遍歷先序遍歷 中序（根）遍歷中序（根）遍歷 左 子樹 右 子樹 根根根根 左左 子樹子樹 右右 子樹子樹 若二叉樹為空樹，則空操作； 否則， （1 1）中序遍歷左子樹；）中序遍歷左子樹； （2 2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （3 3）中序遍歷右子樹）

11、中序遍歷右子樹 中序（根）遍歷中序（根）遍歷 A B C D E F G HK A B C D E F G HK AB D CE H G K F 中序遍歷中序遍歷 void Inorder (BiTree T, void( *visit)(TElemType 2 Inorder(T-lchild, visit); / 遍歷左子樹 3 visit(T-data); / 訪問結(jié)點(diǎn) 4 Inorder(T-rchild, visit); / 遍歷右子樹 后序（根）遍歷后序（根）遍歷 左 子樹 右 子樹 根根根根 左左 子樹子樹 右右 子樹子樹 若二叉樹為空樹，則空操 作；否則， （1 1）后序遍歷左

12、子樹；）后序遍歷左子樹； （2 2）后序遍歷右子樹；）后序遍歷右子樹； （3 3）訪問根結(jié)點(diǎn)。）訪問根結(jié)點(diǎn)。 后序（根）遍歷后序（根）遍歷 A B C D E F G HK A B C D E F G HK AD C B H K G F E void Postorder (BiTree T, void( *visit)(TElemType 2 Postorder(T-lchild, visit); / 遍歷左子樹 3 Postorder(T-rchild, visit); / 遍歷右子樹 4 visit(T-data); / 訪問結(jié)點(diǎn) 后序遍歷后序遍歷 課堂練習(xí)課堂練習(xí) 寫出三種遍歷的結(jié)果 A

13、 B E CD A B C D E F G HK 先序序列：先序序列： 中序序列：中序序列： 后序序列：后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三種遍歷的比較三種遍歷的比較 1、如果不考慮visit，三種遍歷的算法在結(jié)構(gòu) 上是一樣的，因此，壓棧和出棧的過程相同。 三種遍歷的比較三種遍歷的比較 2、三種遍歷的執(zhí)行過程是不一樣的（visit的 位置不一樣）。 3、由前序序列和中序序列，或者后序和中序 序列可以唯一確定一顆二叉樹 A B C D E F G HK 先序序列：先序序列： 中序序列：中序序列： 后序序列：后序

14、序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 三種遍歷的比較三種遍歷的比較 3、復(fù)制二叉樹、復(fù)制二叉樹 4、建立二叉樹、建立二叉樹 2、查詢二叉樹中某個(gè)結(jié)點(diǎn)、查詢二叉樹中某個(gè)結(jié)點(diǎn) 應(yīng)用舉例應(yīng)用舉例 1、統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù)、統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) 遍歷訪問了每個(gè)結(jié)點(diǎn)一次且僅一次遍歷訪問了每個(gè)結(jié)點(diǎn)一次且僅一次 設(shè)置一個(gè)全局變量設(shè)置一個(gè)全局變量count=0count=0 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) 將將visitvisit改為改為:count+:count+ 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) v

15、oid PreOrder (BiTree T) if (! T ) return; count+; Preorder( T-lchild); Preorder( T-rchild); void Preorder (BiTree T,void( *visit)(TElemType 2 visit(T-data); / 訪問結(jié)點(diǎn) 3 Preorder(T-lchild, visit); / 遍歷左子樹 4 Preorder(T-rchild, visit);/ 遍歷右子樹 統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)的個(gè)數(shù) int count=0; main() PreOrder(T); printf(

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

17、度 課堂練習(xí)：課堂練習(xí)： 空樹的深度為空樹的深度為0， 求二叉樹的深度求二叉樹的深度 int Depth (BiTree T )/ 返回二叉樹的深度 if ( !T ) return (0); depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft :depthRight); return depthval; 查詢二叉樹中的某個(gè)結(jié)點(diǎn)查詢二叉樹中的某個(gè)結(jié)點(diǎn) 給定指向二叉樹的根結(jié)點(diǎn)的指針給定指向二叉樹的根結(jié)點(diǎn)的指針T T和和x x，在

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

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

20、樹，給定一棵二叉樹，T指向其根結(jié)點(diǎn)，復(fù)制一棵二叉樹，指向其根結(jié)點(diǎn)，復(fù)制一棵二叉樹， 返回一個(gè)指向新樹根結(jié)點(diǎn)的指針返回一個(gè)指向新樹根結(jié)點(diǎn)的指針 根元素根元素 T 右子樹右子樹 根元素根元素 NEWT 左子樹左子樹右子樹右子樹 左子樹左子樹 復(fù)制二叉樹復(fù)制二叉樹 1、如果、如果T為空，則返回空指針為空，則返回空指針 2、復(fù)制根結(jié)點(diǎn)，、復(fù)制根結(jié)點(diǎn)，p指向新結(jié)點(diǎn)指向新結(jié)點(diǎn) 3、復(fù)制左子樹，、復(fù)制左子樹，pl指向左子樹的根指向左子樹的根 4、復(fù)制右子樹，、復(fù)制右子樹，pr指向右子樹的根指向右子樹的根 5、p-lchid = pl，p-rchild = pr 6、返回、返回p 復(fù)制二叉樹復(fù)制二叉樹 Bit

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