數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---二叉樹的建立和遍歷的演示

1、<p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　題 目: 二叉樹的建立和遍歷的演示（基于動(dòng)態(tài)二叉鏈表）</p><p><b>　　初始條件：</b></p><p>　　理論：學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)》課程，掌握了一種計(jì)算機(jī)高級(jí)語言。</p><p>　　實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)

2、驗(yàn)中心提供計(jì)算機(jī)及軟件開發(fā)環(huán)境。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）</p><p>　　1、系統(tǒng)應(yīng)具備的功能：</p><p>　?。?）建立二叉樹的動(dòng)態(tài)二叉鏈表存儲(chǔ)結(jié)構(gòu)</p><p>　?。?）用遞歸算法和非遞歸算法實(shí)現(xiàn)二叉樹的各種遍歷</p><p

3、><b>　?。?）演示結(jié)果</b></p><p><b>　　2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；</b></p><p><b>　　3、主要算法設(shè)計(jì)；</b></p><p>　　4、編程及上機(jī)實(shí)現(xiàn)；</p><p>　　5、撰寫課程設(shè)計(jì)報(bào)告，包括：</p><

4、p><b>　?。?）設(shè)計(jì)題目；</b></p><p>　?。?）摘要和關(guān)鍵字（中文和英文）；</p><p>　　（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、有關(guān)技術(shù)的討論、設(shè)計(jì)體會(huì)等；</p><p><b>　?。?）結(jié)束語；</b></p><p><b>　　

5、（5）參考文獻(xiàn)。</b></p><p>　　時(shí)間安排： 2011年1月10日－14日 （第19周）</p><p>　　1月10日 查閱資料</p><p>　　1月11日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)</p><p>　　1月12日-13日 編程并上機(jī)調(diào)試</p><p>　　1月14日

6、 撰寫報(bào)告</p><p>　　1月15日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書。</p><p>　　指導(dǎo)教師簽名： 2011年1月10日</p><p>　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p>　　二叉樹的建立和遍歷的演示<

7、;/p><p>　?。ɑ趧?dòng)態(tài)二叉鏈表）</p><p>　　摘 要：二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常節(jié)點(diǎn)的子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。遍歷是對(duì)樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將

8、二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。常用的遍歷方法有先序遍歷、中序遍歷和后續(xù)遍歷，這三種遍歷方法都可以通過遞歸和非遞歸算法實(shí)現(xiàn)。對(duì)于二叉樹的三種遍歷過程，如果用非遞歸算法來實(shí)現(xiàn)，則要復(fù)雜一些。</p><p><b>　　Abstract:</b></p><p>　　Binary tree is an orderly tree that each node

9、hava no more than two sub-trees. Subtree node is usually referred to as the "left sub-tree" and "the right sub-tree". Traversal of a tree is the most basic computing, the so-called binary tree traver

10、sal, that is, according to certain rules and order of every tree of all nodes and each node have been visited once. Binary tree structure as a result of non-linear, therefore, the tree is to traverse all tree nodes can c

11、onverted into a linear sequence to</p><p>　　關(guān)鍵詞：二叉樹 遍歷 遞歸</p><p>　　Key words:</p><p>　　Binary tree traversal recursive</p><p><b>　　1引 言</b>

12、</p><p>　　在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆。</p><p>　　遍歷也稱周游，是指按一定的規(guī)律，訪問二叉樹樹的結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次，且只被訪問一次。訪問的含義可以是查詢某元素、修改某元素、輸出某元素的值，以及對(duì)元素作

13、某種運(yùn)算等等。這實(shí)際上是二叉樹的結(jié)點(diǎn)排成一個(gè)線性序列的過程。由于二叉樹是非線性結(jié)構(gòu)，因此，為得到這樣的一個(gè)線性序列，必須規(guī)定遍歷的次序。</p><p>　　常用的遍歷方法有先序遍歷、中序遍歷和后序遍歷這三種方法 ，并都可用遞歸和非遞歸算法來實(shí)現(xiàn)。在非遞歸的先序、中序和后序遍歷算法中，需要定義一個(gè)棧，來暫存遍歷過程中所遇到的結(jié)點(diǎn)的地址，以便實(shí)現(xiàn)回溯。棧（stack）在計(jì)算機(jī)科學(xué)中是限定僅在表尾進(jìn)行插入或刪除操作的

