第一篇：二叉樹的性質(zhì)總結(jié)

一、二叉樹的性質(zhì)

性質(zhì)

1、二叉樹的第i層上至多有2 i-1（i ?1）個結(jié)點。用數(shù)學(xué)歸納法證明

推廣：k叉樹(或度為k的樹)的第i層上至多有k i-1（i ?1）個結(jié)點

性質(zhì)

2、度為h的二叉樹中至多含有2h-1個結(jié)點。

21-1 + 2 2-1+……+ 2 h-1 = 2 h-1

推廣：深度為h的k叉樹(或度為k的樹)中至多含有(k h-1)/(k-1)個結(jié)點

k1-1 + k 2-1+……+ k h-1 =(k h-1)/(k-1)

性質(zhì)

3、若在任意一棵二叉樹中，有n0個葉子結(jié)點，有n2個度為2的結(jié)點，則：n0=n2+1

證明：設(shè)：有n0個葉子結(jié)點，有n1個度為1的結(jié)點，有n2個度為2的結(jié)點，則二叉樹中結(jié)點總數(shù)為：n=n0+n1+ n2(1)

設(shè)分支的總數(shù)為m,則：m= n1+2 n2(2)

因為n=m+1（3）

所以： n0+n1+ n2 = n1+2 n2 +1

整理得：n0= n2+1

推廣: 度為k的樹有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nk個度為k的結(jié)點則n0為:

?

i=1 k(i-1)ni+

1性質(zhì)3推廣的證明于性質(zhì)3的證明

設(shè)：有n0個葉子結(jié)點，有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nk個度為k的結(jié)點則結(jié)點總數(shù)為：n=n0+n1+ n2 +……+nk(1)

設(shè)分支的總數(shù)為m,則：m= n1+2 n2+……+knk

因為n=m+1（3）

所以：n0+n1+ n2 +……+nk = n1+2 n2+……+knk +1

整理得：n0= 0n1+1n2+……+(k-1)nk+1

性質(zhì)

4、具有n個結(jié)點的完全二叉樹，其深度為?㏒2n?+1

證明：設(shè)n個結(jié)點的完全二叉樹的深度為k，根據(jù)性質(zhì)2可知，k-1層滿二叉樹的結(jié)點總數(shù)為： 2k-1-1

k層滿二叉樹的結(jié)點總數(shù)為： 2k-1

顯然有：

2k-1-1 < n ? 2k-1?2k-1 ? n < 2k

取對數(shù)有：k-1 ? log2n < k

因為k是整數(shù)，所以k-1 = ?log2n?，k= ?㏒2n?+1

結(jié)論成立。

推廣: 具有n個結(jié)點的完全k叉樹，其深度為? logk(k-1)n ?+1

設(shè)n個結(jié)點的完全k叉樹的深度為h，根據(jù)性質(zhì)2推廣可知，h-1層滿k叉樹的結(jié)點總數(shù)為：(k h-1-1)/(k-1)

h層滿二叉樹的結(jié)點總數(shù)為：(k h-1)/(k-1)

顯然有：

(k h-1-1)/(k-1)< n ?(k h-1)/(k-1)

k h-1-1 <(k-1)n ? k h-1

k h-1 ?(k-1)n< k h

取對數(shù)有：h-1 ? logk(k-1)n

因為h是整數(shù)，所以h-1 = ? logk(k-1)n ?，h= ? logk(k-1)n ?+1

性質(zhì)

5、設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序(每一層從左到右)用自然數(shù)1，2，3……,n給結(jié)點進行編號，則對于編號為k(k=1,2,……n)的結(jié)點有以下結(jié)論：

(1)若k=1,則該結(jié)點為根結(jié)點，它沒有雙親結(jié)點；若k>1,則該結(jié)點的雙親結(jié)點編號為 [k/2 ]。

(2)若2k<=n,則編號為k的左孩子結(jié)點編號為2k;否則該結(jié)點無左孩子結(jié)點(顯然也沒有右孩子結(jié)點)。

(3)若2k+1<=n,則編號為k的右孩子結(jié)點編號為2k+1;否則該結(jié)點無右孩子結(jié)點

推廣:一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹，如果按層次順序從1開始對全部結(jié)點進行編號，求：

