資源描述：
《二叉樹的建立和遍歷實(shí)驗(yàn)報(bào)告.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、【二叉樹的建立和遍歷實(shí)驗(yàn)報(bào)告】二叉樹的遍歷實(shí)驗(yàn)心得 [題目]建立二叉樹并求指定結(jié)點(diǎn)路徑、深度、葉子個(gè)數(shù)和左右子樹交換?！ 問題描述] 要求能夠按先序遍歷次序輸入二叉樹中結(jié)點(diǎn)的值來(lái)構(gòu)造二叉樹T；然后用遞歸和非遞歸算法實(shí)現(xiàn)二叉樹T的中序遍歷；接著編寫算法實(shí)現(xiàn)求二叉樹T中指定結(jié)點(diǎn)的路徑，即從鍵盤輸入二叉樹T的任一結(jié)點(diǎn)，可以輸出從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)歷的結(jié)點(diǎn)；最后編寫二叉樹的三個(gè)應(yīng)用算法?！ 基本要求] 分別建立二叉樹存儲(chǔ)結(jié)構(gòu)的輸入輸出函數(shù)、輸出中序遍歷函數(shù)、指定節(jié)點(diǎn)路徑函數(shù)、求深度函數(shù)、求葉子個(gè)數(shù)函數(shù)和將二叉樹左右子樹交換函數(shù) 一
2、、需求與規(guī)格說明 1、定義二叉樹的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，即值域、左指針域、右指針域。要建立二叉樹T的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即建立二叉鏈表。根據(jù)輸入二叉樹結(jié)點(diǎn)的形式不同，建立的方法也不同，本系統(tǒng)采用先序序列遞歸建立二叉樹，建立如下圖所示的二叉樹。應(yīng)該在程序運(yùn)行窗口的主控菜單后，先選擇“1”并回車，緊接著在程序運(yùn)行窗口中提示信息“輸入二叉樹的先序序列結(jié)點(diǎn)值:”之后，采用以下字符序列：abc@@de@g@@f@@@作為建立二叉樹T的輸入字符序列并回車，窗口出現(xiàn)：二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! 圖1二叉樹的圖形結(jié)構(gòu) 2、二叉樹的遍歷。
3、本系統(tǒng)采用非遞歸中序遍歷算法進(jìn)行中序遍歷，這意味著遍歷右子樹時(shí)不再需要保存當(dāng)前層的根指針，可直接修改棧頂記錄中的指針即可。需要在程序運(yùn)行窗口的主控菜單中選擇“2”并回車，程序運(yùn)行窗口會(huì)出現(xiàn)以下中序遍歷序列： 該二叉樹 的中序遍歷序列是:cbegdfa 3、求二叉樹的指定結(jié)點(diǎn)路徑。在程序運(yùn)行窗口的主控菜單中選擇“3”并回車，在程序運(yùn)行窗口中提示信息“輸入要求路徑的結(jié)點(diǎn)值:”輸入“g”并回車，會(huì)得到結(jié)果為：→a→b→d→e→g如果輸入“i”并回車，會(huì)得到結(jié)果為：沒有要求的結(jié)點(diǎn)！ 4、求二叉樹的深度。在程序運(yùn)行窗口的主控菜單中選擇“
4、4”并回車，在會(huì)得到結(jié)果為：該二叉樹的深度為：5 5、求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)。在程序運(yùn)行窗口的主控菜單中選擇“5”并回車，在會(huì)得到結(jié)果為：該二叉樹的葉子結(jié)點(diǎn)數(shù)為：3 6、將二叉樹左右子樹交換。在程序運(yùn)行窗口的主控菜單中選擇“6”并回車.得到結(jié)果為：該二叉樹的左右節(jié)點(diǎn)已交換成功，其中序遍歷序列是：afdgebc 7、退出程序。在程序運(yùn)行窗口的主控菜單中選擇“0”并回車。退出程序?！ 《?、設(shè)計(jì) 1、設(shè)計(jì)思想 在二叉樹上無(wú)論采用哪種遍歷方法，都能夠訪問遍樹中的所有結(jié)點(diǎn)。由于訪問結(jié)點(diǎn)的順序不同，前序遍歷和中序遍歷都很難達(dá)到設(shè)計(jì)的要求
5、；但采用后序遍歷二叉樹是可行的，因?yàn)楹笮虮闅v是最后訪問根結(jié)點(diǎn)，按這個(gè)順序?qū)⒃L問過的結(jié)點(diǎn)存儲(chǔ)到一個(gè)順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹T，當(dāng)后序遍歷訪問到結(jié)點(diǎn)*p時(shí)，此時(shí)棧中存放的所有結(jié)點(diǎn)均為給定結(jié)點(diǎn)*p的祖先，而由這些祖先便構(gòu)成了一條從根結(jié)點(diǎn)到結(jié)點(diǎn)*p之間的路徑。而求二叉樹的深度和葉子結(jié)點(diǎn)數(shù)可以直接判斷結(jié)點(diǎn)孩子的數(shù)目來(lái)完成，將二叉樹的左右子樹交換也可以利用遞歸的方法，交換左右孩子來(lái)實(shí)現(xiàn)?！ ?、設(shè)計(jì)表示 為實(shí)現(xiàn)上述的設(shè)計(jì)思想，首先要定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，我們采用二叉鏈表的方式，相應(yīng)的類型說明為： ty
6、pedefcharDataType; typedefstructnode{ DataTypedata;structnode*lchild,*rchild; }BinTNode,*BinTree; 函數(shù)接口說明: StatusCreateBiTree//1,按照先序遍歷次序遞歸建立二叉樹 StatusInorder//2,二叉樹非遞歸中序遍歷算法*/ BinTreeNodePath//3,求二叉樹根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑intDepth//4.求二叉樹的深度 intLeaf//5.求二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù) BinTNo
7、de*huhuan//將p指針指向的二叉樹的左右子樹進(jìn)行互換 函數(shù)調(diào)用關(guān)系如圖所示： 三、實(shí)現(xiàn)注釋 二叉樹的創(chuàng)建模塊:按照先序遍歷次序遞歸建立二叉樹,通過讀入的字符，分配存儲(chǔ)空間生成新結(jié)點(diǎn)后再逐個(gè)構(gòu)建根結(jié)點(diǎn)、左子樹和右子樹。 二叉樹中序遍歷模塊：采用非遞歸中序遍歷算法，先逐步掃描二叉樹的左子樹，并壓入堆棧，如果棧不為空，左子樹為空，則彈出棧頂?shù)囊粋€(gè)元素并輸出。然后再掃描右子樹，然后再重復(fù)上面的步驟掃描該分支的左子樹，直至整棵二叉樹都掃描完成。此時(shí)輸出的序列便是該二叉樹的中序遍歷序列。語(yǔ)句注釋見代碼?！ 《鏄渲付ńY(jié)點(diǎn)路徑模塊：
8、該模塊由NodePath、FindBT、Findx三個(gè)函數(shù)體構(gòu)成，main函數(shù)通過先調(diào)用Findx函數(shù)來(lái)查找結(jié)點(diǎn)，F(xiàn)indx又通過逐步調(diào)用FindBT函數(shù)遍歷查找結(jié)點(diǎn)的路徑，最后main函數(shù)再通過調(diào)用NodePath函數(shù)