14、線形表。它是是一種數(shù)據(jù)結(jié)構(gòu)，它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來）。所以它非常適合存儲(chǔ)二叉樹的節(jié)點(diǎn)信息。</p><p>　　1.1課程設(shè)計(jì)的任務(wù)</p><p>　　建立二叉樹的動(dòng)態(tài)二叉鏈表存儲(chǔ)結(jié)構(gòu)，用遞歸算法和非遞歸算法實(shí)現(xiàn)二叉樹的各種遍歷，并演示結(jié)果</p><p&g

15、t;　　1.2課程設(shè)計(jì)的性質(zhì)</p><p>　　由要求分析知，本設(shè)計(jì)主要要求解決二叉樹的建立以及三種遍歷的遞歸和非遞歸算法的實(shí)現(xiàn)。所以設(shè)計(jì)一個(gè)良好的先序、中序和后序的遞歸、非遞歸遍歷算法非常重要。</p><p>　　1.3課程設(shè)計(jì)的目的和意義</p><p>　　在此過程中我們將會(huì)了解編程的一些方法和技巧，認(rèn)識(shí)到實(shí)現(xiàn)一個(gè)問有提出問題、分析問題、設(shè)計(jì)問題、實(shí)現(xiàn)等環(huán)

16、節(jié)。此實(shí)踐過程會(huì)是大家熟練掌握基本的數(shù)據(jù)結(jié)構(gòu)和常用的算法，并最終設(shè)計(jì)一個(gè)能夠解決實(shí)際問題并具有一定規(guī)模的</p><p><b>　　大學(xué)數(shù)據(jù)課程設(shè)計(jì)。</b></p><p>　　這次做程序設(shè)計(jì)目的是為更好地掌握C語言編寫數(shù)據(jù)結(jié)構(gòu)程序的方法和技巧，了解C語言的強(qiáng)大的功能，更好地學(xué)習(xí)C語言，并且在這個(gè)過程中更好地鍛煉自己的動(dòng)手能力和實(shí)踐能力。</p>&

17、lt;p>　　通過對(duì)此次數(shù)據(jù)結(jié)構(gòu)大型作業(yè)內(nèi)容的分析，鍛煉學(xué)生分析與編寫大型軟件代碼的能力。通過與同組同學(xué)的合作，鍛煉協(xié)作的能力。</p><p><b>　　2需求分析</b></p><p>　　二叉樹一種數(shù)據(jù)結(jié)構(gòu)，用于保存和處理樹狀的數(shù)據(jù)，比如家譜。他的應(yīng)用極為廣泛，因?yàn)楦鶕?jù)數(shù)據(jù)結(jié)構(gòu)的理論，任何復(fù)雜的樹夠可以轉(zhuǎn)換為二叉中并進(jìn)行處理，二叉樹在排序、查找、大規(guī)模

18、數(shù)據(jù)索引方面有很多很多應(yīng)用。而且二叉樹排序是簡(jiǎn)單算法排序中速度最快的。</p><p>　　在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的節(jié)點(diǎn)，或者對(duì)樹中全部節(jié)點(diǎn)逐一進(jìn)行某種處理。這就提出了遍歷二叉樹。根據(jù)遍歷的方向的選擇，就有了先序、中序和后序遍歷二叉樹。因此掌握二叉樹的三種遍歷二叉樹算法非常重要，而且高效的后序遍歷算法能夠節(jié)省很多成本。</p><p><b>　　3

19、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p><p><b>　　二叉樹的結(jié)點(diǎn)結(jié)構(gòu)體</b></p><p>　　typedef int datatype; /* datatype可以為任何類型，這里假設(shè)為int*/</p><p>　　typedef struct node </p><p>　　{

20、 /*結(jié)構(gòu)體*/</p><p>　　char data; /*數(shù)據(jù)域*/</p><p>　　struct node *lchild,*rchild; /*左右孩子指針*/</p><p><b>　　}bitr

21、ee;</b></p><p><b>　　棧的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p><p>　　typedef struct StackElemType//棧的結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　BiNode ptr;</p><p>&

22、lt;b>　　int flag;</b></p><p>　　}StackElemType;</p><p><b>　　4算法設(shè)計(jì)</b></p><p><b>　　4.1算法分析</b></p><p>　　4.1.1二叉樹創(chuàng)建</p><p>　　用

23、鏈表實(shí)現(xiàn)創(chuàng)建一個(gè)樹結(jié)點(diǎn)的結(jié)構(gòu)體，從鍵盤輸入數(shù)據(jù)，存入數(shù)組。把下標(biāo)為2*i+1 的值存入左孩子，為2*i+2的存入右孩子。BiNode creat()，BiNode stree_creat(char *a,int k)。 </p><p>　　4.1.2先序遍歷二叉樹的遞歸算法</p><p>　　若二叉樹為空，則空操作；否則（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。vo

