第七章二叉樹

1、第七章 二叉樹數(shù)據(jù)結(jié)構(gòu)與關(guān)系數(shù)據(jù)庫(kù)數(shù)據(jù)結(jié)構(gòu)與關(guān)系數(shù)據(jù)庫(kù) 福 建 江 夏 學(xué) 院 FUJIAN JIANGXIA UNIVERSITY應(yīng)用場(chǎng)景 某公司想通過網(wǎng)絡(luò)傳輸一些秘密信息給客戶，把這些秘密信某公司想通過網(wǎng)絡(luò)傳輸一些秘密信息給客戶，把這些秘密信息變成二進(jìn)制碼進(jìn)行傳輸，為了節(jié)省數(shù)據(jù)文件在計(jì)算機(jī)內(nèi)的息變成二進(jìn)制碼進(jìn)行傳輸，為了節(jié)省數(shù)據(jù)文件在計(jì)算機(jī)內(nèi)的存儲(chǔ)空間和提高信息的傳輸速度，必須采用一種有效的編碼存儲(chǔ)空間和提高信息的傳輸速度，必須采用一種有效的編碼方法，編寫程序?qū)崿F(xiàn)之，得到如下所示的輸出結(jié)果。方法，編寫程序?qū)崿F(xiàn)之，得到如下所示的輸出結(jié)果。掌握樹、森林和二叉樹的概念，掌握哈夫曼樹的構(gòu)造及哈弗曼

2、編碼，掌握如何把樹或森林轉(zhuǎn)化為二叉樹，掌握二叉樹的基本性質(zhì)、存儲(chǔ)結(jié)構(gòu)、遍歷。 教學(xué)重點(diǎn)與難點(diǎn)： 二叉樹基本運(yùn)算和存儲(chǔ)結(jié)構(gòu)，二叉樹的遍歷。 教學(xué)目的與要求1.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為多少？2(k-1)2設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有多少個(gè)結(jié)點(diǎn)？2k-1問題二叉樹（二叉樹（Binary Tree）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根(root)的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時(shí)，稱該的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹

3、。在二叉樹中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。二叉樹為空二叉樹。在二叉樹中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。因此二叉樹具有五種基本形態(tài)，如圖點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。因此二叉樹具有五種基本形態(tài)，如圖7.1 所示。所示。7.1 二叉樹的基本概念左子樹左子樹右子樹右子樹右子樹右子樹左子樹左子樹圖圖7.1 二叉樹的五種基本狀態(tài)二叉樹的五種基本狀態(tài)（b）(c)(d)(e)滿二叉樹滿二叉樹在一棵二叉樹中，

4、如果滿足：在一棵二叉樹中，如果滿足：（1）所有分支結(jié)點(diǎn)都存在左子樹和右子樹；（）所有分支結(jié)點(diǎn)都存在左子樹和右子樹；（2）所）所有葉子結(jié)點(diǎn)都在同一層上有葉子結(jié)點(diǎn)都在同一層上,則這樣的一棵二叉樹稱作滿二叉樹。則這樣的一棵二叉樹稱作滿二叉樹。如圖如圖7.2所示，所示，（a）圖就是一棵滿二叉樹，（）圖就是一棵滿二叉樹，（b）圖則不是滿二叉樹。）圖則不是滿二叉樹。7.1 二叉樹的基本概念A(yù)BCDEFGHI123456789ABCDEFGHIJKLMNO123456789101112131415圖圖7.2（a）一棵滿二叉樹）一棵滿二叉樹（b）一棵非滿二叉樹）一棵非滿二叉樹完全二叉樹完全二叉樹一棵深度為一棵

5、深度為k 的有的有n 個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為如果編號(hào)為i（1in）的結(jié)點(diǎn)與滿二叉樹中編號(hào)為）的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i 的結(jié)點(diǎn)在二叉樹中的位置相同的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二，則這棵二叉樹稱為完全二叉樹。完全二叉樹的叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部層的葉子結(jié)點(diǎn)集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹。顯然，一棵滿二叉樹必定是

