合肥學院
電腦科學與技術系
課程設計報告
2009～2010學年第二學期
2023年6月
題目：列印二叉樹結構
一、問題分析和任務定義：
1、問題分析：
本任務的要求是：按凹入錶形式橫向列印任意二叉樹結構，即二叉樹的根在螢幕的最左邊，二叉樹的左子樹在螢幕的下邊，二叉樹的右子樹在螢幕的上邊。
所謂列印二叉樹，即將二叉樹的結點按樹形的形狀橫向反應出來。由圖可以看出：二叉樹的根結點a在最左端，右結點c在最上端，左結點b在最下端，即實現了二叉樹的橫向列印。
通過圖示還可以看出，列印後的二叉樹按行依次序讀出得到序列cfeadb，這與二叉樹中序遍歷rdl序列相同，因此在設計演算法時可以通過中序遍歷思想來決定結點輸出次序，又因為二叉樹結點的位置各不相同，因此可以通過其深度來確定其在螢幕上的位置。
2：任務定義：
要將二叉樹列印出來，首先需要建立乙個二叉樹，在其建表的過程中採用什麼樣的儲存結構更為簡便，更能很好有解決問題，同時思考順序表與鍊錶對於本程式兩者的優缺點各有哪些。這是首要注意的問題。同時還要思考如何建立二叉樹，對結點進行虛、實兩種結點的輸入，如何設計演算法，求出二叉樹各結點的深度，從而確定結點在螢幕上的橫向位置，如何將二叉樹的各結點按行列印出來，並以樹形形狀在螢幕上顯示出來，這些都將是在設計本程式時逐一要解決的問題。
二、概要設計與資料結構選擇
1、二叉樹資料結構
二叉樹的儲存結構有順序表、鍊錶兩種方式。考慮到順序表在儲存時儲存空間的浪費以及操作的不方便，因此本程式採用鏈式儲存更能解決問題。二叉樹是最簡單的樹形結構，它有許多固有屬性：
①二叉樹最多有兩個孩子。②二叉樹在第i層上至多有2i-1個結點。③二叉具有先序，中序，後序三種遍歷方法…… 因此，通過二叉樹這些屬性設計二叉樹的儲存結構：
資料域（data）——用於儲存結點資訊；考慮到每個父親有兩個孩子結點，因此設計兩個指標域：左孩子（lchild）和右孩子（rchild）——分別指向結點的左孩子結點和右孩子結點。用圖示表示如下：
資料型別定義為：
typedef struct nodebitree;
2、二叉樹的建立
逐層輸入二叉樹的結點，若某個結點為空，剛為其補充乙個虛結點，將乙個任意的二叉樹補成一棵滿二叉樹，直到輸入結束。將第乙個輸入的結點置為根結點，而將其它新輸入的結點作為孩子鏈結到其父親結點上。
3、中序遍歷二叉樹
由於要實現二叉樹的橫向列印。因此採用遍歷思想將結點逐個輸出。根據題意運用二叉樹的中序遍歷最為簡捷。即先遍歷其右孩子，再遍歷父親結點，最後遍歷左孩子。演算法步驟如下：
1 中序遍歷右子樹，遞迴呼叫遍歷二叉樹
2 訪問根結點
3 中序遍歷左子樹，遞迴呼叫遍歷二叉樹
4、橫向列印二叉樹
運用中序遍歷二叉樹演算法思想來決定二叉樹結點的輸出次序。運用二叉樹的深度來決定二叉樹結點的橫向位置。根結點的層次為1，每遞迴呼叫一次層次加1，直到呼叫到葉子結點。
所以每一行均有乙個結點輸出。在輸出結點時，先用深度控制結點前要輸入的空格數，然後再輸出結點資訊。
三、詳細設計和編碼
二叉樹建立過程：
建樹過程可以採用遞迴演算法和非遞迴演算法兩種方式。在這裡我運用佇列的知識用非遞迴方法建立二叉樹，具體步驟如下：
①義乙個指標陣列*q[front]用於存放已輸入的結點位址。它的頭指標front指向父親結點，尾指標rear記錄當前輸入的結點。
②始化佇列。置front為1，rear為0；二叉樹結點型別t置為空樹。若輸入的結點不為空則入隊；若輸入的結點為第乙個結點，即rear=1；將其置為根結點。
③斷孩子結點是還輸入完畢。每輸入乙個結點時，將其左右孩子置空，即s->lchild=s->rchild=null。隊尾指標rear為偶數（rear%2==0）則表示輸入的結點為左孩子；
隊尾指標為奇數（rear%2==1）則表示輸入的結點為右孩子，同時佇列頭指標後移。
④輸入的結點為虛結點，則不為結點分配儲存空間。
⑤復上述過程，直接輸入的結束符號時輸入結束。
源**：
bitree *q[maxsize];/*佇列q為指標型別*/
bitree *creatree()
rear++;q[rear]=s;/*將虛結點指標null或新結點位址入隊*/
if(rear==1)
t=s;/*輸入的第乙個結點為根結點*/
else
ch=getchar();
}return t;
}二叉樹建立過程：
對於任意一棵二叉樹，如圖所示則按層次輸入結點信自己依次為abc@ef@@@@@b#（其中@表示虛結點，#表示輸入結束）。
列印二叉樹詳細設計：
判斷二叉樹還為空，若不空，將深度置為0，depth=0用自身遍歷右樹，並使其深度加1。printtree(bt->rchild,depth+1);通過深度控制橫向位置,可以多打些空格,使輸出更美觀for(int i=1;i<4*depth;i++)printf(" ");輸出結點資訊;再遞迴呼叫左子樹,深度加1 printtree(bt->lchild,depth+1);程式結束.
該演算法源**如下:
void printtree(bitree *bt,int depth) /* 按豎向樹狀列印的二叉樹 */
四、上機除錯
除錯中遇到的問題
1、因為採用佇列建立二叉樹，因此在建立二叉樹的過程中會出現隊滿的情況，開始時，將佇列長度置為10，但是在程式執行時出現了誤。認真檢驗源程式並思考後，找到原因就在於儲存空間的分配上出現了問題。因此將隊死的長度置為50。
這樣，雖然還是有空間佔滿的情況，但基本已解決問題。
2、二叉樹結點橫向位置不固定，即輸入的不同二叉樹根結點的橫向位置不固定，經過分析得出是因為將三叉樹結點的深度搞錯了，在子函式printtree(bitree *bt,int depth)，根結點的度因該為1，因此實參因為0。開始時就將計算出的二叉樹的度作為實參導致結果的不正確。修正後執行正常。
3、在程式設計初期，我寫了個計算二叉樹深度的子函式，經過除錯發現，刪除後程式仍正常執行。所以子函式在程式中沒有用處，經過分析認識到：雖然二叉樹的結點人橫向位置是由淇深度確定的，但列印二叉樹結點時不需要通過函式計算其結點深度，只需要用遞迴逐個對結點遍歷時每層深度加一即可，所以考慮到程式的簡捷，將該子函式刪除。
4、通過執行程式發現有的二叉樹結點不能列印出來。例如abc@de@fg#序列，如果進行程式執行會發現，二叉樹結點只能列印abcde五個結點，而fg不能在螢幕上反應出來，以為是程式出現錯誤，所以經過檢驗源程式，但是發現源程式沒有錯誤。通過多次實驗了解到不是源程式有錯誤，而是輸入的結點fg的父結點為虛結點，因此其孩子結點也將不存在，故兩個結點都沒顯示出來
五、測試結果及分析
測試結果為分別為有虛結點和無虛結點兩種情況。
六、使用者使用說明
按完全二叉樹的順序輸入二叉樹各個結點，但是輸入的時個要按層次輸入，即先輸入第一層，再輸入第二層，不是實結點的結點要輸入成虛結點不能不輸入。輸入的結點要能夠建立成乙個二叉樹，如我上面提到的，如果二叉樹的父親結點為虛結點，則它的孩子結點也不可能是實結點，如abc@@der#就是個錯誤的二叉樹，它只能顯示前面幾個結點。而abc@@de@@@@r#這就是個正確的輸入序列。
此外該程式可以實現迴圈輸入，按任務鍵（除結束符外）就成實現程式的迴圈輸入。
七、參考資料
1、譚浩強 c程式設計清華大學出版社 2023年七月第三版
2、王崑崙李紅色資料結構與演算法中國鐵道出版社2023年六月第7版
八、附錄
列印二叉樹結構源程式如下：
#include""
#include""
#define maxsize 50
#define null 0
typedef struct nodebitree;
bitree *q[maxsize];/*佇列q為指標型別*/
bitree *creatree(){/*佇列建立二叉樹，返回根指標*/
char ch;
int front,rear;
bitree *t,*s;
t=null;/*置空二叉樹*/
front=1;rear=0;/*置空佇列*/
printf("\t輸入結點(#號結束,@為虛結點):");
ch=getchar();
while(ch!='#'){/*不是結束符號繼續*/
s=null;/*如果輸入的是虛結點，剛無需為虛結點申請空間*/
if(ch表示虛結點，不是虛結點時建立新結點*/
s=(bitree *)malloc(sizeof(bitree));
資料結構二叉樹基本演算法
資料結構實驗報告 實驗四二叉樹儲存結構的應用 實驗內容 二叉樹各種演算法的實現 專業班級 網路工程專業 1002班 組長 賈鑫 2010100234 組員 賈鵬飛 2010100237 鄧桐桐 2010100229 2012年 4月 27日 實驗報告 實驗型別 綜合實驗室 軟體實驗室二一 實驗名稱 ...
資料結構與演算法 二叉樹的儲存結構
順序儲存結構 該方法是把二叉樹的所有結點按照一定的線性次序儲存到一片連續的儲存單元中。結點在這個序列中的相互位置還能反映出結點之間的邏輯關係。1 完全二叉樹結點編號 1 編號辦法 在一棵n個結點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結點編號，能得到乙個反映整個二叉樹結構的線性序...
資料結構練習二叉樹
學號 31301374 姓名張一博班級軟體工程1301 一 選擇題 1 按照二叉樹定義，具有3個結點的二叉樹共有 c 種形態。a 3 b 4 c 5d 6 2 具有五層結點的完全二叉樹至少有 d 個結點。a 9 b 15 c 31 d 16 3 以下有關二叉樹的說法正確的是 b a 二叉樹的度為2b...