第一篇：二叉樹的性質(zhì)總結(jié)
一、二叉樹的性質(zhì)
性質(zhì)
1、二叉樹的第i層上至多有2 i-1（i ?1）個結(jié)點(diǎn)。用數(shù)學(xué)歸納法證明
推廣：k叉樹(或度為k的樹)的第i層上至多有k i-1（i ?1）個結(jié)點(diǎn)
性質(zhì)
2、度為h的二叉樹中至多含有2h-1個結(jié)點(diǎn)。
21-1 + 2 2-1+……+ 2 h-1 = 2 h-1
推廣：深度為h的k叉樹(或度為k的樹)中至多含有(k h-1)/(k-1)個結(jié)點(diǎn)
k1-1 + k 2-1+……+ k h-1 =(k h-1)/(k-1)
性質(zhì)
3、若在任意一棵二叉樹中，有n0個葉子結(jié)點(diǎn)，有n2個度為2的結(jié)點(diǎn)，則：n0=n2+1
證明：設(shè)：有n0個葉子結(jié)點(diǎn)，有n1個度為1的結(jié)點(diǎn)，有n2個度為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個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，nk個度為k的結(jié)點(diǎn)則n0為:
?
i=1 k(i-1)ni+
1性質(zhì)3推廣的證明于性質(zhì)3的證明
設(shè)：有n0個葉子結(jié)點(diǎn)，有n1個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，nk個度為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個結(jié)點(diǎn)的完全二叉樹，其深度為?㏒2n?+1
證明：設(shè)n個結(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
取對數(shù)有：k-1 ? log2n < k
因?yàn)閗是整數(shù)，所以k-1 = ?log2n?，k= ?㏒2n?+1
結(jié)論成立。
推廣: 具有n個結(jié)點(diǎn)的完全k叉樹，其深度為? logk(k-1)n ?+1
設(shè)n個結(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
取對數(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個結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序(每一層從左到右)用自然數(shù)1，2，3……,n給結(jié)點(diǎn)進(jìn)行編號，則對于編號為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)編號為 [k/2 ]。 (2)若2k<=n,則編號為k的左孩子結(jié)點(diǎn)編號為2k;否則該結(jié)點(diǎn)無左孩子結(jié)點(diǎn)(顯然也沒有右孩子結(jié)點(diǎn))。 (3)若2k+1<=n,則編號為k的右孩子結(jié)點(diǎn)編號為2k+1;否則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn) 推廣:一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個結(jié)點(diǎn)都有K棵非空子樹，如果按層次順序從1開始對全部結(jié)點(diǎn)進(jìn)行編號，求： 1）各層的結(jié)點(diǎn)的數(shù)目是多少？ 2）編號為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？ 3）編號為n的結(jié)點(diǎn)的第i 個孩子結(jié)點(diǎn)（若存在）的編號是多少？ 4）編號為n的結(jié)點(diǎn)有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？ 答: h-1(1)k(h為層數(shù)) h-1（2）因?yàn)樵摌涿繉由暇蠯個結(jié)點(diǎn)，從根開始編號為1，則結(jié)點(diǎn)i的從右向左數(shù)第２個 孩子的結(jié)點(diǎn)編號為ki。設(shè)n 為結(jié)點(diǎn)i的子女，則關(guān)系式(i-1)k+2<=n<=ik+1成立，因i是整數(shù)，故結(jié)點(diǎn)n的雙親i的編號為?n-2)/k?+1。 (3)結(jié)點(diǎn)n(n>1)的前一結(jié)點(diǎn)編號為n-1（其最右邊子女編號是(n-1)*k+1），故結(jié)點(diǎn) n的第 i個孩子的編號是(n-1)*k+1+i。 (4)根據(jù)以上分析，結(jié)點(diǎn)n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即(n-1)%k!=0，其右兄弟編號是n+1。 二：滿二叉樹： 一棵深度為k且有2k-1個結(jié)點(diǎn)的二叉樹 特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。葉子結(jié)點(diǎn)在同一層次上；無度為1的結(jié)點(diǎn) 具有n個結(jié)點(diǎn)的滿二叉樹則 葉子結(jié)點(diǎn)的個數(shù)為：（n+1)/2 度為2的結(jié)點(diǎn)的個數(shù)為：（n-1)/2 三、無度為1的結(jié)點(diǎn) 1: 具有n個結(jié)點(diǎn)的無度為1的結(jié)點(diǎn)的二叉樹，求葉子結(jié)點(diǎ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)個數(shù)n0求總的結(jié)點(diǎn)的個數(shù)n N=n0+n2=2n0-1 四、完全二叉樹：深度為k的有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中的編號從1至n的結(jié)點(diǎn)一一對應(yīng) 特點(diǎn)：除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。 葉子結(jié)點(diǎn)在最后兩層上，度為1的結(jié)點(diǎn)的個數(shù)最多為1 1:具有n個結(jié)點(diǎn)的完全二叉樹，求葉子結(jié)點(diǎn)的個數(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)個數(shù)：求總的結(jié)點(diǎn)的個數(shù) n=n0+n1+n2 n1=1 或n1=0n2=n0-1 n最大為2n0,最小為2n0-1 3:若已知完全二叉樹第k層上具有n個葉子結(jié)點(diǎn)，求最多的結(jié)點(diǎn)個數(shù)及最少的結(jié)點(diǎn)個數(shù)最多的結(jié)點(diǎn)個數(shù)：共有k+1層 前k層共有2k-1個結(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)個結(jié)點(diǎn),所以最多結(jié)點(diǎn)數(shù)為2k-1+ 2(2k-1-n) 最少的結(jié)點(diǎn)個數(shù)：共有k層 前k-1層具有2k-1-1個結(jié)點(diǎn)，k層有n個共有2k-1-1+n 實(shí)驗(yàn)報告 二叉樹 一 實(shí)驗(yàn)?zāi)康?/p> 1、進(jìn)一步掌握指針變量，動態(tài)變量的含義； 2、掌握二叉樹的結(jié)構(gòu)特性以及各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍。 3、掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。 4、熟悉各種存儲結(jié)構(gòu)的特征以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題。 二 實(shí)驗(yàn)原理 樹形結(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)系，它在客觀世界中大量存在。遍歷二叉樹的實(shí)質(zhì)是將非線性結(jié)構(gòu)轉(zhuǎn)為線性結(jié)構(gòu)。 三 使用儀器，材料 計(jì)算機(jī) 2 Wndows xp 3 VC6.0 四實(shí)驗(yàn)步驟 【問題描述】建立一個二叉樹，請分別按前序，中序和后序遍歷該二叉樹。【基本要求】從鍵盤接受輸入（按前序順序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以前序來建立），并采用遞歸算法對其進(jìn)行前序，中序和后序遍歷，將結(jié)果輸出。 【實(shí)現(xiàn)提示】按前序次序輸入二叉樹中結(jié)點(diǎn)的值（一個整數(shù)），0表示空樹，葉子結(jié)點(diǎn)的特征是其左右孩子指針為空。 五實(shí)驗(yàn)過程原始記錄 基本數(shù)據(jù)結(jié)構(gòu)描述； 2 函數(shù)間的調(diào)用關(guān)系； 用類C語言描述各個子函數(shù)的算法； 附錄：源程序。 六 試驗(yàn)結(jié)果分析 將實(shí)驗(yàn)結(jié)果分析、實(shí)驗(yàn)中遇到的問題和解決問題的方法以及關(guān)于本實(shí)驗(yàn)項(xiàng)目的心得體會，寫在實(shí)驗(yàn)報告上。 數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報告 學(xué)院： 班級： 學(xué)號： 姓名： 實(shí)驗(yàn)名稱：二叉樹的建立與遍歷 一、實(shí)驗(yàn)?zāi)康模?/p> 1.掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)； 2.掌握二叉樹創(chuàng)建方法； 3.掌握二叉樹的先序、中序、后序的遞歸實(shí)現(xiàn)方法。 二、實(shí)驗(yàn)內(nèi)容和要求： 創(chuàng)建二叉樹，分別對該二叉樹進(jìn)行先序、中序、后序遍歷，并輸出遍歷結(jié)果。 三、叉樹的建立與遍歷代碼如下： #include };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(“建立二叉樹，請輸入結(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)//如果是第一個元素，則作為根節(jié)點(diǎn) { } 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//為#時，計(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)建二叉樹的算法：首先對一般的二叉樹，添加若干個虛結(jié)點(diǎn)使其成為完全二叉樹，然后依次輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個新結(jié)點(diǎn)，若是第一個，則令其為根結(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è)置一個指針類型的數(shù)組構(gòu)成的隊(duì)列來保存已輸入結(jié)點(diǎn)的地址，并使隊(duì)尾(rear)指向當(dāng)前輸入的結(jié)點(diǎn)，隊(duì)頭(front)指向這個結(jié)點(diǎn)的雙親結(jié)點(diǎn)的前一個位置。由于根結(jié)點(diǎn)的地址放在隊(duì)列的第一個單元里，所以當(dāng)rear為奇數(shù)時，則rear所指的結(jié)點(diǎn)應(yīng)作為左孩子與其雙親鏈接，否則rear所指的結(jié)點(diǎn)應(yīng)作為右孩子與其雙親鏈接。若雙親結(jié)點(diǎn)或孩子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無須鏈接。若一個雙親結(jié)點(diǎn)與兩個孩子鏈接完畢，則進(jìn)行出隊(duì)操作，使隊(duì)頭指針指向下一個待鏈接的雙親結(jié)點(diǎn)。 2.void preorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點(diǎn)元素，在每個循環(huán)中每次先讀取，再進(jìn)行進(jìn)入下一個遞歸循環(huán)中。 3.void inorder(TNODE *bt)函數(shù) ：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點(diǎn)元素，在每個循環(huán)中每次先左子樹，再讀取結(jié)點(diǎn)元素，再進(jìn)行進(jìn)入下一個遞歸循環(huán)中。 4.void postorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點(diǎn)元素，在每個循環(huán)中每次先分別進(jìn)入左右子樹，再進(jìn)行讀取，再進(jìn)行進(jìn)入下一個遞歸循環(huán)中。 六、心得體會： 本次數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)對我有一定的幫助。通過這次的實(shí)踐，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更深入地了解。在寫程序的過程中，我重復(fù)地讀課本上的知識，并且漸漸領(lǐng)悟到數(shù)據(jù)結(jié)構(gòu)編程的方法。在編程中，雖然遇到了一些困難，但我并不氣餒。當(dāng)程序運(yùn)行出來時，我感到了快樂。總之，通過自己地探索和努力，思維得到了鍛煉，編程能力也有了較大地改善。 贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 實(shí) 驗(yàn) 報 告 冊 課程名稱：算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目名稱： 實(shí)驗(yàn)5.二叉樹 實(shí)驗(yàn)學(xué)時： 4 學(xué)生學(xué)號與姓名： 實(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)用二叉樹遞歸遍歷思想解決問題的方法。 二、實(shí)驗(yàn)儀器和設(shè)備 Visual C++ 6.0 三、實(shí)驗(yàn)內(nèi)容與過程 1.建立一棵二叉樹。對此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。 2.在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點(diǎn)的個數(shù)。3.在第一題基礎(chǔ)上，求二叉樹的深度。 程序清單： 1.2.3.贛南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 四、實(shí)驗(yàn)結(jié)果與分析（程序運(yùn)行結(jié)果及其分析） 五、實(shí)驗(yàn)體會（遇到問題及解決辦法，編程后的心得體會） 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告二 題目： 用先序遞歸過程監(jiān)理二叉樹（存儲結(jié)構(gòu)：二叉鏈表） 輸入數(shù)據(jù)按先序遍歷輸入，當(dāng)某節(jié)點(diǎn)左子樹或者右子樹為空時，輸入‘*’號，如輸入abc**d**e**時，得到的二叉樹為： 并用如下實(shí)力測試： 算法思路： 顯然，建立一個二叉鏈表存儲的二叉樹，如果不考慮效率要求，考慮到程序的簡介性，遞歸建立和遞歸遍歷是一種很好的辦法。 利用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 template root = new BiNode //生成一個結(jié)點(diǎn) root->data=aa; root->lchild = Creat(); //遞歸建立左子樹 root->rchild = Creat(); //遞歸建立右子樹 } return root;} 構(gòu)造這樣的函數(shù)，可以在輸入時，按先序遍歷順序每次輸入一個節(jié)點(diǎn)的數(shù)據(jù)，可以實(shí)現(xiàn)任意二叉樹的構(gòu)造。 為了檢驗(yàn)構(gòu)造的二叉樹是否為預(yù)先設(shè)想的二叉樹，需要遍歷二叉樹并進(jìn)行輸出。考慮到單一的輸出并不能確定唯一的二叉樹，因此對遍歷二叉樹的四種常用發(fā)方法，即先序遍歷，中序遍歷，后續(xù)遍歷，層次遍歷分別實(shí)現(xiàn)，通過遍歷結(jié)果檢驗(yàn)構(gòu)造的二叉樹是否為預(yù)先設(shè)計(jì)好的二叉樹。 先序遍歷：采用遞歸的方法建立。template xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹 } 中序遍歷：遞歸方法建立： template if(root==NULL)return; //如果節(jié)點(diǎn)為空，則返回空 else{ zhongxu(root->lchild); //中序遞歸遍歷root的左子樹 cout< //訪問根結(jié)點(diǎn) zhongxu(root->rchild); //中序遞歸遍歷root的右子樹 } } 后序遍歷：遞歸方法建立： template if(root==NULL) return; //如果節(jié)點(diǎn)為空，返回空 else{ houxu(root->lchild); //后序遞歸遍歷root的左子樹 houxu(root->rchild); //后序遞歸遍歷root的右子樹 cout< //訪問根節(jié)點(diǎn) } } 層序遍歷：采用非遞歸方法。利用隊(duì)列的方法層序遍歷二叉樹。建立一個隊(duì)列，在訪問一個節(jié)點(diǎn)的時候，把它的左孩子和右孩子入隊(duì)，并且將這個節(jié)點(diǎn)出隊(duì)。當(dāng)隊(duì)列為空時，就完成了對二叉樹的層序遍歷。 template Q[rear++] = root;// 若節(jié)點(diǎn)不為空，則該節(jié)點(diǎn)入隊(duì) while(front!= rear) { q = Q[front++];//只要隊(duì)列不為空，則節(jié)點(diǎn)依次出隊(duì) cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同時，該節(jié)點(diǎn)的雙子入隊(duì) } } } 函數(shù)主體部分：聲明一個類中的對象，調(diào)用構(gòu)造函數(shù)，建立二叉樹，并輸出四種遍歷結(jié)果，檢驗(yàn)輸出結(jié)果。 int main(){ BiTree BiNode cout<<“前序遍歷序列為 ”< 程序結(jié)構(gòu)： 主函數(shù)建立一個類模板定義構(gòu)造函數(shù)，析構(gòu)函數(shù)，以及成員函數(shù)聲明類中的一個對象調(diào)用構(gòu)造函數(shù)，構(gòu)造一顆二叉樹層序遍歷二叉樹后序遍歷二叉樹中序遍歷二叉樹前序遍歷二叉樹獲取該二叉樹的根節(jié)點(diǎn)將結(jié)果輸出，人工檢驗(yàn) 源代碼： #include template { T data; BiNode template { public: BiTree(); //構(gòu)造函數(shù)，初始化一棵二叉樹 ~BiTree(void); //析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲空間 BiNode //獲得指向根結(jié)點(diǎn)的指針 void xianxu(BiNode //前序遍歷二叉樹 void zhongxu(BiNode //中序遍歷二叉樹 void houxu(BiNode //后序遍歷二叉樹 void cengxu(BiNode //層序遍歷二叉樹 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一個結(jié)點(diǎn) root->data=aa; root->lchild = Creat(); //遞歸建立左子樹 root->rchild = Creat(); //遞歸建立右子樹 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍歷樹的左子樹 xianxu(root->rchild);//先序遍歷樹的右子樹 } } template if(root==NULL)return; //如果節(jié)點(diǎn)為空，則返回空 else{ zhongxu(root->lchild); //中序遞歸遍歷root的左子樹 cout< //訪問根結(jié)點(diǎn) zhongxu(root->rchild); //中序遞歸遍歷root的右子樹 } } template if(root==NULL) return; //如果節(jié)點(diǎn)為空，返回空 else{ houxu(root->lchild); //后序遞歸遍歷root的左子樹 houxu(root->rchild); //后序遞歸遍歷root的右子樹 cout< //訪問根節(jié)點(diǎn) } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用隊(duì)列的方法對樹進(jìn)行層序遍歷 BiNode BiNode else{ Q[rear++] = root;// 若節(jié)點(diǎn)不為空，則該節(jié)點(diǎn)入隊(duì) while(front!= rear) { q = Q[front++];//只要隊(duì)列不為空，則節(jié)點(diǎn)依次出隊(duì) cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同時，該節(jié)點(diǎn)的雙子入隊(duì) } } } template if(root!= NULL){ Release(root->lchild); //釋放左子樹 Release(root->rchild); //釋放右子樹 delete root; } } int main(){ BiTree BiNode cout<<“前序遍歷序列為 ”< cout<<“層序遍歷序列為”< 通過對結(jié)果的分析，發(fā)現(xiàn)輸出結(jié)果與建立二叉樹時的輸入完全符合，說明程序的運(yùn)行結(jié)果是正確的。 心得體會： 1)函數(shù)遞歸的方法可以在相當(dāng)程度上使程序簡潔，避免代碼的冗長復(fù)雜。2)構(gòu)造函數(shù)如果帶參數(shù)，在聲明對象的時候應(yīng)該將實(shí)參指出來。但是本題中構(gòu)造函數(shù)位遞歸調(diào)用，初始的根節(jié)點(diǎn)的數(shù)據(jù)值由鍵盤輸入，因此無法在聲明對象時引入實(shí)參。所以最后選擇了無參但是引用了this指針的構(gòu)造函數(shù)。可見，對于構(gòu)造函數(shù)的含參調(diào)用應(yīng)該小心謹(jǐn)慎。 3)編程時，要不停得檢驗(yàn)自己的輸入與輸出，必要的時候需要人工進(jìn)行計(jì)算，以保證程序的運(yùn)行按照預(yù)先的設(shè)想。第二篇：實(shí)驗(yàn)報告：二叉樹
第三篇：二叉樹遍歷課程設(shè)計(jì)】
第四篇：實(shí)驗(yàn)5_二叉樹
第五篇：數(shù)據(jù)結(jié)構(gòu)作業(yè)——二叉樹
點(diǎn)擊咨詢 