6、一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。未必是滿二叉樹。7.1 二叉樹的基本概念A(yù)BCDEFGHIJ12345678910圖圖7.3（a）一棵完全二叉樹）一棵完全二叉樹ABCDEFG1234678（b）一棵非完全二叉樹）一棵非完全二叉樹性質(zhì)性質(zhì)1 一棵非空二叉樹的第一棵非空二叉樹的第i 層上最多有層上最多有2i-1 個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i1）。）。性質(zhì)性質(zhì)2 一棵深度為一棵深度為k 的二叉樹中，最多具有的二叉樹中，最多具有2k1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。性質(zhì)性質(zhì)3 對(duì)于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為對(duì)于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為，度數(shù)為2 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n2，則有，則有:

7、n0n21。7.2 二叉樹的性質(zhì)性質(zhì)性質(zhì)4 具有具有n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度個(gè)結(jié)點(diǎn)的完全二叉樹的深度k 為為log2n+1。性質(zhì)性質(zhì)5 對(duì)于具有對(duì)于具有n 個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1 開始順序編號(hào)，則對(duì)于任意的序號(hào)為開始順序編號(hào)，則對(duì)于任意的序號(hào)為i 的結(jié)點(diǎn)，的結(jié)點(diǎn)，有：有： （1）如果）如果i1，則序號(hào)為，則序號(hào)為i 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2(“/”表示整除表示整除)；如；如果果i1，則序號(hào)為，則序號(hào)為i 的結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。的

8、結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。 （2）如果）如果2in，則序號(hào)為，則序號(hào)為i 的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i；如果；如果2in，則，則序號(hào)為序號(hào)為i 的結(jié)點(diǎn)無左孩子。的結(jié)點(diǎn)無左孩子。 （3）如果）如果2i1n，則序號(hào)為，則序號(hào)為i 的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i1；如果；如果2i1n，則序號(hào)為，則序號(hào)為i 的結(jié)點(diǎn)無右孩子。的結(jié)點(diǎn)無右孩子。7.2 二叉樹的性質(zhì)一、順序存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)所謂二叉樹的順序存儲(chǔ)，就是用一組所謂二叉樹的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)點(diǎn)。一般是按照二叉樹結(jié)點(diǎn)。一般是按

9、照二叉樹結(jié)點(diǎn)從上至下、從左到右從上至下、從左到右的順序存儲(chǔ)。的順序存儲(chǔ)。7.3 二叉樹的存儲(chǔ)一棵完全二叉樹一棵完全二叉樹圖圖7.4 完全二叉樹的順序存儲(chǔ)示意圖完全二叉樹的順序存儲(chǔ)示意圖一、順序存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)7.3 二叉樹的存儲(chǔ)（b）一棵不完全二叉樹）一棵不完全二叉樹（c）改造后的完全二叉樹）改造后的完全二叉樹圖圖7.5 一般二叉樹及其順序存儲(chǔ)示意圖一般二叉樹及其順序存儲(chǔ)示意圖一、順序存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)表示可描述為：二叉樹的順序存儲(chǔ)表示可描述為：即將即將bt 定義為含有定義為含有MAXNODE 個(gè)個(gè)elemtype 類型元素的一類型元素的一維數(shù)組。維數(shù)組。7.3

10、二叉樹的存儲(chǔ)#define MAXNODE /*二叉樹的最大結(jié)點(diǎn)數(shù)二叉樹的最大結(jié)點(diǎn)數(shù)*/typedef elemtype SqBiTreeMAXNODE /*0 號(hào)單元存放根結(jié)點(diǎn)號(hào)單元存放根結(jié)點(diǎn)*/SqBiTree bt;（1）二叉鏈表存儲(chǔ)）二叉鏈表存儲(chǔ)鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。結(jié)點(diǎn)的別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。結(jié)點(diǎn)的存儲(chǔ)的結(jié)構(gòu)為：存儲(chǔ)的結(jié)構(gòu)為：其中，其中，data 域存放某結(jié)點(diǎn)的數(shù)據(jù)信息；域存放某結(jié)點(diǎn)的數(shù)據(jù)信息；lchi

