數(shù)據(jù)結(jié)構(gòu)C二叉樹試驗報告

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)C二叉樹試驗報告

北京林業(yè)大學

12學年—13學年第1學期數(shù)據(jù)結(jié)構(gòu)試驗報告書

專業(yè)：自動化班級：11－1姓名：寧友菊學號：111044120試驗地點：B2機房任課教師：孟偉

試驗題目：二叉樹的基本操作試驗環(huán)境：VisualC++試驗目的：

1．把握二叉樹的定義；

2．把握二叉樹的基本操作，如建立、前序遍歷、中序遍歷和后序遍歷、結(jié)點個數(shù)的統(tǒng)計等；

試驗內(nèi)容：

用遞歸的方法實現(xiàn)以下算法：

1．以二叉鏈表表示二叉樹，建立一棵二叉樹；2．輸出二叉樹的前序遍歷結(jié)果；3．輸出二叉樹的中序遍歷結(jié)果；4．輸出二叉樹的后序遍歷結(jié)果；5．統(tǒng)計二叉樹的葉結(jié)點個數(shù)；6．統(tǒng)計二叉樹的結(jié)點個數(shù)；

7．計算二叉樹的深度。

8．交換二叉樹每個結(jié)點的左孩子和右孩子；

實現(xiàn)方法、試驗結(jié)果及結(jié)論分析等：

（一）實現(xiàn)方法

1.所用數(shù)據(jù)結(jié)構(gòu)的定義及其相關說明（相關結(jié)構(gòu)體或類的定義及其含義）

試驗采用二叉樹的數(shù)據(jù)結(jié)構(gòu)，以二叉鏈表存儲，主程序中采用switch函數(shù)調(diào)用各個子程序以實現(xiàn)各個功能。0終止程序，輸入錯誤時返回主函數(shù)重新輸入。

2.自定義函數(shù)的名稱及其功能說明（1）voidCreateBiTree以二叉鏈表表示二叉樹，建立一棵二叉樹；

（2）voidPreOrderTraverse輸出二叉樹的前序遍歷結(jié)果；

（3）voidInOrderTraverse輸出二叉樹的中序遍歷結(jié)果；（4）voidPostOrderTraverse輸出二叉樹的后序遍歷結(jié)果；（5）intLeafNodeCount統(tǒng)計二叉樹的葉結(jié)點個數(shù)；

（6）intNodeCount統(tǒng)計二叉樹的結(jié)點個數(shù)；

（7）intDepth計算二叉樹的深度。

（8）intSwap交換二叉樹每個結(jié)點的左孩子和右孩子；

3.主要功能算法voidPreOrderTraverse的時間繁雜度

O（n）=O（n1)O(n2)O(n3)O(n4)O(n5)O(n6)O(n7)xO(n8)O（n1)——voidCreateBiTree函數(shù)算法時間繁雜度O(n)O(n2)——voidPreOrderTraverse函數(shù)算法時間繁雜度O(n)O(n3)——voidInOrderTraverse函數(shù)算法時間繁雜度O(n)O(n4)——voidPostOrderTraverse函數(shù)算法時間繁雜度O(n)O(n5)——intLeafNodeCount函數(shù)算法時間繁雜度O(n)O(n6)——intNodeCount函數(shù)算法時間繁雜度O(n)O(n7)——intDepth函數(shù)算法時間繁雜度O(n)O(n8)——intSwap函數(shù)算法時間繁雜度O(n)

4.試驗流程圖

（二）試驗結(jié)果1、選擇操作一：

2、創(chuàng)立二叉樹

3、前序遍歷結(jié)果

4、中序遍歷結(jié)果

5、后序遍歷結(jié)果

6、總結(jié)點數(shù)

7、葉節(jié)點數(shù)

8、二叉樹深度

9、對換左右孩子

10、退出

11、輸入錯誤檢測

（三）結(jié)論分析

1.問題與解決方法在編寫程序時，遇到了一個程序保存后編譯正確卻運行不了，之后請教了我們班的同學，才知道是第一個函數(shù)出了問題，改了之后就好了。2.收獲和體會

做程序編寫時，必需要細心，有時候問題出現(xiàn)了，可能會一直查不出來。自己也不簡單發(fā)現(xiàn)。在編寫這個程序時，我就出現(xiàn)了