1）各層的結(jié)點的數(shù)目是多少？

2）編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是多少？

3）編號為n的結(jié)點的第i 個孩子結(jié)點（若存在）的編號是多少？

4）編號為n的結(jié)點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？ 答:

h-1(1)k(h為層數(shù))

h-1（2）因為該樹每層上均有K個結(jié)點，從根開始編號為1，則結(jié)點i的從右向左數(shù)第２個

孩子的結(jié)點編號為ki。設(shè)n 為結(jié)點i的子女，則關(guān)系式(i-1)k+2<=n<=ik+1成立，因i是整數(shù)，故結(jié)點n的雙親i的編號為?n-2)/k?+1。

(3)結(jié)點n(n>1)的前一結(jié)點編號為n-1（其最右邊子女編號是(n-1)*k+1），故結(jié)點 n的第 i個孩子的編號是(n-1)*k+1+i。

(4)根據(jù)以上分析，結(jié)點n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即(n-1)%k!=0，其右兄弟編號是n+1。

二：滿二叉樹：

一棵深度為k且有2k-1個結(jié)點的二叉樹

特點：每一層上都含有最大結(jié)點數(shù)。葉子結(jié)點在同一層次上；無度為1的結(jié)點

具有n個結(jié)點的滿二叉樹則

葉子結(jié)點的個數(shù)為：（n+1)/2

度為2的結(jié)點的個數(shù)為：（n-1)/2

三、無度為1的結(jié)點

1: 具有n個結(jié)點的無度為1的結(jié)點的二叉樹，求葉子結(jié)點的個數(shù)

n1=0

n=n1+n2+n0=n0+n2+0

n=2n0-1

n0=（n+1）/2n2=（n-1）/2

2:若已知葉子結(jié)點個數(shù)n0求總的結(jié)點的個數(shù)n

N=n0+n2=2n0-1

四、完全二叉樹：深度為k的有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中的編號從1至n的結(jié)點一一對應(yīng)

特點：除最后一層外，每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置。

葉子結(jié)點在最后兩層上，度為1的結(jié)點的個數(shù)最多為1

1:具有n個結(jié)點的完全二叉樹，求葉子結(jié)點的個數(shù)

n是偶數(shù)：

則n1=1

n=n1+n2+n0=n0+n2+1

n=2n0

n0=n/2n2=n/2-1

n是奇數(shù)：

則n1=0

n=n1+n2+n0=n0+n2+0

n=2n0-1

n0=（n+1）/2n2=（n-1）/2

2:若已知完全二叉樹葉子結(jié)點個數(shù)：求總的結(jié)點的個數(shù)

n=n0+n1+n2

n1=1 或n1=0n2=n0-1

n最大為2n0,最小為2n0-1

3:若已知完全二叉樹第k層上具有n個葉子結(jié)點，求最多的結(jié)點個數(shù)及最少的結(jié)點個數(shù)最多的結(jié)點個數(shù)：共有k+1層

前k層共有2k-1個結(jié)點

k+1層: 第k+1層結(jié)點數(shù)最多為第k層的非葉子結(jié)點數(shù)乘以2；第k層的結(jié)點數(shù)為2k-1，葉子結(jié)點數(shù)為n, 非葉子結(jié)點數(shù)為(2k-1-n)，所以第k+1層結(jié)點數(shù)最多為2(2k-1-n)個結(jié)點,所以最多結(jié)點數(shù)為2k-1+ 2(2k-1-n)

最少的結(jié)點個數(shù)：共有k層 前k-1層具有2k-1-1個結(jié)點，k層有n個共有2k-1-1+n

第二篇：實驗報告：二叉樹

實驗報告 二叉樹

一 實驗?zāi)康?/p>

1、進一步掌握指針變量，動態(tài)變量的含義；

2、掌握二叉樹的結(jié)構(gòu)特性以及各種存儲結(jié)構(gòu)的特點及適用范圍。

3、掌握用指針類型描述、訪問和處理二叉樹的運算。

4、熟悉各種存儲結(jié)構(gòu)的特征以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題。

二 實驗原理