11、ld 與與rchild 分別存放指向分別存放指向左孩子和右孩子的指針，當(dāng)左孩子或右孩子不存在時(shí)，相應(yīng)指針域值左孩子和右孩子的指針，當(dāng)左孩子或右孩子不存在時(shí)，相應(yīng)指針域值為空（用符號(hào)為空（用符號(hào)或或NULL 表示）。表示）。 二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）二叉鏈表存儲(chǔ)）二叉鏈表存儲(chǔ)二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（a）帶頭指針二叉鏈表（b）帶頭結(jié)點(diǎn)二叉鏈表（2）三叉鏈表存儲(chǔ)）三叉鏈表存儲(chǔ)每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：其中，其中，data、lchild 以及以及rchild 三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；parent 域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。域?yàn)橹赶蛟?/p>

12、結(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是，相這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是，相對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言，它增加了空間開銷。對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言，它增加了空間開銷。二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)lchilddatarchildparent（2）三叉鏈表存儲(chǔ)）三叉鏈表存儲(chǔ)二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉樹的二叉鏈表存儲(chǔ)表示可描述為：即將BiTree 定義為指向二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)的指針類型。二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedef struct BiTNode elemtype data; struct BiTNode *lchild,*rchild; /*左右孩子指針*

13、/BiTNode,*BiTree;注：注：*二叉鏈表是最常用的二叉樹存儲(chǔ)方式二叉鏈表是最常用的二叉樹存儲(chǔ)方式 知識(shí)回顧二叉樹的定義二叉樹的定義二叉樹（二叉樹（Binary Tree）是個(gè)有限元素的集合，該集合或者為）是個(gè)有限元素的集合，該集合或者為空空、或者由一個(gè)、或者由一個(gè)稱為根稱為根(root)的元素及兩個(gè)不相交的、被分別稱為的元素及兩個(gè)不相交的、被分別稱為左子樹左子樹和和右子樹右子樹的二叉樹的二叉樹組成。組成。ABCDEFGHI123456789知識(shí)回顧二叉樹的存儲(chǔ)二叉樹的存儲(chǔ)順序存儲(chǔ)順序存儲(chǔ)二叉鏈表二叉鏈表三叉鏈表三叉鏈表結(jié)構(gòu)如何定義？結(jié)構(gòu)如何定義？一、二叉樹的基本操作一、二叉樹的基本

14、操作（1）Initiate（bt）建立一棵空二叉樹。（2）Create（x，lbt，rbt）生成一棵以x 為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹lbt 和rbt為左子樹和右子樹的二叉樹。（3）InsertL（bt，x，parent）將數(shù)據(jù)域信息為x 的結(jié)點(diǎn)插入到二叉樹bt 中作為結(jié)點(diǎn)parent 的左孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)parent 原來有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent 原來的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x 的左孩子結(jié)點(diǎn)。（4）InsertR（bt，x，parent）將數(shù)據(jù)域信息為x 的結(jié)點(diǎn)插入到二叉樹bt 中作為結(jié)點(diǎn)parent 的右孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)parent 原來有右孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent 原來

15、的右孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x 的右孩子結(jié)點(diǎn)。（5）DeleteL（bt，parent）在二叉樹bt 中刪除結(jié)點(diǎn)parent 的左子樹。（6）DeleteR（bt，parent）在二叉樹bt 中刪除結(jié)點(diǎn)parent 的右子樹。（7）Search（bt，x）在二叉樹bt 中查找數(shù)據(jù)元素x。（8）Traverse（bt）按某種方式遍歷二叉樹bt 的全部結(jié)點(diǎn)。7.4 二叉樹的基本操作及實(shí)現(xiàn)（1）Initiate（bt）初始建立二叉樹）初始建立二叉樹bt，并使，并使bt 指向頭結(jié)點(diǎn)。在指向頭結(jié)點(diǎn)。在二叉樹根結(jié)點(diǎn)前建立頭結(jié)點(diǎn)，就如同在單鏈表前建立的頭結(jié)點(diǎn)，二叉樹根結(jié)點(diǎn)前建立頭結(jié)點(diǎn)，就如同在單鏈表前建立的頭結(jié)點(diǎn)，

16、可以方便后邊的一些操作實(shí)現(xiàn)?？梢苑奖愫筮叺囊恍┎僮鲗?shí)現(xiàn)。二、算法實(shí)現(xiàn)int Initiate (BiTree *bt)/*初始化建立二叉樹初始化建立二叉樹*bt 的頭結(jié)點(diǎn)的頭結(jié)點(diǎn)*/if(*bt=(BiTNode *)malloc(sizeof(BiTNode)=NULL)return 0;(*bt)-lchild=NULL;(*bt)-rchild=NULL;return 1;/算法算法7.1（2）Create（x，lbt，rbt）建立一棵以）建立一棵以x 為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹樹lbt 和和rbt為左右子樹的二叉樹。建立成功時(shí)返回所建二叉樹結(jié)點(diǎn)的指針；為

17、左右子樹的二叉樹。建立成功時(shí)返回所建二叉樹結(jié)點(diǎn)的指針；建立失敗時(shí)返回空指針。建立失敗時(shí)返回空指針。二、算法實(shí)現(xiàn)BiTree Create(elemtype x,BiTree lbt,BiTree rbt)/*生成一棵以生成一棵以x 為根結(jié)點(diǎn)的數(shù)據(jù)域值以為根結(jié)點(diǎn)的數(shù)據(jù)域值以lbt 和和rbt 為左右子樹的二叉樹為左右子樹的二叉樹*/BiTree p;if (p=(BiTNode *)malloc(sizeof(BiTNode)=NULL) return NULL;p-data=x;p-lchild=lbt;p-rchild=rbt;return p;/算法算法7.2二、算法實(shí)現(xiàn)BiTree In

18、sertL(BiTree bt,elemtype x,BiTree parent)/*在二叉樹在二叉樹bt 的結(jié)點(diǎn)的結(jié)點(diǎn)parent 的左子樹插入結(jié)點(diǎn)數(shù)據(jù)元素的左子樹插入結(jié)點(diǎn)數(shù)據(jù)元素x*/BiTree p;if (parent=NULL) printf(n 插入出錯(cuò)插入出錯(cuò));return NULL;if (p=(BiTNode *)malloc(sizeof(BiTNode)=NULL) return NULL;p-data=x;p-lchild=NULL;p-rchild=NULL;if (parent-lchild=NULL) parent-lchild=p;else p-lchild=

19、parent-lchild;parent-lchild=p;return bt;/算法算法7.3 ，右插入功能類同，略。，右插入功能類同，略。二、算法實(shí)現(xiàn)BiTree DeleteL(BiTree bt,BiTree parent)/*在二叉樹在二叉樹bt 中刪除結(jié)點(diǎn)中刪除結(jié)點(diǎn)parent 的左子樹的左子樹*/BiTree p;if (parent=NULL|parent-lchild=NULL) printf(n 刪除出錯(cuò)刪除出錯(cuò));return NULL;p=parent-lchild;parent-lchild=NULL;free(p); /*當(dāng)當(dāng)p 為非葉子結(jié)點(diǎn)時(shí)為非葉子結(jié)點(diǎn)時(shí),這樣刪

20、除僅釋放了所刪子樹根結(jié)點(diǎn)的空間這樣刪除僅釋放了所刪子樹根結(jié)點(diǎn)的空間,*/*若要?jiǎng)h除子樹分支中的結(jié)點(diǎn)若要?jiǎng)h除子樹分支中的結(jié)點(diǎn),需用后面介紹的遍歷操作來實(shí)現(xiàn)。需用后面介紹的遍歷操作來實(shí)現(xiàn)。*/return bt;/算法算法7.4二叉樹的遍歷二叉樹的遍歷什么是遍歷？什么是遍歷？按照某一順序，訪問數(shù)據(jù)結(jié)構(gòu)中的按照某一順序，訪問數(shù)據(jù)結(jié)構(gòu)中的所有結(jié)點(diǎn)所有結(jié)點(diǎn)，使每個(gè)，使每個(gè)結(jié)點(diǎn)都被結(jié)點(diǎn)都被訪問一次訪問一次，而且，而且只訪問一次只訪問一次。7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)也叫也叫“周游周游”二叉樹的遍歷二叉樹的遍歷為什么要遍歷？為什么要遍歷？它是插入、刪除、修改、查找和排序運(yùn)算的前提，是它是插入、刪除、修

