二叉樹(shù)的建立及遍歷

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三名稱：二叉樹(shù) 姓名：高寧鑫學(xué)號(hào)：201417525班級(jí)：2014175專業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué) 指導(dǎo)老師：黃春艷一、實(shí)驗(yàn)?zāi)康?1)掌握二叉樹(shù)的定義和存儲(chǔ)表示，學(xué)會(huì)建一棵二叉樹(shù)的方法(2)掌握二叉樹(shù)的遍歷（前序，中序，后序）采用遞歸和非遞歸方法二、實(shí)驗(yàn)要求(1)建二叉樹(shù)(2)遍歷三、實(shí)驗(yàn)原理(1)利用遞歸原理建立一棵二叉鏈表的二叉樹(shù)：為了讓每個(gè)結(jié)點(diǎn)確認(rèn)是否有左右孩子，對(duì)原二叉樹(shù)進(jìn)行擴(kuò)展，將二叉樹(shù)中的每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一個(gè)特定值“.”獲得一個(gè)擴(kuò)展二叉樹(shù)，通過(guò)遍歷序列確定一棵二叉樹(shù)。(2)進(jìn)行二叉樹(shù)的遍歷：指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，

2、使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。四、實(shí)驗(yàn)環(huán)境Windows XP系統(tǒng), Vc6軟件五、算法實(shí)現(xiàn)及步驟實(shí)現(xiàn)的主要算法：(1)首先定義二叉樹(shù)的存儲(chǔ)形式，這里使用了二叉鏈表typedef struct Node /創(chuàng)建結(jié)點(diǎn)類型結(jié)構(gòu)體 DataType data; struct Node *LChild; struct Node *RChild; BitNode,*BitTree;(2)建立一個(gè)二叉樹(shù)void CreatBiTree(BitTree *bt) /用擴(kuò)展前序遍歷序列創(chuàng)建二叉樹(shù)如果是當(dāng)前樹(shù)根置為空否則申請(qǐng)一個(gè)新節(jié)點(diǎn)/ char ch; ch=getchar(); if(ch='

3、;.')*bt=NULL; else *bt=(BitTree)malloc(sizeof(BitNode); (*bt)->data=ch; CreatBiTree(&(*bt)->LChild); CreatBiTree(&(*bt)->RChild); (3)建立遞歸方法二叉樹(shù)的前序、中序、后序遍歷void PreOrder(BitTree root) /前序遍歷二叉樹(shù)的遞歸算法 if (root!=NULL) visit(root ->data); PreOrder(root ->LChild); PreOrder(root -&g

4、t;RChild); void InOrder(BitTree root) /中序遍歷二叉樹(shù)的遞歸算法 if (root!=NULL) InOrder(root ->LChild); visit(root ->data); InOrder(root ->RChild); void PostOrder(BitTree root) /后序遍歷求二叉樹(shù)的遞歸算法 if(root!=NULL) PostOrder(root ->LChild); PostOrder(root ->RChild); visit(root ->data); (4)建立非遞歸方法二叉樹(shù)的前

