實驗題目:二叉樹的操作 (實驗四)
實驗者資訊:
實驗完成的時間:
1、 實驗目的
(1) 掌握二叉樹鍊錶的結構和二叉樹的建立過程。
(2) 掌握佇列的先進先出的運算原則在解決實際問題中的應用。
(3) 進一步掌握指標變數、指標陣列、動態變數的含義。
(4) 掌握遞迴程式設計的特點和程式設計方法。
2、 實驗要求
(1) 熟練掌握二叉鍊錶的儲存結構。
(2) 熟練掌握迴圈佇列的基本操作。
(3) 理解所給出的演算法,掌握迴圈佇列在實際中的應用。
(4) 加深對遞迴演算法的理解。
(5) 將上機程式除錯通過,並能獨立完成一至兩個拓展題目。
3、 實驗內容
已知以二叉鍊錶作儲存結構,試編寫按層次遍歷二叉樹的演算法。(所謂層次遍歷,是指從二叉樹的根結點開始從上到下逐層遍歷二叉樹,在同一層次中從左到右依次訪問各個節點。)除錯程式並對相應的輸出作出分析;修改輸入資料,預期輸出並驗證輸出的結果。
加深對演算法的理解。
4、 實驗方法
本演算法要採用乙個迴圈佇列que,先將二叉樹根結點入佇列,然後退佇列,輸出該結點;若它有左子樹,便將左子樹根結點入佇列;若它有右子樹,便將右子樹根結點入佇列,直到佇列空為止。因為佇列的特點是先進先出,從而達到按層次順序遍歷二叉的目的。
#include<>
#include<>
#define m 100
#define null 0
typedef struct node /*二叉鍊錶結點結構*/
bitree;
bitree *que[m]; /*定義乙個指標陣列,說明佇列中的元素型別為bitree指標型別*/
int front=0,rear=0; /*初始化迴圈佇列*/
bitree *creat() /*建立二叉樹的遞迴演算法*/
return t;
}void inorder(bitree *t) /*中序遍歷二叉樹的遞迴演算法*/
}void enqueue(t) /*把bitree型別的結點*t入佇列*/
bitree *t;
}bitree *delqueue()
void levorder(t) /*層次遍歷二叉樹的演算法*/
bitree *t; }}
main() /*主函式*/
執行結果:
5、 預習思考題
除錯好上述程式後,試著完成以下拓展內容:
(1)寫出二叉樹前序遍歷和後序遍歷的遞迴演算法,並在主函式中呼叫它,除錯好程式並分析其執行結果。
void preorder(bitree *t) /*前序遍歷二叉樹的遞迴演算法*/
}void postorder(bitree *t) /*前序遍歷二叉樹的遞迴演算法*/
}(3)寫出二叉樹三種遍歷的非遞迴演算法,並在主函式中呼叫它,除錯好程式並分析其執行結構。
1.先序遍歷非遞迴演算法
#define maxsize 100
typedef struct
sqstack;
void preorderunrec(bitree t)
//endwhile
if (!stackempty(s)) //通過下一次迴圈中的內嵌while實現右子樹遍歷
//endif
}//endwhile
}//preorder
2.中序遍歷非遞迴演算法
#define maxsize 100
typedef struct
sqstack;
void inorderunrec(bitree t)
//endwhile
if (!stackempty(s))
//endif
}//endwhile
}//inorder
3.後序遍歷非遞迴演算法
#define maxsize 100
typedef enum tagtype;
typedef struct
stacknode;
typedef struct
sqstack;
void postorderunrec(bitree t)
while (!stackempty(s) &&
if (!stackempty(s))
}while (!stackempty(s));
}//postorder
6、 分析討論題:
試分析一下遞迴演算法和非遞迴演算法的優缺點。這兩種演算法各有各的妙處。遞迴演算法很巧妙的呼叫函式遞迴的性質,**簡潔;非遞迴演算法則結合前面學習的棧的知識,很好的利用棧的性質,解決了後序遍歷的問題。
7.實驗總結:
通過本次實驗,我學會了二叉樹鍊錶的結構和二叉樹的建立過程。學會了佇列的先進先出的運算原則在解決實際問題中的應用。進一步掌握了指標變數、指標陣列、動態變數的含義。
學會了遞迴程式設計的特點和程式設計方法。
資料結構實驗九 二叉樹實驗
一,實驗題目 設二叉樹採用鏈式儲存結構,試設計乙個演算法計算一顆給定二叉樹中葉子結點的數目。二,問題分析 本程式要求實現計算一顆給定的採用鏈式儲存結構的二叉樹中葉子結點的數目。首先需要用連是儲存結構建立一顆二叉樹,再對該二叉樹先序遍歷輸出,再利用計算葉子結點個數函式計算出葉子結點即可。資料的輸入形式...
二叉樹實驗報告
實驗報告 實驗名稱二叉樹 班級學號 姓名成績 附件 實驗報告說明 1 實驗名稱 要用最簡練的語言反映實驗的內容。2 實驗目的與要求 目的要明確,要抓住重點。3 實驗原理 簡要說明本實驗專案所涉及的理論知識。4 實驗環境 實驗用的軟硬體環境 配置 5 實驗方案設計 思路 步驟和方法等 這是實驗報告極其...
樹和二叉樹實驗任務書
實驗5 樹和二叉樹 一 實驗目的 1 掌握二叉樹的結構特徵,以及各種儲存結構的特點及適用範圍。2 掌握用指標型別描述 訪問和處理二叉樹的運算。二 實驗要求 1.認真閱讀和掌握本實驗的程式。2.上機執行本程式。3.儲存和列印出程式的執行結果,並結合程式進行分析。4.按照二叉樹的操作需要,重新改寫主程式...