21、改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)。二叉樹一切運(yùn)算的基礎(chǔ)。7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)“遍歷遍歷”曾經(jīng)很簡(jiǎn)單曾經(jīng)很簡(jiǎn)單7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)a1a2.ai-1aiai+1.an. a1 a2 an .H“遍歷遍歷”也可以很復(fù)雜也可以很復(fù)雜7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)V0V1V2V4V3V5V7V8V6歷史上的歷史上的“遍歷遍歷”問題問題-柯尼斯堡七橋問題柯尼斯堡七橋問題7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)歷史上的歷史上的“遍歷遍歷”問題問題-柯尼斯堡七橋問題柯尼斯堡七橋問題7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)圖論和拓?fù)鋵W(xué)均由此

22、問題發(fā)展而來圖論和拓?fù)鋵W(xué)均由此問題發(fā)展而來7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)圖論和拓?fù)鋵W(xué)均由此問題發(fā)展而來圖論和拓?fù)鋵W(xué)均由此問題發(fā)展而來計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)溆?jì)算機(jī)網(wǎng)絡(luò)拓?fù)湓鯓颖闅v一棵二叉樹怎樣遍歷一棵二叉樹-規(guī)定一個(gè)順序規(guī)定一個(gè)順序根據(jù)定義：非空二叉樹由根據(jù)定義：非空二叉樹由根根、左子樹左子樹、右子樹構(gòu)成右子樹構(gòu)成只需要按順序進(jìn)行以下三個(gè)操作：只需要按順序進(jìn)行以下三個(gè)操作：訪問根節(jié)點(diǎn)（訪問根節(jié)點(diǎn)（D）遍歷左子樹（遍歷左子樹（L）遍歷右子樹（遍歷右子樹（R）7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)ABCDE怎樣遍歷一棵二叉樹怎樣遍歷一棵二叉樹-規(guī)定一個(gè)順序規(guī)定一個(gè)順序D、L、R的組合定義了幾種可能的遍歷方案

