一,實驗題目
設二叉樹採用鏈式儲存結構,試設計乙個演算法計算一顆給定二叉樹中葉子結點的數目。
二,問題分析
本程式要求實現計算一顆給定的採用鏈式儲存結構的二叉樹中葉子結點的數目。首先需要用連是儲存結構建立一顆二叉樹,再對該二叉樹先序遍歷輸出,再利用計算葉子結點個數函式計算出葉子結點即可。
資料的輸入形式和輸入值的範圍:輸入的二叉樹元素為字元型元素。輸入@表示輸入的二叉樹元素為空。輸入#鍵表示輸入結束。
1, 結果的輸出形式:結果輸出的為先序遍歷後的二叉樹元素,其仍為字元型。輸出的葉子結點個數為整型。
2, 測試資料:(1)輸入的二叉樹元素為:3 4 5
2)輸入的二叉樹元素為:3 4 5 5 7 2 3 7 @ 3 @ 6 7 @ 9
三,概要設計
(1)為了實現上述程式的功能,需要:
a,建立一顆二叉樹
b,先序遍歷輸出該二叉樹
c,計算出該二叉樹的葉子結點個數
d,輸出葉子結點個數
(2)本程式包含4個函式:
a,主函式main()
b,建立二叉樹函式creatree()
c,先序遍歷輸出二叉樹函式front()
d,計算葉子結點個數函 num()
各函式間關係如右圖所示:
四,詳細設計
(1)結點型別定義:
typedef struct nodebitree;
bitree *q[maxsize];
(2)建立二叉樹函式偽**:
bitree *creatree()
rear++;q[rear]=s;
if(rear==1) t=s
else
scanf("%c",&ch);}return t;}
(3)先序遍歷輸出二叉樹函式偽**:
void front(bitree *t)}
(4)計算葉子結點個數函式偽**:
int num(bitree *t)
x=x+num(t->lchild); x=x+num(t->rchild);}
return x;}
五,源**
#include ""
#include ""
#define maxsize 100
#define null 0
typedef struct nodebitree;
bitree *q[maxsize]; //定義乙個指向二叉樹的佇列q指標
bitree *creatree()
rear++;
q[rear]=s; //將虛結點指標null或新節點位址入隊
if(rear==1)
t=s輸入的第乙個結點為新結點
else
scanf("%c",&ch);
}return t;
}int num(bitree *t)
x=x+num(t->lchild); //遞迴呼叫
x=x+num(t->rchild);
}return x;
}void front(bitree *t) //先序遍歷輸出二叉樹
}void main()
六,除錯分析
1, 在主函式中,當輸出一棵樹的葉子節點的個數時,用語句printf("%d",&x);除錯時提示沒有錯誤,但輸出的卻是一串位址,再仔細檢查一會才發現原來輸出的是值而不是位址,即printf("%d",x);
2,再輸入二叉樹是也出現了錯誤,計算出來的葉子節點數總是不正確,還以為是計算的函式出了問題,結果在問其他同學時才發現原來輸入二叉樹的元素時,不能輸入空格鍵和回車鍵,因為它們也是乙個字元,也是樹的乙個元素。
七,使用手冊
使用者在使用時,根據介面提示,首先輸入一系列二叉樹元素,當輸入『#』時,二叉樹元素輸入結束。此時,則會輸出先序遍歷二叉樹的結果和該二叉樹的葉子結點個數。注意,在輸入時,@表示空結點,當輸入空格鍵或回車鍵時,也是乙個二叉樹元素,使用者需特別注意。
八,測試結果
資料結構樹與二叉樹實驗報告
樹和二叉樹上機實習 1 實驗目的 1 熟悉二叉樹結點的結構。2 掌握對二叉樹基本操作的實現。3 理解遍歷的概念,會利用遞迴方法編寫對二叉樹結構進行遍歷的演算法。4 理解二叉樹的線索化過程是基於對二叉樹進行遍歷,而線索二叉樹上的線索又為相應的遍歷提供了方便。2 實驗要求 1 二叉樹的儲存及基本操作的實...
資料結構實驗樹和二叉樹的應用
課程題目 資料結構實驗 學院 班級 姓名 學號 實驗題目 樹和二叉樹的應用 實驗內容 哈夫曼編碼設計 實驗目的 掌握樹和二叉樹的概念及工作原理,運用其原理及概念完成上述實驗題中的內容。實驗要求 為了使學生更好的掌握與理解課堂上老師所講的概念與原理,實驗前每個學生要認真預習所做的實驗內容及編寫源程式偽...
實驗四二叉樹
實驗題目 二叉樹的操作 實驗四 實驗者資訊 實驗完成的時間 1 實驗目的 1 掌握二叉樹鍊錶的結構和二叉樹的建立過程。2 掌握佇列的先進先出的運算原則在解決實際問題中的應用。3 進一步掌握指標變數 指標陣列 動態變數的含義。4 掌握遞迴程式設計的特點和程式設計方法。2 實驗要求 1 熟練掌握二叉鍊錶...