24、id PreOrder(BiNode root)。</p><p>　　4.1.3中序遍歷二叉樹的遞歸算法</p><p>　　若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。void InOrder(BiNode root)。</p><p>　　4.1.4后序遍歷二叉樹的遞歸算法</p><p>

25、　　若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹。（3）訪問根結(jié)點(diǎn)；void PostOrder(BiNode root)。</p><p>　　4.1.5先序非遞歸算法</p><p>　　BiNode根指針，若 BiNode!= NULL對(duì)于非遞歸算法，引入棧模擬遞歸工作棧，初始時(shí)棧為空。void F_PreOrder(BiNode root)</p&g

26、t;<p>　　4.1.6中序非遞歸算法</p><p>　　BiNode是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。void F_inOrder(BiNode root)。</p><p>　　4.1.7后序非遞歸算法</p><p>　　BiNode是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根</p

27、><p>　　需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過。void F_PostOrder(BiNode root)。</p><p><b>　　4.2流程圖</b></p><p>　　圖 1 二叉樹的創(chuàng)建</p><p>　　圖2 前序遞歸遍歷</p><p>　　圖3 中序遞歸遍歷</p

28、><p>　　圖4 后序遞歸遍歷</p><p>　　圖5、前序非遞歸遍歷</p><p>　　圖6 中序非遞歸遍歷</p><p><b>　　4.3算法代碼</b></p><p>　　4.3.1二叉樹的建立</p><p>　　BiNode stree_creat(c

29、har *a,int k) </p><p><b>　　{</b></p><p>　　BiNode root; max++;</p><p>　　if(a[k]=='\0'||k>maxsize) </p><p>　　return NULL; //判斷樹是否為空</p><

30、p><b>　　else </b></p><p><b>　　{</b></p><p>　　root=(BiNode)malloc(LEN);//動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)</p><p>　　root->data=a[k]; </p><p>　　root->lchild=stree_cr

31、eat(a,2*k+1); //遞歸調(diào)用為左孩子賦值</p><p>　　root->rchild=stree_creat(a,2*k+2); //遞歸調(diào)用為右子賦值</p><p>　　return root;//返回根節(jié)點(diǎn)指針</p><p><b>　　} </b></p><p><b>　　}

32、</b></p><p>　　4.3.2先序遞歸遍歷</p><p>　　void PreOrder(BiNode root){</p><p>　　if(root==NULL)return;//遞歸調(diào)用的約束條件</p><p><b>　　else</b></p><p><

33、b>　　{ </b></p><p>　　if(root->data=='0') ;</p><p><b>　　else</b></p><p>　　cout<<"["<<root->data<<"]";</p&g

34、t;<p>　　PreOrder(root->lchild);</p><p>　　PreOrder(root->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.3.3中序遞歸遍歷</p>

35、<p>　　void InOrder(BiNode root)</p><p><b>　　{</b></p><p>　　if(root==NULL)return;//遞歸調(diào)用的約束條件</p><p><b>　　else</b></p><p><b>　　{</

36、b></p><p>　　InOrder(root->lchild);</p><p>　　if(root->data=='0') ;</p><p>　　else cout<<"["<<root->data<<"]";</p>&l

37、t;p>　　InOrder(root->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.3.4后序遞歸遍歷</p><p>　　void PostOrder(BiNode root)</p><

38、p><b>　　{</b></p><p>　　if(root==NULL)return;//遞歸調(diào)用的約束條件</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　PostOrder(root->lchild)

39、;</p><p>　　PostOrder(root->rchild);</p><p>　　if(root->data=='0') ;</p><p>　　else cout<<"["<<root->data<<"]";</p><p

40、><b>　　}</b></p><p><b>　　}</b></p><p>　　4.3.5先序非遞歸遍歷</p><p>　　void F_PreOrder(BiNode root)</p><p><b>　　{</b></p><p>　

41、　BiNode s[maxsize];//申請(qǐng)一個(gè)BiNode數(shù)組</p><p>　　int top=0;//采用順序棧，并假定不會(huì)發(fā)生上溢</p><p><b>　　do{</b></p><p>　　while(root!=NULL)//當(dāng)結(jié)點(diǎn)不為空時(shí)</p><p><b>　　{</b>

42、</p><p>　　if(root->data=='0') ;</p><p><b>　　else</b></p><p>　　cout<<"["<<root->data<<"]";</p><p>　　s[++

43、top]=root;//依次將結(jié)點(diǎn)壓入棧</p><p>　　root=root->lchild;//根賦值為它的左孩子</p><p><b>　　}</b></p><p>　　if(top>0)//當(dāng)節(jié)點(diǎn)為空但棧頂不為零時(shí)</p><p><b>　　{</b></p>

44、<p>　　root=s[top--];棧頂下移把棧頂元素負(fù)給根結(jié)點(diǎn)</p><p>　　root=root->rchild; 根賦值為它的右子</p><p><b>　　}</b></p><p>　　}while(root!=NULL||top>0);</p><p><b>　

45、　}</b></p><p>　　4.3.6中序非遞歸遍歷</p><p>　　void F_inOrder(BiNode root)</p><p><b>　　{</b></p><p>　　BiNode s[maxsize]; //申請(qǐng)一個(gè)BiNode數(shù)組</p><p>　

46、　int top=0; //采用順序棧，并假定不會(huì)發(fā)生上溢</p><p><b>　　do{</b></p><p>　　while(root!=NULL) //當(dāng)結(jié)點(diǎn)不為空時(shí)</p><p><b>　　{</b></p><p>　　s[++top] = root; //依次將結(jié)點(diǎn)壓入棧<

47、;/p><p>　　root = root->lchild; //根賦值為它的左孩子</p><p><b>　　}</b></p><p>　　if(top>0) //當(dāng)節(jié)點(diǎn)為空但棧頂不為零時(shí)</p><p><b>　　{</b></p><p>　　root =

48、 s[top]; 把棧頂元素負(fù)給根結(jié)點(diǎn)</p><p>　　if(root->data=='0') ;</p><p>　　else cout<<"["<<root->data<<"]";//輸出根結(jié)點(diǎn)</p><p>　　root=s[top--];棧頂下移

49、把棧頂元素負(fù)給根結(jié)點(diǎn)</p><p>　　root=root->rchild; 根賦值為它的右子</p><p><b>　　}</b></p><p>　　}while(root!=NULL||top>0);</p><p><b>　　} </b></p><p&

50、gt;　　4.3.7后序非遞歸遍歷</p><p>　　void F_PostOrder(BiNode root)</p><p>　　{StackElemTyp s[maxsize];//申請(qǐng)一個(gè)StackElemType數(shù)組</p><p>　　BiNode p=root;</p><p>　　int top = 0;</p>

51、;<p><b>　　do{</b></p><p>　　while(p!=NULL) //當(dāng)結(jié)點(diǎn)不為空時(shí)</p><p><b>　　{</b></p><p>　　s[top].flag = 0;//標(biāo)記位負(fù)為零</p><p>　　s[top].ptr = p;//將樹的結(jié)點(diǎn)依次

52、壓入棧中</p><p>　　p=p->lchild;//樹沿左子樹下移</p><p><b>　　top++;</b></p><p><b>　　}</b></p><p>　　while(s[top-1].flag == 1)//當(dāng)棧的最上面元素標(biāo)記位為一時(shí)輸出</p>

53、<p>　　{ if( s[top-1].ptr->data=='0') top--;</p><p><b>　　else</b></p><p>　　cout<<"["<<s[--top].ptr->data<<"]";</p>

54、<p><b>　　}</b></p><p>　　if(top>0) //當(dāng)節(jié)點(diǎn)為空但棧頂不為零時(shí)</p><p><b>　　{</b></p><p>　　s[top-1].flag = 1; 棧的最上面元素標(biāo)記位賦值為一</p><p>　　p = s[top-1].ptr

55、; 棧的最上面元素樹結(jié)點(diǎn)賦給p</p><p>　　p = p->rchild;樹沿右子樹下移</p><p><b>　　}</b></p><p>　　}while(top>0);</p><p><b>　　}</b></p><p><b>　　

56、4.4演示結(jié)果</b></p><p>　　4.4.1二叉樹的建立</p><p>　　4.4.2先序遞歸遍歷</p><p>　　4.4.3中序遞歸遍歷</p><p>　　4.4.4后序遞歸遍歷</p><p>　　4.4.5先序非遞歸遍歷</p><p>　　4.4.6中序非遞

57、歸遍歷</p><p>　　4.4.7后序非遞歸遍歷</p><p><b>　　5有關(guān)技術(shù)的討論</b></p><p>　　5.1程序設(shè)計(jì)的優(yōu)缺點(diǎn)</p><p>　　這個(gè)程序設(shè)計(jì)的算法清晰，思想明了，能清楚的實(shí)現(xiàn)二叉樹的建立、三種遍歷的遞歸和非遞歸運(yùn)算。但是這個(gè)程序在設(shè)計(jì)過程時(shí)有些麻煩，而且三種遍歷的算法自己不是太

58、清楚，不能很清楚的描述三種遍歷。</p><p>　　5.2程序設(shè)計(jì)遇到的問題</p><p>　　在設(shè)計(jì)時(shí)主要三種遍歷不是很清楚，所以還是很模糊，剛開始不能很準(zhǔn)確的把三種遍歷的算法寫出來，所以在這個(gè)問題上還要繼續(xù)思考。在寫菜單時(shí)不是很了解，后來在同學(xué)的幫助下把程序的模塊寫出來了，自己還要努力學(xué)習(xí)寫算法。</p><p><b>　　6設(shè)計(jì)體會(huì)</b

59、></p><p>　　通過這次做數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我發(fā)現(xiàn)真正掌握一個(gè)知識(shí)點(diǎn)并不只是要從書上看，還要查一些相關(guān)資料，并且理論與現(xiàn)實(shí)結(jié)合在一起。這次做的是關(guān)于二叉樹的課程設(shè)計(jì)，剛開始以為并不是很難，但真正做的時(shí)候才發(fā)現(xiàn)這一節(jié)的知識(shí)點(diǎn)很多，也有一些比較混淆的難點(diǎn)，比如二叉樹的遍歷就有三種情況，包括前序遍歷、中序遍歷、后序遍歷。</p><p>　　當(dāng)然這次在做課程設(shè)計(jì)的時(shí)候遇到一些問題

60、，不過得到大家的幫助，問題得到解決，也成功的完成了本次的課程設(shè)計(jì)。</p><p><b>　　7結(jié)束語</b></p><p>　　在二叉樹的創(chuàng)建過程中沒有利用到構(gòu)造函數(shù)來直接構(gòu)造一個(gè)二叉樹，這樣就不用每次創(chuàng)建一個(gè)二叉樹時(shí)候還要再重新使用一個(gè)函數(shù)來生成相關(guān)的節(jié)點(diǎn)。另外在棧中，釋放內(nèi)存也沒有用析構(gòu)函數(shù)來完成此功能，還用了一個(gè)另外一個(gè)函數(shù)，實(shí)在有點(diǎn)費(fèi)事。</p&g

61、t;<p>　　在二叉樹算法的設(shè)計(jì)中，不僅讓我更加理解了二叉樹的特點(diǎn)，更加讓我鍛煉了程序設(shè)計(jì)能力，并學(xué)到了一些常用的程序設(shè)計(jì)技巧，深刻明白了程序的可讀性和健壯性的重大作用。</p><p>　　以下是本人在編寫此過程中的一些心得：</p><p>　　1、在程序設(shè)計(jì)中，經(jīng)常沒有申請(qǐng)內(nèi)存就開始使用，造成了很大的錯(cuò)誤。</p><p>　　2、往往在一塊內(nèi)

62、存使用完了之后沒有及時(shí)釋放其內(nèi)存，雖然在這里沒有出現(xiàn)什么錯(cuò)誤，但是為以后寫其他程序造成了隱患。</p><p>　　3、在程序中，使用模板類方便各種數(shù)據(jù)類型都可以操作，提供了很大方便。</p><p>　　4、在輸入時(shí)，采用用戶自定義空標(biāo)記，方便數(shù)據(jù)的快速輸入。</p><p>　　5、在非遞歸后序遍歷中只使用一個(gè)節(jié)點(diǎn)作為標(biāo)志域，避免每一個(gè)節(jié)點(diǎn)都用一個(gè)標(biāo)志域而申請(qǐng)過

63、多的內(nèi)存造成浪費(fèi)。</p><p><b>　　8參考文獻(xiàn)</b></p><p>　　【1】《數(shù)據(jù)結(jié)構(gòu)（C語言版）》 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社</p><p>　　【2】《數(shù)據(jù)結(jié)構(gòu)（第二版）》 薛超英 主編 華中科技大學(xué)出版社</p><p>　　【3】《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》嚴(yán)蔚敏 吳偉民 編著 清華

64、大學(xué)出版社</p><p>　　【4】《數(shù)據(jù)結(jié)構(gòu)》 試題研究編寫組 編著 機(jī)械工業(yè)出版社</p><p>　　本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表</p><p>　　班級(jí)：　　　　　　　姓名：　　　　　　　學(xué)號(hào)：</p><p>　　注：最終成績(jī)以五級(jí)分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、</p><

65、p>　　及格（60-69分）、60分以下為不及格</p><p><b>　　指導(dǎo)教師簽名：</b></p><p><b>　　年 月 日</b></p><p><b>　　附：源代碼</b></p><p>　　#include<iostream>

66、</p><p>　　using namespace std;</p><p>　　#include<stdlib.h> </p><p>　　#include<math.h> </p><p>　　#define maxsize 100</p><p>　　#define LEN sizeof

67、(struct btree) </p><p>　　int max=1;</p><p>　　typedef struct btree //二叉樹節(jié)點(diǎn)結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　btree *lchild,*rchild; </p><p>　　char d

68、ata; </p><p>　　}*BiNode; </p><p>　　typedef struct StackElemType//棧的結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　BiNode ptr;</p><p><b>　　int flag;</

