二叉樹的遍歷與求結(jié)點(diǎn)路徑

課程設(shè)計(jì)項(xiàng)目研究報(bào)告目錄TOC\o"1-5"\h\z摘要11、弓I言21.1課題設(shè)計(jì)背景?21.2課題設(shè)計(jì)的目的和意義21.3課題的內(nèi)容22、課程設(shè)計(jì)計(jì)劃表32.1人員分配表32.2課程設(shè)計(jì)完成進(jìn)度表?33、總體設(shè)計(jì)43.1課程設(shè)計(jì)的方案設(shè)計(jì)論證?43.2主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)43.3模塊的劃分及功能描述?44、程序設(shè)計(jì)54.1程序流程圖54.2重要函數(shù)?64.3程序詳細(xì)分析75、源程序166、程序運(yùn)行及結(jié)果216.1程序運(yùn)行環(huán)境216.2運(yùn)行結(jié)果217、課程設(shè)計(jì)心得體會(huì)248、參考文獻(xiàn)24摘要《數(shù)據(jù)結(jié)構(gòu)》是一種基于C程序建立的一種專業(yè)的算法技術(shù)，是一門基礎(chǔ)的結(jié)構(gòu)知識(shí)，是為了解決抽象問題設(shè)計(jì)的一種數(shù)學(xué)模型的算法，然后進(jìn)行運(yùn)行調(diào)試，以達(dá)到目的。這是一門基礎(chǔ)課，在日常生活、學(xué)習(xí)中，運(yùn)用的范圍非常廣泛，這要求我們能夠掌握并應(yīng)用。本次課程設(shè)計(jì)目的在于檢驗(yàn)學(xué)生在《數(shù)據(jù)結(jié)構(gòu)》課程一學(xué)期中的學(xué)習(xí)成果，從而加深學(xué)生對(duì)所學(xué)知識(shí)的進(jìn)一步理解與鞏固。本次課程設(shè)計(jì)過程中我們主要根據(jù)課本中的實(shí)現(xiàn)思想及算法編寫程序，體現(xiàn)以課本知識(shí)的應(yīng)用為主，在學(xué)習(xí)了線性表、棧、隊(duì)列、二叉樹、樹和圖等結(jié)構(gòu)的基礎(chǔ)上，以能夠更加熟練的應(yīng)用所學(xué)知識(shí)，并能更為深刻理解數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵，熟悉它們各自的應(yīng)用場(chǎng)合及方法。有些在平時(shí)做實(shí)驗(yàn)報(bào)告中沒有掌握的內(nèi)容在這次課程設(shè)計(jì)中都是先通過看課本學(xué)懂了，然后再在課程設(shè)計(jì)中加深印象，實(shí)現(xiàn)算法的應(yīng)用和擴(kuò)展。這次的課程設(shè)計(jì)的設(shè)計(jì)內(nèi)容主要是通過實(shí)際的例子和程序來實(shí)現(xiàn)課本中所學(xué)習(xí)的算法的應(yīng)用。我們主要做了建立二叉樹以及對(duì)二叉樹的遍歷與求結(jié)點(diǎn)路徑這個(gè)課題。本文利用C語言編寫程序，分別實(shí)現(xiàn)了先序建立二叉樹的存儲(chǔ)結(jié)構(gòu)以及對(duì)二叉樹的先序遍歷、中序遍歷、后序遍歷以及對(duì)指定結(jié)點(diǎn)路徑的輸出。樹結(jié)構(gòu)的應(yīng)用主要模塊：建立二叉樹、對(duì)二叉樹的不同方法進(jìn)行遍歷、求指定結(jié)點(diǎn)路徑等，以及對(duì)指針數(shù)組的應(yīng)用為基礎(chǔ)對(duì)樹結(jié)構(gòu)的操作和應(yīng)用。幾個(gè)功能模塊已經(jīng)通過全面的測(cè)試，能夠很好的運(yùn)行，達(dá)到了預(yù)期的效果。關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷結(jié)點(diǎn)路徑引言1.1課題設(shè)計(jì)背景《數(shù)據(jù)結(jié)構(gòu)》作為一門獨(dú)立的課程最早是美國的一些大學(xué)開設(shè)的，1968年美國唐?歐?克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，目前在我國，《數(shù)據(jù)結(jié)構(gòu)》也已經(jīng)不僅僅是計(jì)算機(jī)專業(yè)的教學(xué)計(jì)劃中的核心課程之一，而且是其它非計(jì)算機(jī)專業(yè)的主要選修課程之一。《數(shù)據(jù)結(jié)構(gòu)》在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便。值得注意的是，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型的觀點(diǎn)來論數(shù)據(jù)結(jié)構(gòu)，已成為一種新的趨勢(shì)，越來越被人們所重視。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)。葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以是一個(gè)也可以是多個(gè)。課題設(shè)計(jì)的目的和意義樹形結(jié)構(gòu)是一類很重要的非線性數(shù)據(jù)結(jié)構(gòu)，樹中結(jié)點(diǎn)之間具有明確的層次關(guān)系，并且結(jié)點(diǎn)之間有分支，它非常類似于實(shí)際的樹。樹形結(jié)構(gòu)在客觀世界中大量存在，如行政組織機(jī)構(gòu)和人類社會(huì)的家譜關(guān)系等都可用樹形結(jié)構(gòu)形象地表示。在計(jì)算機(jī)應(yīng)用領(lǐng)域，樹結(jié)構(gòu)也被廣泛地應(yīng)用。例如在編譯程序中，用樹結(jié)構(gòu)來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，用樹結(jié)構(gòu)來表示組織信息；在計(jì)算機(jī)圖形學(xué)中，用數(shù)結(jié)構(gòu)來表示圖像關(guān)系等。課題設(shè)計(jì)的內(nèi)容利用一個(gè)簡單的菜單，通過菜單項(xiàng)進(jìn)行選擇，實(shí)現(xiàn)和完成如下功能：建立二叉樹存儲(chǔ)結(jié)構(gòu)、求二叉樹的前序遍歷、求二叉樹的中序遍歷、求二叉樹的后序遍歷、求指定結(jié)點(diǎn)的路徑。

