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

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

性質(zhì)

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

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

性質(zhì)

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

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

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

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

性質(zhì)

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

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

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

因?yàn)閚=m+1（3）

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

整理得：n0= n2+1

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

?

i=1 k(i-1)ni+

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

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

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

因?yàn)閚=m+1（3）

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

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

性質(zhì)

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

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

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

顯然有：

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

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

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

結(jié)論成立。

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

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

h層滿二叉樹的結(jié)點(diǎn)總數(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

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

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

性質(zhì)

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

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

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

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

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

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

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

3）編號(hào)為n的結(jié)點(diǎn)的第i 個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？

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

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

h-1（2）因?yàn)樵摌涿繉由暇蠯個(gè)結(jié)點(diǎn)，從根開始編號(hào)為1，則結(jié)點(diǎn)i的從右向左數(shù)第２個(gè)

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

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

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

二：滿二叉樹：

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

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

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

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

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

三、無(wú)度為1的結(jié)點(diǎn)

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

n1=0

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

n=2n0-1

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

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

N=n0+n2=2n0-1

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

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

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

1:具有n個(gè)結(jié)點(diǎn)的完全二叉樹，求葉子結(jié)點(diǎn)的個(gè)數(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é)點(diǎn)個(gè)數(shù)：求總的結(jié)點(diǎn)的個(gè)數(shù)

n=n0+n1+n2

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

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

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

前k層共有2k-1個(gè)結(jié)點(diǎn)

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

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

第二篇：實(shí)驗(yàn)報(bào)告：二叉樹

實(shí)驗(yàn)報(bào)告 二叉樹

一 實(shí)驗(yàn)?zāi)康?/p>

1、進(jìn)一步掌握指針變量，動(dòng)態(tài)變量的含義；

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

3、掌握用指針類型描述、訪問(wèn)和處理二叉樹的運(yùn)算。

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

二 實(shí)驗(yàn)原理

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

三 使用儀器，材料 計(jì)算機(jī) 2 Wndows xp 3 VC6.0

四實(shí)驗(yàn)步驟

【問(wèn)題描述】建立一個(gè)二叉樹，請(qǐng)分別按前序，中序和后序遍歷該二叉樹。【基本要求】從鍵盤接受輸入（按前序順序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以前序來(lái)建立），并采用遞歸算法對(duì)其進(jìn)行前序，中序和后序遍歷，將結(jié)果輸出。

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

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

六 試驗(yàn)結(jié)果分析

將實(shí)驗(yàn)結(jié)果分析、實(shí)驗(yàn)中遇到的問(wèn)題和解決問(wèn)題的方法以及關(guān)于本實(shí)驗(yàn)項(xiàng)目的心得體會(huì)，寫在實(shí)驗(yàn)報(bào)告上。

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

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

學(xué)院： 班級(jí)： 學(xué)號(hào)：

姓名：

實(shí)驗(yàn)名稱：二叉樹的建立與遍歷

一、實(shí)驗(yàn)?zāi)康模?/p>

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

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

二、實(shí)驗(yàn)內(nèi)容和要求：

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

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

#include #include struct tnode//結(jié)點(diǎn)結(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;//初始隊(duì)列中需要的變量front、rear和計(jì)數(shù)器counter char ch;printf(“建立二叉樹，請(qǐng)輸入結(jié)點(diǎn):（#表示虛節(jié)點(diǎn),!表示結(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;//把非#的元素入隊(duì)

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

} else {

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

}

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

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

}

}

}

}

front++;

counter++;

else//為#時(shí)，計(jì)數(shù)，但不連接結(jié)點(diǎn) {

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;

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

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

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

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

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

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

六、心得體會(huì)：

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

第四篇：實(shí)驗(yàn)5_二叉樹

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

實(shí) 驗(yàn) 報(bào) 告 冊(cè)

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

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

實(shí)驗(yàn)5 二叉樹

一、實(shí)驗(yàn)?zāi)康暮鸵?/p>

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

二、實(shí)驗(yàn)儀器和設(shè)備

Visual C++ 6.0

三、實(shí)驗(yàn)內(nèi)容與過(guò)程

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

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

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

四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析）

五、實(shí)驗(yàn)體會(huì)（遇到問(wèn)題及解決辦法，編程后的心得體會(huì)）

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

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告二

題目：

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

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

并用如下實(shí)力測(cè)試：

算法思路：

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

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

初始化：利用構(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<<“請(qǐng)按前序序列方式輸入節(jié)點(diǎn)數(shù)據(jù)，每次輸入一個(gè)”<>aa;if(aa==“*”)root = NULL;else{

root = new BiNode;

//生成一個(gè)結(jié)點(diǎn) root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

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

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

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

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

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

if(root==NULL)return;

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

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

//訪問(wèn)根結(jié)點(diǎn)

zhongxu(root->rchild);

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

}

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

if(root==NULL)

return;

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

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

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

//訪問(wèn)根節(jié)點(diǎn)

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

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

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

{

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

if(q->lchild!= NULL)

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

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時(shí)，該節(jié)點(diǎn)的雙子入隊(duì)

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

int main(){

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

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

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

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

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

#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é)點(diǎn)的存儲(chǔ)空間

BiNode* Getroot();

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

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<<“請(qǐng)按前序序列方式輸入節(jié)點(diǎn)數(shù)據(jù)，每次輸入一個(gè)”<>aa;

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

else{

root = new BiNode;

//生成一個(gè)結(jié)點(diǎn)

root->data=aa;

root->lchild = Creat();

//遞歸建立左子樹

root->rchild = Creat();

//遞歸建立右子樹

}

return root;}

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

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

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

else{

cout<data<<“ ”;//訪問(wèn)根節(jié)點(diǎn)

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

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

} }

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

if(root==NULL)return;

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

else{

zhongxu(root->lchild);

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

cout<data<<“ ”;

//訪問(wèn)根結(jié)點(diǎn)

zhongxu(root->rchild);

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

} }

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

if(root==NULL)

return;

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

else{

houxu(root->lchild);

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

houxu(root->rchild);

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

cout<data<<“ ”;

//訪問(wèn)根節(jié)點(diǎn)

} }

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

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

BiNode* Q[MaxSize];

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

else{

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

while(front!= rear)

{

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

cout<data<<“ ”;

if(q->lchild!= NULL)

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

if(q->rchild!= NULL)

Q[rear++] = q->rchild;// 同時(shí)，該節(jié)點(diǎn)的雙子入隊(duì)

} } }

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

if(root!= NULL){

Release(root->lchild);

//釋放左子樹

Release(root->rchild);

//釋放右子樹

delete root;

}

}

int main(){

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

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

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

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

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

心得體會(huì)：

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

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