69、b></p><p>　　}StackElemType;</p><p>　　BiNode p ;</p><p><b>　　//二叉樹的建立</b></p><p>　　BiNode stree_creat(char *a,int k) </p><p><b>　　{<

70、/b></p><p>　　BiNode root; max++;</p><p>　　if(a[k]=='\0'||k>maxsize) </p><p>　　return NULL; //判斷樹是否為空</p><p><b>　　else </b></p><p>

71、;<b>　　{</b></p><p>　　root=(BiNode)malloc(LEN);//動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)</p><p>　　root->data=a[k]; </p><p>　　root->lchild=stree_creat(a,2*k+1); //遞歸調(diào)用為左孩子賦值</p><p>　　ro

72、ot->rchild=stree_creat(a,2*k+2); //遞歸調(diào)用為右子賦值</p><p>　　return root;//返回根節(jié)點(diǎn)指針</p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void print(BiNode

73、root) //輸出所創(chuàng)建的二叉樹</p><p><b>　　{ </b></p><p>　　BiNode h[maxsize]={NULL}; </p><p>　　int top=0,base=0,j=0,k=0,n=0,m=0; </p><p>　　h[top]=root;</p><p&

74、gt;　　j=log(max+1)/log(2)-1;</p><p>　　if(pow(2,j+1)-1<max) j++;</p><p>　　cout<<"你剛輸入的是:\n"; </p><p>　　while(h[base]!=NULL) //把二叉樹的值依次存入數(shù)組</p><p><b