樹形結(jié)構(gòu)是一種應(yīng)用十分廣泛和重要的非線性數(shù)據(jù)結(jié)構(gòu)，是一種以分支關(guān)系定義的層次結(jié)構(gòu)。在這種結(jié)構(gòu)中，每個數(shù)據(jù)元素至多只有一個前驅(qū)，但可以有多個后繼；數(shù)據(jù)元素之間的關(guān)系是一對多的層次關(guān)系。樹形結(jié)構(gòu)主要用于描述客觀世界中具有層次結(jié)構(gòu)的數(shù)據(jù)關(guān)系，它在客觀世界中大量存在。遍歷二叉樹的實質(zhì)是將非線性結(jié)構(gòu)轉(zhuǎn)為線性結(jié)構(gòu)。

三 使用儀器，材料 計算機 2 Wndows xp 3 VC6.0

四實驗步驟

【問題描述】建立一個二叉樹，請分別按前序，中序和后序遍歷該二叉樹?！净疽蟆繌逆I盤接受輸入（按前序順序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以前序來建立），并采用遞歸算法對其進行前序，中序和后序遍歷，將結(jié)果輸出。

【實現(xiàn)提示】按前序次序輸入二叉樹中結(jié)點的值（一個整數(shù)），0表示空樹，葉子結(jié)點的特征是其左右孩子指針為空。

五實驗過程原始記錄 基本數(shù)據(jù)結(jié)構(gòu)描述； 2 函數(shù)間的調(diào)用關(guān)系； 用類C語言描述各個子函數(shù)的算法； 附錄：源程序。

六 試驗結(jié)果分析

將實驗結(jié)果分析、實驗中遇到的問題和解決問題的方法以及關(guān)于本實驗項目的心得體會，寫在實驗報告上。

第三篇：二叉樹遍歷課程設(shè)計】

數(shù)據(jù)結(jié)構(gòu)程序設(shè)計報告

學(xué)院： 班級： 學(xué)號：

姓名：

實驗名稱：二叉樹的建立與遍歷

一、實驗?zāi)康模?/p>

1.掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)； 2.掌握二叉樹創(chuàng)建方法；

3.掌握二叉樹的先序、中序、后序的遞歸實現(xiàn)方法。

二、實驗內(nèi)容和要求：

創(chuàng)建二叉樹，分別對該二叉樹進行先序、中序、后序遍歷，并輸出遍歷結(jié)果。

三、叉樹的建立與遍歷代碼如下：

#include #include struct tnode//結(jié)點結(jié)構(gòu)體 {

};typedef struct tnode TNODE;

TNODE *creat(void){ TNODE *root,*p;TNODE *queue[50];char data;struct tnode *lchild,*rchild;

int front=0,rear=-1,counter=0;//初始隊列中需要的變量front、rear和計數(shù)器counter char ch;printf(“建立二叉樹，請輸入結(jié)點:（#表示虛節(jié)點,!表示結(jié)束)n”);

ch=getchar();

while(ch!='!'){ if(ch!='#')

{ p=(TNODE *)malloc(sizeof(TNODE));

p->data=ch;

p->lchild=NULL;

p->rchild=NULL;rear++;

queue[rear]=p;//把非#的元素入隊

if(rear==0)//如果是第一個元素，則作為根節(jié)點 {

} else {

if(counter%2==1)//奇數(shù)時與其雙親的左子樹連接 {

}

if(counter%2==0)//偶數(shù)時與其雙親的右子樹連接 {

queue[front]->rchild=p;queue[front]->lchild=p;root=p;counter++;

}

}

}

}

front++;

counter++;

else//為#時，計數(shù)，但不連接結(jié)點 {

if(counter%2==0)

front++;counter++;

}

ch=getchar();} return root;void preorder(TNODE *bt)//先序遍歷 {

if(bt!=NULL){

printf(“%c

”,bt->data);preorder(bt->lchild);preorder(bt->rchild);

} } void inorder(TNODE *bt)//中序遍歷 {

if(bt!=NULL){

inorder(bt->lchild);printf(“%c

”,bt->data);inorder(bt->rchild);

} }

void postorder(TNODE *bt)//后序遍歷 {

if(bt!=NULL){

postorder(bt->lchild);postorder(bt->rchild);printf(“%c

”,bt->data);

} } int main(){

TNODE *root;

root=creat();printf(“遞歸先序遍歷是:”);

preorder(root);

printf(“n”);printf(“遞歸中序遍歷是：”);inorder(root);printf(“n”);

} printf(“遞歸后序遍歷是：”);postorder(root);printf(“n”);return 0;

