數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)第1頁/共17頁數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)第2頁/共17頁實驗四線索二叉樹實驗——實驗?zāi)康膶嶒災(zāi)康暮腿蝿?wù)１、目的（1）掌握線索二叉樹的有關(guān)知識。（2）掌握求解線索二叉樹中結(jié)點前趨和后繼的算法以及以相應(yīng)次序遍歷線索二叉樹的算法。（3）掌握二叉樹的線索化算法的設(shè)計。第3頁/共17頁實驗四線索二叉樹實驗—實驗任務(wù)2、實驗任務(wù)說明：線索二叉樹是為了快速求解二叉樹中結(jié)點在指定次序下的前驅(qū)和后繼，而將二叉鏈表中空的左右孩子指針分別改為指向其前驅(qū)和后繼結(jié)點而得到的結(jié)構(gòu)，反映了運算對數(shù)據(jù)結(jié)構(gòu)的設(shè)計的影響。因此，首先要了解線索二叉樹的結(jié)構(gòu)特點，其中原本為空的指針被修改為前驅(qū)和后繼指針，使得對左右子樹和線索的判斷發(fā)生了變化。利用線索可以實現(xiàn)某些次序下的前驅(qū)和后繼。本實驗期望能理解線索二叉樹的結(jié)構(gòu)特點，實現(xiàn)各前驅(qū)和后接算法的求解，并掌握將二叉樹轉(zhuǎn)換為線索二叉樹的算法，即線索化算法。說明：為使實驗程序簡潔直觀，下面的部分實驗程序中的一些功能實現(xiàn)仍以調(diào)用庫函數(shù)程序"btrechar.h"中的函數(shù)的形式給出，并假設(shè)該庫函數(shù)中定義了線索二叉樹的相關(guān)功能，如顯示線索二叉樹等。

第4頁/共17頁實驗四線索二叉樹實驗—實驗任務(wù)續(xù)1編寫算法實現(xiàn)下列問題的求解。<1>按先序次序遍歷先序線索二叉樹。 實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：full41.cbt第二組數(shù)據(jù)：letter.cbt<2>按中序次序遍歷中序線索二叉樹。 實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：full41.cbt第二組數(shù)據(jù)：letter.cbt第5頁/共17頁實驗四線索二叉樹實驗—實驗任務(wù)續(xù)2編寫算法實現(xiàn)下列問題的求解。<3>將值為x的結(jié)點作為先序線索二叉樹T的左子樹的（先序）最后一個結(jié)點的右孩子插入進去。 實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：full41.cbt第二組數(shù)據(jù)：letter.cbt<4>按中序次序線索化二叉樹。 實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：full41.cbt第二組數(shù)據(jù)：letter.cbt<5>按后序次序線索化二叉樹。 實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：full41.cbt第二組數(shù)據(jù)：letter.cbt第6頁/共17頁實驗四線索二叉樹實驗—實驗數(shù)據(jù)另外，為便于初學(xué)者的實驗，以及提高實驗的效率，提供了多個這種形式的結(jié)構(gòu)文件，文件名就是所給出的標注，實驗時可以按照實驗例程中的調(diào)用形式調(diào)用就可以構(gòu)造出所需要的結(jié)構(gòu)了。讀者也可以自己編寫函數(shù)來讀取文件中所存儲的結(jié)構(gòu)信息構(gòu)造出二叉樹（構(gòu)造所用的基本方法參見后面的討論）。第7頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)full41.cbt第8頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)full42.cbt第9頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)cbitre.cbt第10頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)tbt1.cbt第11頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)bitre.cbt第12頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)cbtr1.cbt第13頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)letter.cbt第14頁/共17頁實驗四線索二叉樹實驗

——實驗數(shù)據(jù)full5.cbt第15頁/共17頁實驗四線索二叉樹