樹上任意兩結(jié)點(diǎn)的路徑求法.doc

《樹上任意兩結(jié)點(diǎn)的路徑求法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、...《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告題目：樹上任意兩個(gè)結(jié)點(diǎn)間路徑的查找班級(jí)：姓名：學(xué)號(hào)：完成日期：.......一、問題描述例如：知識(shí)題第28個(gè)任務(wù)——樹上任意兩個(gè)結(jié)點(diǎn)間路徑的查找：對(duì)于任意的一棵樹，任給該樹中的兩個(gè)結(jié)點(diǎn)，可以在該樹中找到從其中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的一條路徑。路徑是樹中結(jié)點(diǎn)的序列，a1a2…an是樹中結(jié)點(diǎn)a1到結(jié)點(diǎn)an的一條路徑，當(dāng)且僅當(dāng)a1,a2…,an均是樹中的結(jié)點(diǎn)，且對(duì)任意的ai和ai+1(1<=i

2、在計(jì)算機(jī)表示這棵樹。3.能夠接受從字符終端輸入的任意兩個(gè)結(jié)點(diǎn)，當(dāng)這兩個(gè)結(jié)點(diǎn)均是同一棵樹中的結(jié)點(diǎn)時(shí)，可輸出它們之間的路徑；當(dāng)這兩個(gè)結(jié)點(diǎn)不是同一棵樹中的結(jié)點(diǎn)時(shí)，輸出錯(cuò)誤提示。無(wú)論什么情況下，當(dāng)輸入不正確時(shí)均提示用戶重新輸入。4.編寫函數(shù)createTree,創(chuàng)建一棵樹。5.編寫函數(shù)isNode,判斷任一結(jié)點(diǎn)是否在指定的樹中。6.編寫函數(shù)searchPath，生成樹中兩結(jié)點(diǎn)間的路徑。7.編寫函數(shù)printPath，輸出樹中兩結(jié)點(diǎn)間的路徑。二、需求分析先輸入根結(jié)點(diǎn)，然后提示自左向右依次輸入各結(jié)點(diǎn)的孩子，如果沒有孩子，則輸入#，直至整棵樹輸入完成，并給出提示。舉例：輸入的樹如下圖所示。

3、屏幕顯示應(yīng)為：（斜體為輸入容）Pleaseinputtheroot:-L-lPleaseinputthesonof“L-1”:-L-l-lPleaseinputthesonof“L-1”:-L-l-2Pleaseinputthesonof“L-1”:-L-l-3Pleaseinputthesonof“L-1”:-#Pleaseinputthesonof“L-1-1”:-#Pleaseinputthesonof”L-1-2”:-L-1-2-1Pleaseinputthesonof”L-1-2”:-L-1-2-2Pleaseinputthesonof“L-1-2”:-#Pleas

4、einputthesonof”L-1-3”:-L-1-3-1Pleaseinputthesonof”L-1-3”:-#Pleaseinputthesonof”L-1-2-1”:-#Pleaseinputthesonof”L-1-2-2”:-#Pleaseinputthesonof”L-1-3-1”:-#.......Finished!當(dāng)樹輸入完成后，給出輸入結(jié)點(diǎn)的提示，并要求輸入任意兩個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)間以逗號(hào)（“，”）分割，并以回車（“?”）作為結(jié)束。例如：PleaseinputTWOnodesofthetree(separatedbyacomma,e.g.,a,b):?L_1,

5、L_2?“L_2”isNOTinthetree!PleaseinputTWOnodesofthetreeagain:?輸入要求與格式結(jié)點(diǎn)間的路徑以結(jié)點(diǎn)序列的形式給出。在結(jié)點(diǎn)序列中，任意兩結(jié)點(diǎn)之間以一個(gè)制表符分隔。每行最多顯示5個(gè)結(jié)點(diǎn)。例如，當(dāng)給定結(jié)點(diǎn)L_1_1和L_1_2_2時(shí)，輸出結(jié)果應(yīng)為：ThepathfromL_1_1toL_1_2_2is:L_1_1L_1L_1_2L_1_2_2測(cè)試說(shuō)明對(duì)于下圖所示的樹，測(cè)試用例1：輸入兩結(jié)點(diǎn)：P,M輸出結(jié)果：“P”isNOTinthetree!測(cè)試用例2：輸入兩結(jié)點(diǎn)：N,P輸出結(jié)果：“P”isNOTinthetree!測(cè)試用例3：輸

6、入兩結(jié)點(diǎn)：N,M輸出結(jié)果：NKHCADIM三、程序設(shè)計(jì)#include#include#definenum100#defineOK1typedefintStatus;typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}BinTNode,*BinTree;intfound;BinTNode*p;.......Statuscreatetree(BinTree*bt){charch;scanf("%c",&ch);if(ch=='')(*bt

7、)=NULL;else{(*bt)=(BinTNode*)malloc(sizeof(BinTNode));(*bt)->data=ch;createtree(&(*bt)->lchild);createtree(&(*bt)->rchild);}returnOK;}voidsearchPath(BinTreebt,BinTNode*ch){typedefenum{FALSE,TRUE}boolean;BinTNode*stack[num];inttag[num];inti,top;booleanfin