四、程序運行結(jié)果：

五、程序設(shè)計指導(dǎo)：

1.創(chuàng)建二叉樹的算法：首先對一般的二叉樹，添加若干個虛結(jié)點使其成為完全二叉樹，然后依次輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點，若是第一個，則令其為根結(jié)點，否則將新結(jié)點鏈接至它的雙親結(jié)點上。如此重復(fù)下去，直至遇到輸入結(jié)束符（自定）為止。為了使新結(jié)點能夠與雙親結(jié)點正確相連，并考慮到這種方法中先建立的結(jié)點其孩子結(jié)點也一定先建立的特點，可以設(shè)置一個指針類型的數(shù)組構(gòu)成的隊列來保存已輸入結(jié)點的地址，并使隊尾(rear)指向當(dāng)前輸入的結(jié)點，隊頭(front)指向這個結(jié)點的雙親結(jié)點的前一個位置。由于根結(jié)點的地址放在隊列的第一個單元里，所以當(dāng)rear為奇數(shù)時，則rear所指的結(jié)點應(yīng)作為左孩子與其雙親鏈接，否則rear所指的結(jié)點應(yīng)作為右孩子與其雙親鏈接。若雙親結(jié)點或孩子結(jié)點為虛結(jié)點，則無須鏈接。若一個雙親結(jié)點與兩個孩子鏈接完畢，則進行出隊操作，使隊頭指針指向下一個待鏈接的雙親結(jié)點。

2.void preorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先讀取，再進行進入下一個遞歸循環(huán)中。

3.void inorder(TNODE *bt)函數(shù) ：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先左子樹，再讀取結(jié)點元素，再進行進入下一個遞歸循環(huán)中。

4.void postorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先分別進入左右子樹，再進行讀取，再進行進入下一個遞歸循環(huán)中。

六、心得體會：

本次數(shù)據(jù)結(jié)構(gòu)程序設(shè)計對我有一定的幫助。通過這次的實踐，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更深入地了解。在寫程序的過程中，我重復(fù)地讀課本上的知識，并且漸漸領(lǐng)悟到數(shù)據(jù)結(jié)構(gòu)編程的方法。在編程中，雖然遇到了一些困難，但我并不氣餒。當(dāng)程序運行出來時，我感到了快樂?？傊?，通過自己地探索和努力，思維得到了鍛煉，編程能力也有了較大地改善。

第四篇：實驗5_二叉樹

贛南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院

實 驗 報 告 冊

課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)

實驗項目名稱： 實驗5.二叉樹 實驗學(xué)時： 4 學(xué)生學(xué)號與姓名： 實驗地點： 數(shù)計樓四樓 實驗日期： 年 月 日 指導(dǎo)老師：

實驗5 二叉樹

一、實驗?zāi)康暮鸵?/p>

（1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。

二、實驗儀器和設(shè)備

Visual C++ 6.0

三、實驗內(nèi)容與過程

1.建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。

2.在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點的個數(shù)。3.在第一題基礎(chǔ)上，求二叉樹的深度。

程序清單： 1.2.3.贛南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院

四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）

五、實驗體會（遇到問題及解決辦法，編程后的心得體會）

第五篇：數(shù)據(jù)結(jié)構(gòu)作業(yè)——二叉樹

數(shù)據(jù)結(jié)構(gòu)實驗報告二

題目：

用先序遞歸過程監(jiān)理二叉樹（存儲結(jié)構(gòu)：二叉鏈表）

輸入數(shù)據(jù)按先序遍歷輸入，當(dāng)某節(jié)點左子樹或者右子樹為空時，輸入‘*’號，如輸入abc**d**e**時，得到的二叉樹為：

并用如下實力測試：

算法思路：

顯然，建立一個二叉鏈表存儲的二叉樹，如果不考慮效率要求，考慮到程序的簡介性，遞歸建立和遞歸遍歷是一種很好的辦法。

利用C++的類模板的方法實現(xiàn)建立，遍歷，輸出等二叉樹操作。首先利用構(gòu)造函數(shù)實現(xiàn)先序遍歷建立二叉樹，然后調(diào)用類模板中已經(jīng)聲明好的四種遍歷函數(shù)，將遍歷結(jié)果輸出，檢驗建立好的二叉樹是否為要求的二叉樹。