75、>　　{ </b></p><p>　　h[++top]=h[base]->lchild; </p><p>　　h[++top]=h[base]->rchild; </p><p><b>　　base++; </b></p><p><b>　　} </b><

76、/p><p>　　for(top=0;h[k]!=NULL;top++)//按層輸出</p><p><b>　　{ </b></p><p>　　m=pow(2,j)-top;//計(jì)算每行輸出的空格數(shù)</p><p>　　if(top!=0) m=m-top;</p><p>　　for(n=0;n

77、<m;n++) </p><p>　　cout<<" ";</p><p>　　for(base=0;base<pow(2,top)&&h[k]!=NULL;base++)//控制每層輸出的個(gè)數(shù)</p><p><b>　　{</b></p><p>　　if(

78、h[k]->data=='0') cout<<"["<<"]";//當(dāng)為空時(shí)輸出[]</p><p>　　else cout<<h[k]->data<<" ";</p><p><b>　　k++;</b></p>&l

79、t;p><b>　　}</b></p><p>　　cout<<"\n";</p><p>　　for(n=0;n<(m-1);n++) </p><p>　　cout<<" ";</p><p>　　for(base=0;base<pow

80、(2,top)&&h[k]!=NULL;base++)</p><p>　　cout<<"/"<<"| "; </p><p>　　cout<<"\n";</p><p><b>　　} </b></p><p&g