課程設(shè)計(jì)計(jì)劃表2.1人員分配表指導(dǎo)老師：分組成員安排成員座號(hào)項(xiàng)目內(nèi)容序號(hào)20號(hào)1、先序遍歷程序模塊以及分析2、界面設(shè)計(jì)程序模塊3、Word相關(guān)排版0115號(hào)1、求結(jié)點(diǎn)路徑程序模塊以及分析2、查找函數(shù)3、結(jié)構(gòu)功能模塊描述0221號(hào)1、創(chuàng)建二叉樹存儲(chǔ)結(jié)構(gòu)2、中序遍歷程序模塊以及分析3、調(diào)試程序0313號(hào)1、后序遍歷模塊以及分析2、畫程序流程圖3、心得體會(huì)04課程設(shè)計(jì)完成進(jìn)度表日期完成的工作2011.01.15整體規(guī)劃，合理分配任務(wù)項(xiàng)目2011.01.16設(shè)計(jì)并劃分模塊，并設(shè)計(jì)流程圖2011.01.17子模塊程序設(shè)計(jì)，并調(diào)試2011.01.18系統(tǒng)整合程序模塊，并調(diào)試2011.01.19綜合分析源程序，并調(diào)試成功2011.01.20完成課程設(shè)計(jì)，并撰寫課程設(shè)計(jì)報(bào)告總體設(shè)計(jì)3.1課程設(shè)計(jì)的方案設(shè)計(jì)論證本設(shè)計(jì)中，在二叉樹的上無論采用哪種遍歷方法，都能夠訪問完二叉樹中的所有結(jié)點(diǎn)。但是考慮到時(shí)間復(fù)雜度以及空間復(fù)雜度，由于非遞歸遍歷二叉樹的時(shí)間復(fù)雜度和空間復(fù)雜度都復(fù)雜于遞歸遍歷二叉樹，因此我們采用遞歸遍歷二叉樹，其時(shí)間復(fù)雜度最小為O（），無需采用復(fù)雜的入棧出棧等。而對(duì)于求結(jié)點(diǎn)的路（n），徑，考慮到棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)比較繁瑣，從而定義一指針數(shù)組來一一存儲(chǔ)該二叉樹先序遍歷過的結(jié)點(diǎn)，并對(duì)該結(jié)點(diǎn)進(jìn)行判斷是否為指定的目標(biāo)結(jié)點(diǎn)，并進(jìn)行輸出等操作，此方法操作簡單，容易理解。主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本設(shè)計(jì)中，對(duì)二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其結(jié)構(gòu)定義如下：typedefstructnode{datatypedata;structnode*lchild,*rchild;}bintnode;每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，即值域data,左指針域*lchild和右指針域*rchild。模塊的劃分及功能描述本程序分為7大模塊：全局變量定義、創(chuàng)建結(jié)構(gòu)體、創(chuàng)建二叉鏈表存儲(chǔ)表示對(duì)二叉樹三種不同的遍歷、查找目標(biāo)結(jié)點(diǎn)、求結(jié)點(diǎn)路徑、主函數(shù)。（1）全局變量定義（2）創(chuàng)建結(jié)構(gòu)體（3）創(chuàng)建二叉鏈表存儲(chǔ)表示：定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),輸入數(shù)據(jù)生成二叉樹。（4）二叉樹三種不同的遍歷：先序遍歷：采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)先序遍歷，先訪問根結(jié)點(diǎn)，再依次訪問左右子樹。中序遍歷：采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)中序遍歷，先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。C.后序遍歷：采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)后序遍歷，先訪問左右子樹，再訪問根結(jié)點(diǎn)。（5）查找目標(biāo)結(jié)點(diǎn)：采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，利用后序遍歷二叉樹方法，對(duì)各個(gè)結(jié)點(diǎn)進(jìn)行判斷改結(jié)點(diǎn)是否在二叉樹中。（6）求結(jié)點(diǎn)路徑：采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，利用先序遍歷二叉樹方法以及指針數(shù)組的存儲(chǔ)結(jié)構(gòu)方法，對(duì)結(jié)點(diǎn)路徑的遍歷查找及輸出。（7）主函數(shù)核心算法的設(shè)計(jì)；二叉樹是n個(gè)結(jié)點(diǎn)的有窮個(gè)集合，它或者是空集（n=0）,或者同時(shí)滿足以下兩個(gè)條件；（1）：有且僅有一個(gè)稱為根的結(jié)點(diǎn)；（2）：其余結(jié)點(diǎn)分為兩個(gè)互不相交的集合T],T2，并且T]，T2，都是二叉樹，分別稱為根的左子樹和右子樹。程序設(shè)計(jì)4.1程序流程圖（1）主程流程圖主函數(shù)f建立二叉樹「卩11Jf1r先序遍歷中序遍歷后序遍歷査找/判斷結(jié)點(diǎn)求結(jié)點(diǎn)路徑<丿1JX.丿

