第七章二叉樹

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

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

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

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

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

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

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

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

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

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

11、ld 與與rchild 分別存放指向分別存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值為空（用符號為空（用符號或或NULL 表示）。表示）。 二、鏈式存儲結(jié)構(gòu)（1）二叉鏈表存儲）二叉鏈表存儲二、鏈式存儲結(jié)構(gòu)（a）帶頭指針二叉鏈表（b）帶頭結(jié)點二叉鏈表（2）三叉鏈表存儲）三叉鏈表存儲每個結(jié)點由四個域組成，具體結(jié)構(gòu)為：每個結(jié)點由四個域組成，具體結(jié)構(gòu)為：其中，其中，data、lchild 以及以及rchild 三個域的意義同二叉鏈表結(jié)構(gòu)；三個域的意義同二叉鏈表結(jié)構(gòu)；parent 域為指向該結(jié)點雙親結(jié)點的指針。域為指向該

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

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

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

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

16、可以方便后邊的一些操作實現(xiàn)。可以方便后邊的一些操作實現(xiàn)。二、算法實現(xiàn)int Initiate (BiTree *bt)/*初始化建立二叉樹初始化建立二叉樹*bt 的頭結(jié)點的頭結(jié)點*/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é)點的數(shù)據(jù)域信息，以二叉為根結(jié)點的數(shù)據(jù)域信息，以二叉樹樹lbt 和和rbt為左右子樹的二叉樹。建立成功時返回所建二叉樹結(jié)點的指針；為

17、左右子樹的二叉樹。建立成功時返回所建二叉樹結(jié)點的指針；建立失敗時返回空指針。建立失敗時返回空指針。二、算法實現(xiàn)BiTree Create(elemtype x,BiTree lbt,BiTree rbt)/*生成一棵以生成一棵以x 為根結(jié)點的數(shù)據(jù)域值以為根結(jié)點的數(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二、算法實現(xiàn)BiTree In

18、sertL(BiTree bt,elemtype x,BiTree parent)/*在二叉樹在二叉樹bt 的結(jié)點的結(jié)點parent 的左子樹插入結(jié)點數(shù)據(jù)元素的左子樹插入結(jié)點數(shù)據(jù)元素x*/BiTree p;if (parent=NULL) printf(n 插入出錯插入出錯);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 ，右插入功能類同，略。，右插入功能類同，略。二、算法實現(xiàn)BiTree DeleteL(BiTree bt,BiTree parent)/*在二叉樹在二叉樹bt 中刪除結(jié)點中刪除結(jié)點parent 的左子樹的左子樹*/BiTree p;if (parent=NULL|parent-lchild=NULL) printf(n 刪除出錯刪除出錯);return NULL;p=parent-lchild;parent-lchild=NULL;free(p); /*當當p 為非葉子結(jié)點時為非葉子結(jié)點時,這樣刪

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

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

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

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

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

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

26、調(diào)用的結(jié)束條件遞歸調(diào)用的結(jié)束條件*/Visit(bt); /*訪問結(jié)點的數(shù)據(jù)域訪問結(jié)點的數(shù)據(jù)域*/PreOrder(bt-lchild); /*先序遞歸遍歷先序遞歸遍歷bt 的左子樹的左子樹*/PreOrder(bt-rchild); /*先序遞歸遍歷先序遞歸遍歷bt 的右子樹的右子樹*/中序遍歷二叉樹的遞歸算法如下：中序遍歷二叉樹的遞歸算法如下：7.5 二叉樹的遍歷方法及遞歸實現(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é)點的數(shù)據(jù)域訪問結(jié)點的數(shù)據(jù)域*/InOrder(bt-rchild); /*中序遞歸遍歷中序遞歸遍歷bt 的右子樹的右子樹*/中序遍歷二叉樹的遞歸算法如下：中序遍歷二叉樹的遞歸算法如下：7.5 二叉樹的遍歷方法及遞歸實現(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é)點的數(shù)據(jù)域訪問結(jié)點的數(shù)據(jù)域*/7.5 二叉樹的遍歷方法及遞歸實現(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é)點）開始，結(jié)點）開始，從上至下從上至下逐層遍歷逐層遍歷，在，在同一層中同一層中，則按，則按從左從左到右到右的順序?qū)Y(jié)點的順序?qū)Y(jié)點逐個訪問逐個訪問。7.5 二叉樹的遍歷方法及遞歸實現(xiàn)ABCDEAB CD E層次遍歷層次遍歷-算法實現(xiàn)思路算法實現(xiàn)思路 可設置一個隊列結(jié)構(gòu)，遍歷從二叉樹

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