81、t;<b>　　} </b></p><p>　　//二叉樹的后序遍歷遞歸算法</p><p>　　void PostOrder(BiNode root)</p><p><b>　　{</b></p><p>　　if(root==NULL)return;//遞歸調(diào)用的約束條件</p>

82、<p><b>　　else</b></p><p><b>　　{</b></p><p>　　PostOrder(root->lchild);</p><p>　　PostOrder(root->rchild);</p><p>　　if(root->data==

83、'0') ;</p><p>　　else cout<<"["<<root->data<<"]";</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　

84、//二叉樹的中序遍歷遞歸算法</p><p>　　void InOrder(BiNode root)</p><p><b>　　{</b></p><p>　　if(root==NULL)return;//遞歸調(diào)用的約束條件</p><p><b>　　else</b></p>&l

85、t;p><b>　　{</b></p><p>　　InOrder(root->lchild);</p><p>　　if(root->data=='0') ;</p><p>　　else cout<<"["<<root->data<<&quo

86、t;]";</p><p>　　InOrder(root->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//二叉樹的前序遞歸遍歷算法</p><p>　　void PreOrder(Bi

87、Node root){</p><p>　　if(root==NULL)return;//遞歸調(diào)用的約束條件</p><p><b>　　else</b></p><p><b>　　{ </b></p><p>　　if(root->data=='0') ;</p&g

88、t;<p><b>　　else</b></p><p>　　cout<<"["<<root->data<<"]";</p><p>　　PreOrder(root->lchild);</p><p>　　PreOrder(root->r

89、child);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//二叉樹的前序遍歷非遞歸算法 </p><p>　　void F_PreOrder(BiNode root)</p><p><b>　　{<

90、/b></p><p>　　BiNode s[maxsize];//申請(qǐng)一個(gè)BiNode數(shù)組</p><p>　　int top=0;//采用順序棧，并假定不會(huì)發(fā)生上溢</p><p><b>　　do{</b></p><p>　　while(root!=NULL)//當(dāng)結(jié)點(diǎn)不為空時(shí)</p><

91、;p><b>　　{</b></p><p>　　if(root->data=='0') ;</p><p><b>　　else</b></p><p>　　cout<<"["<<root->data<<"]"

92、;</p><p>　　s[++top]=root;//依次將結(jié)點(diǎn)壓入棧</p><p>　　root=root->lchild;//根賦值為它的左孩子</p><p><b>　　}</b></p><p>　　if(top>0)//當(dāng)節(jié)點(diǎn)為空但棧頂不為零時(shí)</p><p><

93、b>　　{</b></p><p>　　root=s[top--];//棧頂下移把棧頂元素負(fù)給根結(jié)點(diǎn)</p><p>　　root=root->rchild; //根賦值為它的右子</p><p><b>　　}</b></p><p>　　}while(root!=NULL||top>0)

94、;</p><p><b>　　}</b></p><p>　　//中序非遞歸遍歷算法</p><p>　　void F_inOrder(BiNode root)</p><p><b>　　{</b></p><p>　　BiNode s[maxsize]; //申請(qǐng)一

95、個(gè)BiNode數(shù)組</p><p>　　int top=0; //采用順序棧，并假定不會(huì)發(fā)生上溢</p><p><b>　　do{</b></p><p>　　while(root!=NULL) //當(dāng)結(jié)點(diǎn)不為空時(shí)</p><p><b>　　{</b></p><p>　

96、　s[++top] = root; //依次將結(jié)點(diǎn)壓入棧</p><p>　　root = root->lchild; //根賦值為它的左孩子</p><p><b>　　}</b></p><p>　　if(top>0) //當(dāng)節(jié)點(diǎn)為空但棧頂不為零時(shí)</p><p><b>　　{</b&g

97、t;</p><p>　　root = s[top]; //把棧頂元素負(fù)給根結(jié)點(diǎn)</p><p>　　if(root->data=='0') ;</p><p>　　else cout<<"["<<root->data<<"]";//輸出根結(jié)點(diǎn)</p&g

98、t;<p>　　root=s[top--];//棧頂下移把棧頂元素負(fù)給根結(jié)點(diǎn)</p><p>　　root=root->rchild; //根賦值為它的右子</p><p><b>　　}</b></p><p>　　}while(root!=NULL||top>0);</p><p><

99、b>　　} </b></p><p>　　//后序非遞歸遍歷算法</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　BiNode ptr;</p><p><b>　　int flag;</b>&

100、lt;/p><p>　　}StackElemTyp;</p><p>　　void F_PostOrder(BiNode root)</p><p><b>　　{</b></p><p>　　StackElemTyp s[maxsize];//申請(qǐng)一個(gè)StackElemType數(shù)組</p><p>

101、;　　BiNode p=root;</p><p>　　int top = 0;</p><p><b>　　do{</b></p><p>　　while(p!=NULL) //當(dāng)結(jié)點(diǎn)不為空時(shí)</p><p><b>　　{</b></p><p>　　s[top].fla

102、g = 0;//標(biāo)記位負(fù)為零</p><p>　　s[top].ptr = p;//將樹的結(jié)點(diǎn)依次壓入棧中</p><p>　　p=p->lchild;//樹沿左子樹下移</p><p><b>　　top++;</b></p><p><b>　　}</b></p><p

103、>　　while(s[top-1].flag == 1)//當(dāng)棧的最上面元素標(biāo)記位為一時(shí)輸出</p><p>　　{ if( s[top-1].ptr->data=='0') top--;</p><p><b>　　else</b></p><p>　　cout<<"["&

104、lt;<s[--top].ptr->data<<"]";</p><p><b>　　}</b></p><p>　　if(top>0) //當(dāng)節(jié)點(diǎn)為空但棧頂不為零時(shí)</p><p><b>　　{</b></p><p>　　s[top-1].fl

105、ag = 1;// 棧的最上面元素標(biāo)記位賦值為一</p><p>　　p = s[top-1].ptr; //棧的最上面元素樹結(jié)點(diǎn)賦給p</p><p>　　p = p->rchild;//樹沿右子樹下移</p><p><b>　　}</b></p><p>　　}while(top>0);</p&g

106、t;<p><b>　　}</b></p><p>　　//輸入二叉樹信息的函數(shù)</p><p>　　BiNode creat()</p><p><b>　　{ </b></p><p>　　BiNode p=NULL ;</p><p>　　cout<