23、呢？的組合定義了幾種可能的遍歷方案呢？LDR、LRD、DLR、DRL、RLD、RDL若限定先左后右，則有三種實(shí)現(xiàn)方案：若限定先左后右，則有三種實(shí)現(xiàn)方案：7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)DLRLDRLRD 先先序遍歷序遍歷 中中序遍歷序遍歷 后后序遍歷序遍歷怎樣遍歷一棵二叉樹怎樣遍歷一棵二叉樹-規(guī)定一個(gè)順序規(guī)定一個(gè)順序7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)DLRLDRLRD 先先序遍歷序遍歷 中中序遍歷序遍歷 后后序遍歷序遍歷三種方式的步驟是什么三種方式的步驟是什么？（1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（2）先序遍歷根結(jié)點(diǎn)的左子樹；）先序遍歷根結(jié)點(diǎn)的左子樹；（3）先序遍歷根結(jié)點(diǎn)的右子樹。）先序遍歷根結(jié)

24、點(diǎn)的右子樹。（1）中序遍歷根結(jié)點(diǎn)的左子樹；）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹。）中序遍歷根結(jié)點(diǎn)的右子樹。（1）后序遍歷根結(jié)點(diǎn)的左子樹；）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹。）后序遍歷根結(jié)點(diǎn)的右子樹。（3）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)；例例7.5.1 7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)先序遍歷：先序遍歷：根節(jié)點(diǎn)根節(jié)點(diǎn)左子樹左子樹右子樹右子樹ABCDEAB D E E例例7.5.1 7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)中序遍歷：中序遍歷：根節(jié)點(diǎn)根節(jié)點(diǎn)左子樹左子樹右子樹右子樹ABCDEAD B E C例例7.5.1 7.5 二叉樹的遍歷

