二叉樹的建立和遍歷實驗報告.docx

《二叉樹的建立和遍歷實驗報告.docx》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、【二叉樹的建立和遍歷實驗報告】二叉樹的遍歷實驗心得　　[題目]建立二叉樹并求指定結點路徑、深度、葉子個數和左右子樹交換?！　問題描述]　　要求能夠按先序遍歷次序輸入二叉樹中結點的值來構造二叉樹T；然后用遞歸和非遞歸算法實現二叉樹T的中序遍歷；接著編寫算法實現求二叉樹T中指定結點的路徑，即從鍵盤輸入二叉樹T的任一結點，可以輸出從根結點到該結點所經歷的結點；最后編寫二叉樹的三個應用算法。　　[基本要求]　　分別建立二叉樹存儲結構的輸入輸出函數、輸出中序遍歷函數、指定節(jié)點路徑函數、求深度函數、求葉子個數函數和將二叉樹左右子樹交換函數　　一

2、、需求與規(guī)格說明　　1、定義二叉樹的存儲結構，每個結點中設置三個域，即值域、左指針域、右指針域。要建立二叉樹T的鏈式存儲結構，即建立二叉鏈表。根據輸入二叉樹結點的形式不同，建立的方法也不同，本系統采用先序序列遞歸建立二叉樹，建立如下圖所示的二叉樹。應該在程序運行窗口的主控菜單后，先選擇“1”并回車，緊接著在程序運行窗口中提示信息“輸入二叉樹的先序序列結點值:”之后，采用以下字符序列：abc@@de@g@@f@@@作為建立二叉樹T的輸入字符序列并回車，窗口出現：二叉樹的鏈式存儲結構建立完成!　　圖1二叉樹的圖形結構　　2、二叉樹的遍歷。

3、本系統采用非遞歸中序遍歷算法進行中序遍歷，這意味著遍歷右子樹時不再需要保存當前層的根指針，可直接修改棧頂記錄中的指針即可。需要在程序運行窗口的主控菜單中選擇“2”并回車，程序運行窗口會出現以下中序遍歷序列：　　該二叉樹　　的中序遍歷序列是:cbegdfa　　3、求二叉樹的指定結點路徑。在程序運行窗口的主控菜單中選擇“3”并回車，在程序運行窗口中提示信息“輸入要求路徑的結點值:”輸入“g”并回車，會得到結果為：→a→b→d→e→g如果輸入“i”并回車，會得到結果為：沒有要求的結點！　　4、求二叉樹的深度。在程序運行窗口的主控菜單中選擇“

4、4”并回車，在會得到結果為：該二叉樹的深度為：5　　5、求二叉樹的葉子結點個數。在程序運行窗口的主控菜單中選擇“5”并回車，在會得到結果為：該二叉樹的葉子結點數為：3　　6、將二叉樹左右子樹交換。在程序運行窗口的主控菜單中選擇“6”并回車.得到結果為：該二叉樹的左右節(jié)點已交換成功，其中序遍歷序列是：afdgebc　　7、退出程序。在程序運行窗口的主控菜單中選擇“0”并回車。退出程序?！　《?、設計　　1、設計思想　　在二叉樹上無論采用哪種遍歷方法，都能夠訪問遍樹中的所有結點。由于訪問結點的順序不同，前序遍歷和中序遍歷都很難達到設計的要求

5、；但采用后序遍歷二叉樹是可行的，因為后序遍歷是最后訪問根結點，按這個順序將訪問過的結點存儲到一個順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹T，當后序遍歷訪問到結點*p時，此時棧中存放的所有結點均為給定結點*p的祖先，而由這些祖先便構成了一條從根結點到結點*p之間的路徑。而求二叉樹的深度和葉子結點數可以直接判斷結點孩子的數目來完成，將二叉樹的左右子樹交換也可以利用遞歸的方法，交換左右孩子來實現?！　?、設計表示　　為實現上述的設計思想，首先要定義二叉樹的鏈式存儲結構，我們采用二叉鏈表的方式，相應的類型說明為：　　ty

6、pedefcharDataType;　　typedefstructnode{　　DataTypedata;structnode*lchild,*rchild;　　}BinTNode,*BinTree;　　函數接口說明:　　StatusCreateBiTree//1,按照先序遍歷次序遞歸建立二叉樹　　StatusInorder//2,二叉樹非遞歸中序遍歷算法*/　　BinTreeNodePath//3,求二叉樹根結點到給定結點*p的路徑intDepth//4.求二叉樹的深度　　intLeaf//5.求二叉樹的葉子結點個數　　BinTNo

7、de*huhuan//將p指針指向的二叉樹的左右子樹進行互換　　函數調用關系如圖所示：　　三、實現注釋　　二叉樹的創(chuàng)建模塊:按照先序遍歷次序遞歸建立二叉樹,通過讀入的字符，分配存儲空間生成新結點后再逐個構建根結點、左子樹和右子樹?！　《鏄渲行虮闅v模塊：采用非遞歸中序遍歷算法，先逐步掃描二叉樹的左子樹，并壓入堆棧，如果棧不為空，左子樹為空，則彈出棧頂的一個元素并輸出。然后再掃描右子樹，然后再重復上面的步驟掃描該分支的左子樹，直至整棵二叉樹都掃描完成。此時輸出的序列便是該二叉樹的中序遍歷序列。語句注釋見代碼?！　《鏄渲付ńY點路徑模塊：

8、該模塊由NodePath、FindBT、Findx三個函數體構成，main函數通過先調用Findx函數來查找結點，Findx又通過逐步調用FindBT函數遍歷查找結點的路徑，最后main函數再通過調用NodePath函數