5、序、中序、后序遍歷void preOrder2(BinTree *root) /非遞歸前序遍歷 stack<BinTree*> s;BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) cout<<p->data<<"" s.push(p); p=p->lchild; if(!s.empty() p=s.top(); s.pop(); p=p->rchild；void inOrder2(BinTree *root) /非遞歸中序遍歷 stack<BinTr

6、ee*> s; BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) s.push(p); p=p->lchild; if(!s.empty() p=s.top(); cout<<p->data<<"" s.pop(); p=p->rchild; void postOrder2(BinTree *root) /非遞歸后序遍歷 stack<BTNode*> s; BinTree *p=root; BTNode *temp;while(p!=NULL|!s.e

7、mpty() while(p!=NULL)/沿左子樹(shù)往下搜索，直至出現(xiàn)沒(méi)有左子樹(shù)的結(jié)點(diǎn) BTNode *btn=(BTNode *)malloc(sizeof(BTNode); btn->btnode=p; btn->isFirst=true; s.push(btn); p=p->lchild; if(!s.empty() temp=s.top(); s.pop(); if(temp->isFirst=true) /表示是第一次出現(xiàn)在棧頂 temp->isFirst=false; s.push(temp); p=temp->btnode->rchild

8、; else /第二次出現(xiàn)在棧頂 cout<<temp->btnode->data<<"" p=NULL; 六、實(shí)驗(yàn)結(jié)果遞歸方法的遍歷結(jié)果：非遞歸方法的遍歷結(jié)果：七、心得體會(huì) 通過(guò)這次實(shí)驗(yàn)，讓我對(duì)樹(shù)有了更深入的認(rèn)識(shí)，不僅再次熟悉了樹(shù)以及二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；而且更加清楚二叉樹(shù)的遍歷原理以及三種遍歷方法。在這次實(shí)驗(yàn)中，多次應(yīng)用到了遞歸，這樣讓我進(jìn)一步掌握了遞歸的算法思想。 然而在輸入二叉樹(shù)中的元素時(shí)，只能按設(shè)定的前序遍歷的次序輸入合法的結(jié)點(diǎn)的值，不然程序無(wú)法進(jìn)行?？偟膩?lái)說(shuō)，通過(guò)這次實(shí)驗(yàn)，讓我對(duì)樹(shù)有了更多的認(rèn)識(shí)，明白書(shū)

9、本上的程序一定要自己去調(diào)試，這樣才能將書(shū)本程序與老師講的內(nèi)容融會(huì)貫通，達(dá)到溫故而知新。主程序源代碼：遞歸方法：#include<stdio.h>#include<stdlib.h>#include <malloc.h>#include <conio.h>typedef int DataType; typedef struct Node /創(chuàng)建結(jié)點(diǎn)類型結(jié)構(gòu)體 DataType data; struct Node *LChild; struct Node *RChild; BitNode,*BitTree;void CreatBiTree(BitTr

10、ee *bt) /用擴(kuò)展前序遍歷序列創(chuàng)建二叉樹(shù)如果是當(dāng)前樹(shù)根置為空否則申請(qǐng)一個(gè)新節(jié)點(diǎn)/ char ch; ch=getchar(); if(ch='.')*bt=NULL; else *bt=(BitTree)malloc(sizeof(BitNode); ( *bt)->data=ch; CreatBiTree(&(*bt)->LChild); CreatBiTree(&(*bt)->RChild); void visit(char ch)/訪問(wèn)根節(jié)點(diǎn) printf("%c",ch); void PreOrder(BitT

11、ree root) /前序遍歷二叉樹(shù)的遞歸算法 if (root!=NULL) visit(root ->data); PreOrder(root ->LChild); PreOrder(root ->RChild); void InOrder(BitTree root) /中序遍歷二叉樹(shù)的遞歸算法 if (root!=NULL) InOrder(root ->LChild); visit(root ->data); InOrder(root ->RChild); void PostOrder(BitTree root) /后序遍歷求二叉樹(shù)的遞歸算法 if(

12、root!=NULL) PostOrder(root ->LChild); PostOrder(root ->RChild); visit(root ->data); void main() BitTree T; int layer; layer=0; printf("請(qǐng)輸入二叉樹(shù)中的元素(以擴(kuò)展前序遍歷序列輸入,其中.代表空子樹(shù)):n"); CreatBiTree(&T); printf("前序遍歷序列為:"); PreOrder(T); printf("n中序遍歷序列為:"); InOrder(T); p

13、rintf("n后序遍歷序列為:"); PostOrder(T);非遞歸方法#include <iostream>#include<string.h>#include<stack>using namespace std;typedef struct node char data; struct node *lchild,*rchild;BinTree;typedef struct node1 BinTree *btnode; bool isFirst;BTNode;void creatBinTree(char *s,BinTree *&a

14、mp;root) /創(chuàng)建二叉樹(shù)，s為形如A(B,C(D,E)形式的字符串 int i; bool isRight=false; stack<BinTree*> s1; /存放結(jié)點(diǎn) stack<char> s2; /存放分隔符 BinTree *p,*temp; root->data=s0; root->lchild=NULL; root->rchild=NULL; s1.push(root); i=1; while(i<strlen(s) if(si='(') s2.push(si); isRight=false; else if

15、(si=',') isRight=true; else if(si=')') s1.pop(); s2.pop(); else if(isalpha(si) p=(BinTree *)malloc(sizeof(BinTree); p->data=si; p->lchild=NULL; p->rchild=NULL; temp=s1.top(); if(isRight=true) temp->rchild=p; cout<<temp->data<<"的右孩子是"<<si<

16、<endl; else temp->lchild=p; cout<<temp->data<<"的左孩子是"<<si<<endl; if(si+1='(') s1.push(p); i+; void display(BinTree *root) /顯示樹(shù)形結(jié)構(gòu) if(root!=NULL) cout<<root->data; if(root->lchild!=NULL) cout<<'(' display(root->lchild); i

17、f(root->rchild!=NULL) cout<<',' display(root->rchild); cout<<')' void preOrder2(BinTree *root) /非遞歸前序遍歷 stack<BinTree*> s; BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) cout<<p->data<<"" s.push(p); p=p->lchild; if(!s.empt

18、y() p=s.top(); s.pop(); p=p->rchild; void inOrder2(BinTree *root) /非遞歸中序遍歷 stack<BinTree*> s; BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) s.push(p); p=p->lchild; if(!s.empty() p=s.top(); cout<<p->data<<"" s.pop(); p=p->rchild; void postOrder2(BinTree *root) /非遞歸后序遍歷 stack<BTNode*> s; BinTree *p=root; BTNode *temp; while(p!=NULL|!s.empty() while(p!=NULL) /沿左子樹(shù)一直往下搜索，直至出現(xiàn)沒(méi)有左子樹(shù)的結(jié)點(diǎn) BTNode *btn=(BTNode *)malloc(sizeof(BTNode); btn->btnode=p; b