初始化：利用構(gòu)造函數(shù)建立二叉樹。采用先序遞歸的調(diào)用方法，構(gòu)造函數(shù)主體如下：

template BiTree::BiTree(){ this->root = Creat();//利用this指針調(diào)用creat函數(shù) }

template BiNode* BiTree::Creat()//定義構(gòu)造函數(shù) { BiNode* root;T aa;cout<<“請按前序序列方式輸入節(jié)點數(shù)據(jù)，每次輸入一個”<>aa;if(aa==“*”)root = NULL;else{

root = new BiNode;

//生成一個結(jié)點 root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

} return root;} 構(gòu)造這樣的函數(shù)，可以在輸入時，按先序遍歷順序每次輸入一個節(jié)點的數(shù)據(jù)，可以實現(xiàn)任意二叉樹的構(gòu)造。

為了檢驗構(gòu)造的二叉樹是否為預(yù)先設(shè)想的二叉樹，需要遍歷二叉樹并進行輸出?？紤]到單一的輸出并不能確定唯一的二叉樹，因此對遍歷二叉樹的四種常用發(fā)方法，即先序遍歷，中序遍歷，后續(xù)遍歷，層次遍歷分別實現(xiàn)，通過遍歷結(jié)果檢驗構(gòu)造的二叉樹是否為預(yù)先設(shè)計好的二叉樹。

先序遍歷：采用遞歸的方法建立。template voidBiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節(jié)點為空，則返回空 else{ cout<data<<“ ”;//訪問根節(jié)點

xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹

} 中序遍歷：遞歸方法建立： template voidBiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節(jié)點為空，則返回空 else{ zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹 cout<data<<“ ”;

//訪問根結(jié)點

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹

}

} 后序遍歷：遞歸方法建立： template voidBiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節(jié)點為空，返回空 else{ houxu(root->lchild);

//后序遞歸遍歷root的左子樹 houxu(root->rchild);

//后序遞歸遍歷root的右子樹 cout<data<<“ ”;

//訪問根節(jié)點

} } 層序遍歷：采用非遞歸方法。利用隊列的方法層序遍歷二叉樹。建立一個隊列，在訪問一個節(jié)點的時候，把它的左孩子和右孩子入隊，并且將這個節(jié)點出隊。當(dāng)隊列為空時，就完成了對二叉樹的層序遍歷。

template voidBiTree::cengxu(BiNode *root){ constintMaxSize = 100;int front = 0;int rear = 0;//利用隊列的方法對樹進行層序遍歷 BiNode* Q[MaxSize];BiNode* q;if(root==NULL)return;// 如果節(jié)點為空，返回空 else{

Q[rear++] = root;// 若節(jié)點不為空，則該節(jié)點入隊 while(front!= rear)

{

q = Q[front++];//只要隊列不為空，則節(jié)點依次出隊 cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時，該節(jié)點的雙子入隊

} } } 函數(shù)主體部分：聲明一個類中的對象，調(diào)用構(gòu)造函數(shù)，建立二叉樹，并輸出四種遍歷結(jié)果，檢驗輸出結(jié)果。