107、<"請(qǐng)輸入你的二叉樹(請(qǐng)按層次由上往下從左到右依次輸入并按#結(jié)束，如果節(jié)點(diǎn)為空請(qǐng)輸入'0',本遍歷器僅支持單字符),輸入為:\n";</p><p>　　int i=0,j=0; </p><p>　　char b[maxsize]={'#'},n ;</p><p>　　//當(dāng)輸入不為'#'

108、時(shí)給數(shù)組賦值</p><p><b>　　do{ </b></p><p><b>　　cin>>n;</b></p><p>　　if(n!='#') b[i]=n;</p><p><b>　　i++;</b></p><p

109、>　　}while(n!='#');</p><p>　　p=stree_creat(b,0);//創(chuàng)建樹</p><p>　　print(p);//輸出樹</p><p><b>　　return p;</b></p><p><b>　　}</b></p>&

110、lt;p><b>　　//主函數(shù)</b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　int k;</b></p><p>　　cout<<"\n ";</p>

111、;<p>　　cout<<"\n ____________________________________________________________________________ ";</p><p>　　cout<<" | 歡迎使用樹的多種遍歷器

112、 |";</p><p>　　cout<<" | |";</p><p>　　cout<<" |________________________________

113、____________________________________________| \n";</p><p><b>　　do{</b></p><p>　　cout<<"\n ";</p><p>　　cout<<"\n 1.