25、方法及遞歸實(shí)現(xiàn)后序遍歷：后序遍歷：根節(jié)點(diǎn)根節(jié)點(diǎn)左子樹左子樹右子樹右子樹ABCDEAD E B C例例7.5.2 7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)中序遍歷、先序遍中序遍歷、先序遍歷、后序遍歷分別歷、后序遍歷分別是什么樣的序列？是什么樣的序列？a + b * c - d - e / f- + a * b - c d / e fa b c d - * + e f / -先序遍歷二叉樹的遞歸算法如下：先序遍歷二叉樹的遞歸算法如下：7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)void PreOrder(BiTree bt)/*先序遍歷二叉樹先序遍歷二叉樹bt*/if (bt=NULL) return; /*遞歸

26、調(diào)用的結(jié)束條件遞歸調(diào)用的結(jié)束條件*/Visit(bt); /*訪問結(jié)點(diǎn)的數(shù)據(jù)域訪問結(jié)點(diǎn)的數(shù)據(jù)域*/PreOrder(bt-lchild); /*先序遞歸遍歷先序遞歸遍歷bt 的左子樹的左子樹*/PreOrder(bt-rchild); /*先序遞歸遍歷先序遞歸遍歷bt 的右子樹的右子樹*/中序遍歷二叉樹的遞歸算法如下：中序遍歷二叉樹的遞歸算法如下：7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)void InOrder(BiTree bt)/*中序遍歷二叉樹中序遍歷二叉樹bt*/if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件遞歸調(diào)用的結(jié)束條件*/InOrder(bt-lchild); /*

27、中序遞歸遍歷中序遞歸遍歷bt 的左子樹的左子樹*/Visit(bt); /*訪問結(jié)點(diǎn)的數(shù)據(jù)域訪問結(jié)點(diǎn)的數(shù)據(jù)域*/InOrder(bt-rchild); /*中序遞歸遍歷中序遞歸遍歷bt 的右子樹的右子樹*/中序遍歷二叉樹的遞歸算法如下：中序遍歷二叉樹的遞歸算法如下：7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)void PostOrder(BiTree bt)/*后序遍歷二叉樹后序遍歷二叉樹bt*/if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件遞歸調(diào)用的結(jié)束條件*/PostOrder(bt-lchild); /*后序遞歸遍歷后序遞歸遍歷bt 的左子樹的左子樹*/PostOrder(bt-

28、rchild); /*后序遞歸遍歷后序遞歸遍歷bt 的右子樹的右子樹*/Visit(bt); /*訪問結(jié)點(diǎn)的數(shù)據(jù)域訪問結(jié)點(diǎn)的數(shù)據(jù)域*/7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)int main(void) BiTree bt,lt,rt;lt=Create(E,NULL,NULL);rt=Create(F,NULL,NULL);rt=Create(C,lt,rt); lt=Create(G,NULL,NULL);lt=Create(D,NULL,lt);lt=Create(B,lt,NULL);bt=Create(A,lt,rt); printf(先序遍歷：先序遍歷：); PreOrder(bt);p

29、rintf(n);printf(中序遍歷：中序遍歷：); InOrder(bt);printf(n);printf(后序遍歷：后序遍歷：); PostOrder(bt);printf(n);return 0;層次遍歷層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點(diǎn)）開始，結(jié)點(diǎn)）開始，從上至下從上至下逐層遍歷逐層遍歷，在，在同一層中同一層中，則按，則按從左從左到右到右的順序?qū)Y(jié)點(diǎn)的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問逐個(gè)訪問。7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)ABCDEAB CD E層次遍歷層次遍歷-算法實(shí)現(xiàn)思路算法實(shí)現(xiàn)思路 可設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹

30、的根結(jié)點(diǎn)開始，首先將根可設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)指針入隊(duì)列，然后從對(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行結(jié)點(diǎn)指針入隊(duì)列，然后從對(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：下面兩個(gè)操作：（1）訪問該元素所指結(jié)點(diǎn)；）訪問該元素所指結(jié)點(diǎn)；（2）若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將該元素）若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)a1 a2 a3 a4 a5入隊(duì)入隊(duì)出隊(duì)出隊(duì)層次遍歷層次遍歷-算法實(shí)現(xiàn)算法實(shí)現(xiàn)7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn)void LevelOrder(BiTree bt) BiTree queueMAXSIZENODE; int front,rear; if(bt=NULL) return; front=-1; rear=0; queuerear=bt; 層次遍歷層次遍歷-算法實(shí)現(xiàn)算法實(shí)現(xiàn)7.5 二叉樹的遍歷方法及遞歸實(shí)現(xiàn) while(front!=rear) front+; Visit(queuefront); if(queuefront-l