int main(){

BiTreeshu;//聲明類中一個對象，在構(gòu)造了一顆樹

BiNode* root = shu.Getroot();//獲取指向根結(jié)點的指針

cout<<“前序遍歷序列為 ”<

程序結(jié)構(gòu)：

主函數(shù)建立一個類模板定義構(gòu)造函數(shù)，析構(gòu)函數(shù)，以及成員函數(shù)聲明類中的一個對象調(diào)用構(gòu)造函數(shù)，構(gòu)造一顆二叉樹層序遍歷二叉樹后序遍歷二叉樹中序遍歷二叉樹前序遍歷二叉樹獲取該二叉樹的根節(jié)點將結(jié)果輸出，人工檢驗 源代碼：

#include using namespace std;

template struct BiNode

{

T data;

BiNode *lchild, *rchild;};

template class BiTree

{ public: BiTree();

//構(gòu)造函數(shù)，初始化一棵二叉樹 ~BiTree(void);

//析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點的存儲空間

BiNode* Getroot();

//獲得指向根結(jié)點的指針

void xianxu(BiNode *root);

//前序遍歷二叉樹

void zhongxu(BiNode *root);

//中序遍歷二叉樹

void houxu(BiNode *root);

//后序遍歷二叉樹

void cengxu(BiNode *root);

//層序遍歷二叉樹 private:

BiNode *root;

BiNode *Creat();

void Release(BiNode *root);

};template BiTree::BiTree(){ this->root = Creat();//利用this指針調(diào)用creat函數(shù) }

template BiNode* BiTree::Creat()//定義構(gòu)造函數(shù) { BiNode* root;T aa;cout<<“請按前序序列方式輸入節(jié)點數(shù)據(jù)，每次輸入一個”<>aa;

if(aa==“*”)root = NULL;

else{

root = new BiNode;

//生成一個結(jié)點

root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

}

return root;}

template BiTree::~BiTree(void){ Release(root);//析構(gòu)函數(shù)，釋放存儲指針?biāo)枰目臻g }

template BiNode* BiTree::Getroot()//獲取根節(jié)點所在指針的位置 { return root;}

template void BiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果節(jié)點為空，則返回空

else{

cout<data<<“ ”;//訪問根節(jié)點

xianxu(root->lchild);//先序遍歷樹的左子樹

xianxu(root->rchild);//先序遍歷樹的右子樹

} }

template void BiTree::zhongxu(BiNode *root){

if(root==NULL)return;

//如果節(jié)點為空，則返回空

else{

zhongxu(root->lchild);

//中序遞歸遍歷root的左子樹

cout<data<<“ ”;

//訪問根結(jié)點

zhongxu(root->rchild);

//中序遞歸遍歷root的右子樹

} }

template void BiTree::houxu(BiNode *root){

if(root==NULL)

return;

//如果節(jié)點為空，返回空

else{

houxu(root->lchild);

//后序遞歸遍歷root的左子樹

houxu(root->rchild);

//后序遞歸遍歷root的右子樹

cout<data<<“ ”;

//訪問根節(jié)點

} }

template void BiTree::cengxu(BiNode *root){

const int MaxSize = 100;int front = 0;int rear = 0;//利用隊列的方法對樹進行層序遍歷

BiNode* Q[MaxSize];

BiNode* q;if(root==NULL)return;// 如果節(jié)點為空，返回空

else{

Q[rear++] = root;// 若節(jié)點不為空，則該節(jié)點入隊

while(front!= rear)

{

q = Q[front++];//只要隊列不為空，則節(jié)點依次出隊

cout<data<<“ ”;

if(q->lchild!= NULL)

Q[rear++] = q->lchild;

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時，該節(jié)點的雙子入隊

} } }

template void BiTree::Release(BiNode* root)//析構(gòu)函數(shù)，釋放存儲空間 {

if(root!= NULL){

Release(root->lchild);

//釋放左子樹

Release(root->rchild);

//釋放右子樹

delete root;

}

}

int main(){

BiTree shu;//聲明類中一個對象，在構(gòu)造了一顆樹

BiNode* root = shu.Getroot();//獲取指向根結(jié)點的指針

cout<<“前序遍歷序列為 ”<

cout<<“層序遍歷序列為”<

通過對結(jié)果的分析，發(fā)現(xiàn)輸出結(jié)果與建立二叉樹時的輸入完全符合，說明程序的運行結(jié)果是正確的。

心得體會：

1)函數(shù)遞歸的方法可以在相當(dāng)程度上使程序簡潔，避免代碼的冗長復(fù)雜。2)構(gòu)造函數(shù)如果帶參數(shù)，在聲明對象的時候應(yīng)該將實參指出來。但是本題中構(gòu)造函數(shù)位遞歸調(diào)用，初始的根節(jié)點的數(shù)據(jù)值由鍵盤輸入，因此無法在聲明對象時引入實參。所以最后選擇了無參但是引用了this指針的構(gòu)造函數(shù)?？梢?，對于構(gòu)造函數(shù)的含參調(diào)用應(yīng)該小心謹(jǐn)慎。

3)編程時，要不停得檢驗自己的輸入與輸出，必要的時候需要人工進行計算，以保證程序的運行按照預(yù)先的設(shè)想。