(2)可控界面流程圖:(2)可控界面流程圖:4.2重要函數(shù)主函數(shù)voidmain（）輸入函數(shù)scanf（）輸出函數(shù)printf（）二叉樹的先序建立函數(shù)createbintree（）二叉樹的先序遍歷函數(shù)preorder（）二叉樹的中序遍歷函數(shù)inorder（）二叉樹的后序遍歷函數(shù)postorder（）結(jié)點(diǎn)查找函數(shù)findx（）求結(jié)點(diǎn)路徑函數(shù)nodepath（）4.3程序詳細(xì)分析定義二叉樹用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)二叉樹。其中，Lchild和Rchild是分別指向該結(jié)點(diǎn)左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。定義二叉樹結(jié)點(diǎn)值的類型為字符型且結(jié)點(diǎn)個(gè)數(shù)不超過100個(gè)，把bintree構(gòu)造成bintnode類型。具體實(shí)現(xiàn)方法如下：typedefchardatatype;typedefstructnode{/******構(gòu)造數(shù)據(jù)結(jié)構(gòu)*********/datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;建立二叉樹創(chuàng)建二叉鏈表存儲(chǔ)的二叉樹。按二叉樹帶空指針的先序次序輸入結(jié)點(diǎn)值，結(jié)點(diǎn)類型為字符型。按先序次序輸入，其中“#”表示空結(jié)點(diǎn)。算法是按照先序遍歷思想設(shè)計(jì)的。構(gòu)造二叉鏈表表示的二叉樹T,“#”符號(hào)表示空樹。具體實(shí)現(xiàn)方法如下：voidcreatebintree(bintree*bt)/***先序創(chuàng)建二叉樹***/{charch;fflush(stdin);if((ch=getchar())=='#')*bt=NULL;/***連續(xù)讀取輸入的字符***/else{*bt=(bintree)malloc(sizeof(bintnode));(*bt)->data=ch;createbintree(&((*bt)->lchild));createbintree(&((*bt)->rchild));}遞歸先序遍歷二叉樹：函數(shù)功能是用遞歸的方法對(duì)二叉樹進(jìn)行先序遍歷，調(diào)用此函數(shù)可以獲得二叉樹的遞歸的先序遍歷的結(jié)果。算法思想：若二叉樹為空，則結(jié)束遍歷操作；否則訪問根結(jié)點(diǎn)；數(shù)據(jù)元素調(diào)用函數(shù)visit()；先序遍歷根的左子樹；先序遍歷根的右子樹。具體實(shí)現(xiàn)方法如下：voidVisit(charch)/***在遍歷時(shí)輸出遍歷的路徑(遍歷輸出函數(shù))***/{printf("%c",ch);}voidpreorder(bintreeroot)/***先序遍歷二叉樹***/{if(root!=NULL){Visit(root->data);preorder(root->lchild);preorder(root->rchild);}}遞歸中序遍歷二叉樹：函數(shù)功能是用遞歸的方法對(duì)二叉樹進(jìn)行中序遍歷，調(diào)用此函數(shù)可以獲得二叉樹的遞歸的中序遍歷的結(jié)果。算法思想：若二叉樹為空，則結(jié)束遍歷操作；否則中序遍歷根的左子樹；數(shù)據(jù)元素調(diào)用函數(shù)visit()；訪問根結(jié)點(diǎn)；中序遍歷根的右子樹。具體實(shí)現(xiàn)方法如下：voidVisit(charch)/***在遍歷時(shí)輸出遍歷的路徑(遍歷輸出函數(shù))***/{printf("%c",ch);}voidinorder(bintreeroot)/***中序遍歷二叉樹***/{if(root!=NULL){inorder(root->lchild);Visit(root->data);inorder(root->rchild);}}遞歸后序遍歷二叉樹：函數(shù)功能是用遞歸的方法對(duì)二叉樹進(jìn)行后序遍歷，調(diào)用此函數(shù)可以獲得二叉樹的遞歸的后序遍歷的結(jié)果。算法思想：若二叉樹為空，則結(jié)束遍歷操作；否則后序遍歷根的左子樹；后序遍歷根的右子樹；數(shù)據(jù)元素調(diào)用函數(shù)Visit()；訪問根結(jié)點(diǎn)。具體實(shí)現(xiàn)方法如下：voidVisit(charch)/***在遍歷時(shí)輸出遍歷的路徑(遍歷輸出函數(shù))***/{printf("%c",ch);}voidpostorder(bintreeroot)/***后序遍歷二叉樹***/{if(root!=NULL){postorder(root->lchild);postorder(root->rchild);Visit(root->data);}}6)查找函數(shù)函數(shù)功能是用遞歸方法對(duì)二叉樹進(jìn)行先序遍歷查找，調(diào)用此函數(shù)可以返回二叉樹中指定目標(biāo)結(jié)點(diǎn)。算法思想：若找到目標(biāo)結(jié)點(diǎn)，則返回該目標(biāo)結(jié)點(diǎn)；否則訪問二叉樹的根結(jié)點(diǎn)；先序遍歷根的左子樹；先序遍歷根的右子樹。具體實(shí)現(xiàn)方法如下：voidfindbt(bintreebt,datatypex)/*遞歸查找目標(biāo)結(jié)點(diǎn)x*/{if((bt!=NULL)&&!found){if(bt->data==x){p=bt;found=1;/*找到目標(biāo)結(jié)點(diǎn)，令found=1，跳出遞歸查找函數(shù)*/}else{findbt(bt->lchild,x);findbt(bt->rchild,x);}}}bintnode*findx(bintreebt,datatypex)/*調(diào)用findbt函數(shù)，以指針類型返回p*/{found=0;p=NULL;findbt(bt,x);return(p);}7）求指定結(jié)點(diǎn)路徑：該函數(shù)功能是根據(jù)已創(chuàng)建的二叉樹和輸入的目標(biāo)結(jié)點(diǎn)，調(diào)用此函數(shù)可以查找并輸出目標(biāo)結(jié)點(diǎn)的路徑。算法思想：根據(jù)先序遍歷二叉樹的遞歸定義，采用一個(gè)指針數(shù)組來保存返回的結(jié)點(diǎn)。先掃描根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)并寫入指針數(shù)組。判斷該結(jié)點(diǎn)是否與指定目標(biāo)結(jié)點(diǎn)相等，若不相等，然后掃描該結(jié)點(diǎn)的右結(jié)點(diǎn)并寫入指針數(shù)組，再掃描該右結(jié)點(diǎn)的所有左結(jié)點(diǎn)寫入指針數(shù)組。當(dāng)一個(gè)結(jié)點(diǎn)的左孩子樹均訪問完后再訪問該結(jié)點(diǎn)，并與給定的結(jié)點(diǎn)比較。若相等，則循環(huán)輸出指針數(shù)組中的所有元素，而這個(gè)順序值就是要求的路徑。若不相等，則繼續(xù)上述過程。具體實(shí)現(xiàn)方法如下：voidnodepath（bintreebt,bintnode*ch）/***在二叉樹中查找目標(biāo)結(jié)點(diǎn)，并輸出目標(biāo)結(jié)點(diǎn)的路勁***/{typedefenum{FALSE,TRUE}boolean;bintnode*stack[num];/*****定義指針數(shù)組*****/inttag[num];/*****標(biāo)志數(shù)組*****/inti,top;booleanfind;bintnode*s;find=FALSE;top=0;s=bt;do{while（s!=NULL）/***只要s不為空，把s以及s的左孩子（遞歸）寫入stack[top]***/{top++;stack[top]=s;/**用來存儲(chǔ)標(biāo)記查找目標(biāo)數(shù)據(jù)時(shí)走過的路徑（結(jié)點(diǎn)）**/tag[top]=0;/***第top個(gè)的結(jié)點(diǎn)為左孩子，記tag[top]為0***/s=s->lchild;}if(top>0)/***s不為空，即有寫入數(shù)組，數(shù)組不為空***/{s=stack[top];/*s為最后的左孩子(其孩子結(jié)點(diǎn)沒有左孩子了)*/if(tag[top]==1){if(s==ch){for(i=1;i<=top;i++)printf("->%c",stack[i]->data);/***找到與輸入相符的目標(biāo)數(shù)據(jù)，即輸出路徑***/find=TRUE;}elsetop--;/*沒有找到相符的數(shù)據(jù)，即刪除該結(jié)點(diǎn)，把結(jié)點(diǎn)往上移*/s=stack[top];}if(top>0&&!find){if(tag[top]!=1){s=s->rchild;/****最后一個(gè)的左結(jié)點(diǎn)沒有左孩子了，開始往右查找目標(biāo)結(jié)點(diǎn)，第top個(gè)結(jié)點(diǎn)為右孩子記為1***/tag[top]=1;}elses=NULL;}

}while(!find&&top!=0);/***當(dāng)查找該二叉樹時(shí)有找到目標(biāo)結(jié)點(diǎn)或都查找完該二叉樹沒有找到目標(biāo)結(jié)點(diǎn)，則退出循環(huán)***/}(8)主函數(shù)：該函數(shù)為程序的主函數(shù)功能是循環(huán)輸出菜單，功能界面；從界面獲取功能菜單中對(duì)應(yīng)的字符，通過switch()語句實(shí)現(xiàn)對(duì)函數(shù)的調(diào)用，進(jìn)而實(shí)現(xiàn)功能。具體代碼如下：/*****主函數(shù)*****/voidmain()/*****主函數(shù)*****/{bintree*bt;intxz=1;charch1;printf("\t**********************************************************\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\t*\t\tWELCOMCOMEHERE\t\t*\n");printf("\t*KindlyReminder:Firstyoushouldcreateabinarytree!*\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\twhile(xz){/*****輸出菜單,功能*****/printf("\nAbinarytreetraverseandbegnodepath!\n");printf("================================================\n");printf("1.Createabinarytreestorageprintf("structure!\n");printf("traverse!\n");printf("2.Forbinarytree'spreorderto3.Forbinarytreeinordertotraverse!\n");printf("4.Forbinarytreepostordertotraverse!\n");printf("5.Foraspecifiednodepath!\n");printf("0.ExitSystem!\n");printf("================================================\n");printf("Pleasechooseastraw:(0-5)\n");scanf("%d",&xz);/*****通過switch語句選擇相應(yīng)的方法實(shí)現(xiàn)相應(yīng)的功能*****/switch(xz){case1:printf("Inputsomevalueofbinarytreenode:\n");createbintree(&bt);printf("Abinarytreechainstructureestablishcomplete!\n\n");break;case2:printf("Abinarytreepreordertotraversis:\n");preorder(bt);printf("\n");break;case3:printf("Abinarytreeinordertotraversis:\n");inorder(bt);printf("\n");break;case4:printf("Abinarytreepostordertotraversis:\n");postorder(bt);printf("\n");break;case5:printf("pleaseinputanode:\n");ch1=getchar();ch1=getchar();findx(bt,ch1);if(p!=NULL){printf("thenode'spathis:\n");nodepath(bt,p);printf("\n");}else/*當(dāng)輸入的目標(biāo)結(jié)點(diǎn)不存在，輸出錯(cuò)誤提示*/printf("!ERROR!\nthenodeisunfound!\n");break;/***當(dāng)輸入的字符不與菜單的功能對(duì)應(yīng)，提示錯(cuò)誤，返回菜單界面**/default:printf("thecommandisunfound!tryagain!\n");}}}源程序#include<stdio.h>#include<stdlib.h>#definenum100typedefchardatatype;typedefstructnode{/******構(gòu)造結(jié)構(gòu)體*********/datatypedata;structnode*lchild,*rchild;}bintnode;typedefbintnode*bintree;intfound;bintnode*p;voidcreatebintree(bintree*bt)/*****先序創(chuàng)建二叉樹******/{charch;fflush(stdin);if((ch=getchar())=='#')*bt=NULL;/*****連續(xù)讀取輸入的字符*****/else{*bt=(bintree)malloc(sizeof(bintnode));(*bt)->data=ch;createbintree(&((*bt)->lchild));createbintree(&((*bt)->rchild));}}voidVisit(charch)/***在遍歷時(shí)輸出遍歷的路徑(遍歷輸出函數(shù))***/{printf("%c",ch);}voidpreorder(bintreeroot)/***先序遍歷二叉樹***/{if(root!=NULL){Visit(root->data);preorder(root->lchild);preorder(root->rchild);}}

