2008級資料結構實驗報告
實驗名稱： 實驗三——樹
學生姓名：
班級：班內序號：
學號：日期： 2023年11月22日
1．實驗要求
根據二叉樹的抽象資料型別的定義，使用二叉鍊錶實現乙個二叉樹。
二叉樹的基本功能：
1、二叉樹的建立
2、前序遍歷二叉樹
3、中序遍歷二叉樹
4、後序遍歷二叉樹
5、按層序遍歷二叉樹
6、求二叉樹的深度
7、求根結點到指定結點的路徑
8、二叉樹的銷毀
9、其他：自定義操作
編寫測試main()函式測試線性表的正確性
2. 程式分析
2.1 儲存結構
頭指標root
二叉樹的二叉鍊錶儲存示意圖
2.2 關鍵演算法分析
2.2.1前序遍歷
1、root為空，返回。
2、root不為空
2.1 輸出根結點
2.2 遞迴前序遍歷左子樹
2.3 遞迴前序遍歷右子樹
2.2.2中序遍歷
1、root為空，返回。
2、root不為空
2.2 遞迴中序遍歷左子樹
2.1 輸出根結點
2.3 遞迴中序遍歷右子樹
2.2.3 後序遍歷
1、root為空，返回。
2、root不為空
2.2 遞迴後序遍歷左子樹
2.3 遞迴後序遍歷右子樹
2.1 輸出根結點
2.2.4 層序遍歷
1、佇列初始化
2、如果二叉樹非空，將跟指標入隊
3、迴圈直到隊列為空
3.1 q=佇列的隊頭元素出隊
3.2 訪問結點q的資料域
3.3 如果結點q存在左孩子，則將左孩子指標入隊
3.4 如果結點q存在右孩子，則將右孩子指標入隊
2.2.5 求路徑
1、初始化順序棧指標和t為根節點
2、迴圈直到t為空或棧為空
2.1 迴圈直到根結點為空
2.1.1棧頂指標加一
2.2.2根結點入棧stack，棧0入棧tag
2.2.3根結點指向左孩子
2.2迴圈直到棧頂指標為空且tag[top]=1
2.2.1將stack頂指標的元素賦給t
2.2.2找到值為p的結點，顯示路徑
2.2.3否則，出棧
2.3如果棧不為空
2.3.1掃瞄右子樹
2.3.2 tag[top]置1
2.2.5求深度
1、根結點為空，返回
2、根結點不為空
2.1 遞迴求左子樹路徑長度hl
2.2 遞迴求右子樹路徑長度hr
2.3 取左hl,hr中的最大值加一即為深度
3. 程式執行結果
4. 總結
一、 除錯時出現的問題
1、 剛開始寫程式的時候有一些沒有定義的函式。定義後，解決。
2、 沒有寫 #include "" 導致出現很多的錯誤。
3、 不能很好的呼叫帶形參的建構函式。所以，將建構函式寫成了不帶引數的函式，並且，將其呼叫的creat（）函式也寫為不帶參的函式。解決了該問題。
4、 當把depth(root)函式中比大小的語句寫為return max(hl,hr)+1時，系統不能識別。新增 #include 後，仍然不能識別。所以，將這條語句改為 hl>hr?
(hl+1):(hr+1); 就沒有問題了。
5、 對於系統總是說 不正確。後來發現，在類的定義中，我將path函式的宣告寫成了path(binode* root,binode* data)。而在主函式中，我將data定義為乙個char型的變數。
這樣就造成了形參和實參的不匹配，自然會出錯。
二、 心得體會
資料的儲存順序可以通過乙個二叉樹的結構來實現。而對於同乙個二叉樹，又可以用前序遍歷，中序遍歷，後序遍歷，層序遍歷的不同順序進行遍歷。通過樹的結構，可以找到元素和元素之間的順序關係。
三、 下一步的改進
1、 加強帶形參的建構函式的呼叫及其有關方面的知識
2、 對於這個函式本身，在求函式路徑上，應考慮二叉樹中有相同值的元素的情況。
資料結構試驗 二叉樹
實驗報告名稱 姓名學號專業班級 日期實驗6 二叉樹的建立及遍歷 一 實驗目的 1 學會實現二叉樹結點結構和對二叉樹的基本操作。2 掌握對二叉樹每種操作的具體實現，學會利用遞迴方法編寫對二叉樹這種遞迴資料結構進行處理的演算法。二 實驗要求 1 認真閱讀和掌握和本實驗相關的教材內容。2 編寫完整程式完成...
資料結構實驗五樹
1 掌握二叉樹的基本特性 2 掌握二叉樹的遞迴遍歷演算法 3 理解二叉樹的非遞迴演算法 4 通過二叉樹的深度和層次遍歷演算法，理解二叉樹的基本特性 1 閱讀並執行下面程式，根據輸入寫出執行結果，並畫出二叉樹的形態。include include define max 20 typedef struc...
資料結構試驗 三
實驗三 迴圈佇列 實驗學時 2學時 一 實驗目的 1 掌握迴圈佇列的儲存結構 2 掌握在迴圈佇列上進行的各種操作。二 實驗內容 1 編寫迴圈佇列的建立函式 2 編寫迴圈佇列的進隊 出隊 初始化等函式。三 實驗重點 對迴圈佇列的特點理解。四 實驗難點 迴圈佇列操作函式的編寫。五 實驗要求 1 用c語言...