114、創(chuàng)建二叉樹 ";</p><p>　　cout<<"\n 2.前序遞歸遍歷算法 ";</p><p>　　cout<<"\n 3.中序遞歸遍歷算法 ";</p><p>　　cout<<&q

115、uot;\n 4.后序遞歸遍歷算法 ";</p><p>　　cout<<"\n 5.前序非遞歸遍歷算法 ";</p><p>　　cout<<"\n 6.中序非遞歸遍歷算法 ";

116、</p><p>　　cout<<"\n 7.后序非遞歸遍歷算法 "; </p><p>　　cout<<"\n 8.退出操作\n";</p><p>　　cout<<"請(qǐng)選擇你要進(jìn)行的操作

117、(數(shù)字鍵)：";</p><p><b>　　cin>>k; </b></p><p>　　switch(k){</p><p><b>　　case 1:{</b></p><p>　　p=creat();//調(diào)用creat()創(chuàng)建二叉樹</p><p&

118、gt;<b>　　}break;</b></p><p><b>　　case 2:{</b></p><p>　　cout<<"二叉樹的前序遞歸遍歷 :";</p><p>　　PreOrder(p);//調(diào)用PreOrder(p)前序遍歷</p><p><

119、b>　　} break; </b></p><p><b>　　case 3:{</b></p><p>　　cout<<"二叉樹的中序遞歸遍歷 :";</p><p>　　InOrder(p); //調(diào)用InOrder(p)中序遍歷</p><p><b>　

120、　} break;</b></p><p><b>　　case 4:{</b></p><p>　　cout<<"二叉樹的后序遞歸遍歷 :";</p><p>　　PostOrder(p); //調(diào)用PostOrder(p) 后序遍歷</p><p><b>　　}

121、 break;</b></p><p><b>　　case 5:{</b></p><p>　　cout<<"二叉樹前序非遞歸遍歷:";</p><p>　　F_PreOrder(p); //調(diào)用F_PreOrder(p)前序遍歷</p><p><b>　　}br

122、eak;</b></p><p><b>　　case 6:{</b></p><p>　　cout<<"二叉樹中序非遞歸遍歷:";</p><p>　　F_inOrder(p); //調(diào)用F_inOrder(p) 中序遍歷</p><p><b>　　}break;

123、</b></p><p><b>　　case 7:{</b></p><p>　　cout<<"二叉樹后序非遞歸遍歷:";</p><p>　　F_PostOrder(p);</p><p><b>　　}break;</b></p>&l