/***中序遍歷二叉樹***//***后序遍歷二叉樹***/voidinorder(bintreeroot)/***中序遍歷二叉樹***//***后序遍歷二叉樹***/{if(root!=NULL){inorder(root->lchild);Visit(root->data);inorder(root->rchild);}}voidpostorder(bintreeroot){if(root!=NULL){postorder(root->lchild);postorder(root->rchild);Visit(root->data);}}voidfindbt(bintreebt,datatypex)/***遞歸查找目標(biāo)結(jié)點(diǎn)x***/{if((bt!=NULL)&&!found){if(bt->data==x){p=bt;found=1;/***找到目標(biāo)結(jié)點(diǎn)，令found=l,跳出遞歸查找函數(shù)***/}else{findbt(bt->lchild,x);findbt(bt->rchild,x);}}}bintnode*findx(bintreebt,datatypex)/*****調(diào)用findbt函數(shù)，以扌旨針類型返回p*****/{found=0;p=NULL;findbt(bt,x);return(p);

/*****在二叉樹中查找目標(biāo)結(jié)點(diǎn)，/*****定義指針數(shù)組*****//*****標(biāo)志數(shù)組*****/void/*****在二叉樹中查找目標(biāo)結(jié)點(diǎn)，/*****定義指針數(shù)組*****//*****標(biāo)志數(shù)組*****/并輸出目標(biāo)節(jié)結(jié)點(diǎn)的路徑*****/{typedefenum{FALSE,TRUE}boolean;bintnode*stack[num];inttag[num];inti,top;booleanfind;bintnode*s;find=FALSE;top=0;s=bt;do{while（s!二NULL）/*只要s不為空，把s以及s的左孩子（遞歸）寫入stack[top]*/{top++;stack[top]=s;/***用來存儲(chǔ)標(biāo)記查找目標(biāo)數(shù)據(jù)時(shí)走過的路徑（結(jié)點(diǎn)）***/tag[top]=0;/***第top個(gè)的結(jié)點(diǎn)為左孩子，記tag[top]為***/s=s->lchild;}if(top>0){s=stack[top];/***s不為空，即有寫入數(shù)組，數(shù)組不為空***//***s為最后的左孩子（其孩子結(jié)點(diǎn)沒有左孩子了）***/if(tag[top]==1){if(s==ch)for(i=1;i<=top;i++)printf("->%c",stack[i]->data);/******找到與輸入相符的目標(biāo)數(shù)據(jù)，即輸出路徑******/find=TRUE;}elsetop--;/**沒有找到相符的數(shù)據(jù)，即刪除該結(jié)點(diǎn)，把結(jié)點(diǎn)往上移**/s=stack[top];}if（top>0&&!find）{if（tag[top]!=1）{s=s->rchild;/***最后一個(gè)的左結(jié)點(diǎn)沒有左孩子了，開始往右

查找目標(biāo)結(jié)點(diǎn)，第top個(gè)結(jié)點(diǎn)為右孩子記為***/tag[top]=1;}elses=NULL;}}}while(!find&&top!=0);/***當(dāng)查找該二叉樹書時(shí)有找到目標(biāo)結(jié)點(diǎn)或都查找完該二叉樹沒有找到目標(biāo)結(jié)點(diǎn)，則退出循環(huán)***/}/*****主函數(shù)*****/voidmain()/*****主函數(shù)*****/{bintree*bt;intxz=1;charch1;printf("\t**********************************************************\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\t*\t\tWELCOMCOMEHEARE\t\t*\n");printf("\t*KindlyReminder:Firstyoushouldcreateabinarytree!*\n");printf("\t*\t\t\t\t\t\t\t*\n");printf("\t**********************************************************\n");while(xz){while(xz){/*****輸出菜單*****/printf("\nAbinarytreetraverseandbegnodepath!\n");printf("================================================\n");printf("1.Createabinarytreestoragestructure!\n");printf("2.Forbinarytree'spreordertotraverse!\n");printf("3.Forbinarytreeinordertotraverse!\n");printf("4.Forbinarytreepostordertotraverse!\n");printf("5.Foraspecifiednodepath!\n");printf("0.ExitSystem!\n");printf("================================================\n");printf("Pleasechooseastraw:(0-5)\n");scanf("%d",&xz);switch(xz){/***通過switch語句選擇相應(yīng)的方法實(shí)現(xiàn)相應(yīng)的功能***/case1:printf("Inputsomevalueofbinarytreenode:\n");createbintree(&bt);printf("Abinarytreechainstructureestablishcomplete!\n\n");break;case2:printf("Abinarytreepreordertotraversis:\n");preorder(bt);printf("\n");break;case3:printf("Abinarytreeinordertotraversis:\n");inorder(bt);printf("\n");break;case4:printf("Abinarytreepostordertotraversis:\n");postorder(bt);printf("\n");break;case5:printf("pleaseinputanode:\n");ch1=getchar();ch1=getchar();findx(bt,ch1);if(p!=NULL){printf("thenode'spathis:\n");nodepath(bt,p);printf("\n");}elseprintf("!ERROR!\nthenodeisunfound!\n");break;default:printf("thecommandisunfound!tryagain!\n");/*****當(dāng)輸入的字符不與菜單的功能對(duì)應(yīng)，提示錯(cuò)誤，返回菜單界面*****/}}}

程序運(yùn)行及結(jié)果6.1程序運(yùn)行環(huán)境個(gè)人PC機(jī)；windowsxp系統(tǒng)；win-tc編程軟件。6.2運(yùn)行結(jié)果(1)輸入元素?cái)?shù)據(jù)：ABC##DE#G##F###運(yùn)行結(jié)果為：Abinarytreechainstructureestablishcomplete!Abinarytreechainstructureestablishcomplete?Abinarytreetraverseandbegnodepath?Createabinarytreestoragestructure?Forbin日廠vtree!spreordertotraverse?Forbin日廠vtreeino廠de廠totraverse?Forbinarytreepostordertotraverse?Foraspecifiednodepath?0.ExitSystem