-北 京 林 業(yè) 大 學12學年13學年第1學期數(shù)據(jù)結構實驗報告書專 業(yè)：自動化 班 級：111 姓 名： 寧友菊 學 號： 111044120 實驗地點： B2機房 任課教師： 孟偉 實驗題目：二叉樹的基本操作 實驗環(huán)境： Visual C+ 實驗目的：1掌握二叉樹的定義；2掌握二叉樹的基本操作，如建立、前序遍歷、中序遍歷和后序遍歷、結點個數(shù)的統(tǒng)計等；實驗內容：用遞歸的方法實現(xiàn)以下算法：1以二叉鏈表表示二叉樹，建立一棵二叉樹；2輸出二叉樹的前序遍歷結果；3輸出二叉樹的中序遍歷結果；4輸出二叉樹的后序遍歷結果；5統(tǒng)計二叉樹的葉結點個數(shù)；6統(tǒng)計二叉樹的結點個數(shù)；7計算二叉樹的深度。8交換二叉樹每個結點的左孩子和右孩子；實現(xiàn)方法、實驗結果及結論分析等：（一）實現(xiàn)方法1. 所用數(shù)據(jù)結構的定義及其相關說明（相關結構體或類的定義及其含義） 實驗采用二叉樹的數(shù)據(jù)結構，以二叉鏈表存儲，主程序中采用switch函數(shù)調用各個子程序以實現(xiàn)各個功能。0結束程序，輸入錯誤時返回主函數(shù)重新輸入。2. 自定義函數(shù)的名稱及其功能說明 （1）void CreateBiTree 以二叉鏈表表示二叉樹，建立一棵二叉樹；（2）void PreOrderTraverse 輸出二叉樹的前序遍歷結果；（3）void InOrderTraverse 輸出二叉樹的中序遍歷結果；（4）void PostOrderTraverse 輸出二叉樹的后序遍歷結果；（5）int LeafNodeCount 統(tǒng)計二叉樹的葉結點個數(shù)；（6）int Node Count 統(tǒng)計二叉樹的結點個數(shù)；（7）int Depth 計算二叉樹的深度。（8）int Swap 交換二叉樹每個結點的左孩子和右孩子；3. 主要功能算法void PreOrderTraverse的時間復雜度O（n）=O（n1)O(n2)O(n3)O(n4)O(n5)O(n6)O(n7)xO(n8)O（n1)void CreateBiTree函數(shù)算法時間復雜度O(n)O(n2)void PreOrderTraverse函數(shù)算法時間復雜度O(n)O(n3)void InOrderTraverse函數(shù)算法時間復雜度O(n)O(n4)void PostOrderTraverse 函數(shù)算法時間復雜度O(n)O(n5)int LeafNodeCount函數(shù)算法時間復雜度O(n)O(n6)int NodeCount函數(shù)算法時間復雜度O(n)O(n7)int Depth函數(shù)算法時間復雜度O(n) O(n8)int Swap 函數(shù)算法時間復雜度O(n)4. 實驗流程圖（2） 實驗結果1、選擇操作一：2、 創(chuàng)建二叉樹3、 前序遍歷結果4、 中序遍歷結果5、 后序遍歷結果6、 總結點數(shù)7、 葉節(jié)點數(shù)8、 二叉樹深度9、 對換左右孩子10、 退出11、 輸入錯誤檢測（三）結論分析1. 問題與解決方法在編寫程序時，遇到了一個程序保存后編譯正確卻運行不了，之后請教了我們班的同學，才知道是第一個函數(shù)出了問題，改了之后就好了。2. 收獲和體會 做程序編寫時，必須要細心，有時候問題出現(xiàn)了，可能會一直查不出來。自己也不容易發(fā)現(xiàn)。在編寫這個程序時，我就出現(xiàn)了這個問題，之后一定要盡量避