第一篇：二叉樹(shù)遍歷課程設(shè)計(jì)】

數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)告

學(xué)院： 班級(jí)： 學(xué)號(hào)：

姓名：

實(shí)驗(yàn)名稱(chēng)：二叉樹(shù)的建立與遍歷

一、實(shí)驗(yàn)?zāi)康模?/p>

1.掌握二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)； 2.掌握二叉樹(shù)創(chuàng)建方法；

3.掌握二叉樹(shù)的先序、中序、后序的遞歸實(shí)現(xiàn)方法。

二、實(shí)驗(yàn)內(nèi)容和要求：

創(chuàng)建二叉樹(shù)，分別對(duì)該二叉樹(shù)進(jìn)行先序、中序、后序遍歷，并輸出遍歷結(jié)果。

三、叉樹(shù)的建立與遍歷代碼如下：

#include #include struct tnode//結(jié)點(diǎn)結(jié)構(gòu)體 {

};typedef struct tnode TNODE;

TNODE *creat(void){ TNODE *root,*p;TNODE *queue[50];char data;struct tnode *lchild,*rchild;

int front=0,rear=-1,counter=0;//初始隊(duì)列中需要的變量front、rear和計(jì)數(shù)器counter char ch;printf(“建立二叉樹(shù)，請(qǐng)輸入結(jié)點(diǎn):（#表示虛節(jié)點(diǎn),!表示結(jié)束)n”);

ch=getchar();

while(ch!='!'){ if(ch!='#')

{ p=(TNODE *)malloc(sizeof(TNODE));

p->data=ch;

p->lchild=NULL;

p->rchild=NULL;rear++;

queue[rear]=p;//把非#的元素入隊(duì)

if(rear==0)//如果是第一個(gè)元素，則作為根節(jié)點(diǎn) {

} else {

if(counter%2==1)//奇數(shù)時(shí)與其雙親的左子樹(shù)連接 {

}

if(counter%2==0)//偶數(shù)時(shí)與其雙親的右子樹(shù)連接 {

queue[front]->rchild=p;queue[front]->lchild=p;root=p;counter++;

}

}

}

}

front++;

counter++;

else//為#時(shí)，計(jì)數(shù)，但不連接結(jié)點(diǎn) {

if(counter%2==0)

front++;counter++;

}

ch=getchar();} return root;void preorder(TNODE *bt)//先序遍歷 {

if(bt!=NULL){

printf(“%c

”,bt->data);preorder(bt->lchild);preorder(bt->rchild);

} } void inorder(TNODE *bt)//中序遍歷 {

if(bt!=NULL){

inorder(bt->lchild);printf(“%c

”,bt->data);inorder(bt->rchild);

} }

void postorder(TNODE *bt)//后序遍歷 {

if(bt!=NULL){

postorder(bt->lchild);postorder(bt->rchild);printf(“%c

”,bt->data);

} } int main(){

TNODE *root;

root=creat();printf(“遞歸先序遍歷是:”);

preorder(root);

printf(“n”);printf(“遞歸中序遍歷是：”);inorder(root);printf(“n”);

} printf(“遞歸后序遍歷是：”);postorder(root);printf(“n”);return 0;

四、程序運(yùn)行結(jié)果：

五、程序設(shè)計(jì)指導(dǎo)：

1.創(chuàng)建二叉樹(shù)的算法：首先對(duì)一般的二叉樹(shù)，添加若干個(gè)虛結(jié)點(diǎn)使其成為完全二叉樹(shù)，然后依次輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)，則建立一個(gè)新結(jié)點(diǎn)，若是第一個(gè)，則令其為根結(jié)點(diǎn)，否則將新結(jié)點(diǎn)鏈接至它的雙親結(jié)點(diǎn)上。如此重復(fù)下去，直至遇到輸入結(jié)束符（自定）為止。為了使新結(jié)點(diǎn)能夠與雙親結(jié)點(diǎn)正確相連，并考慮到這種方法中先建立的結(jié)點(diǎn)其孩子結(jié)點(diǎn)也一定先建立的特點(diǎn)，可以設(shè)置一個(gè)指針類(lèi)型的數(shù)組構(gòu)成的隊(duì)列來(lái)保存已輸入結(jié)點(diǎn)的地址，并使隊(duì)尾(rear)指向當(dāng)前輸入的結(jié)點(diǎn)，隊(duì)頭(front)指向這個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的前一個(gè)位置。由于根結(jié)點(diǎn)的地址放在隊(duì)列的第一個(gè)單元里，所以當(dāng)rear為奇數(shù)時(shí)，則rear所指的結(jié)點(diǎn)應(yīng)作為左孩子與其雙親鏈接，否則rear所指的結(jié)點(diǎn)應(yīng)作為右孩子與其雙親鏈接。若雙親結(jié)點(diǎn)或孩子結(jié)點(diǎn)為虛結(jié)點(diǎn)，則無(wú)須鏈接。若一個(gè)雙親結(jié)點(diǎn)與兩個(gè)孩子鏈接完畢，則進(jìn)行出隊(duì)操作，使隊(duì)頭指針指向下一個(gè)待鏈接的雙親結(jié)點(diǎn)。

2.void preorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點(diǎn)元素，在每個(gè)循環(huán)中每次先讀取，再進(jìn)行進(jìn)入下一個(gè)遞歸循環(huán)中。

3.void inorder(TNODE *bt)函數(shù) ：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點(diǎn)元素，在每個(gè)循環(huán)中每次先左子樹(shù)，再讀取結(jié)點(diǎn)元素，再進(jìn)行進(jìn)入下一個(gè)遞歸循環(huán)中。

4.void postorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點(diǎn)元素，在每個(gè)循環(huán)中每次先分別進(jìn)入左右子樹(shù)，再進(jìn)行讀取，再進(jìn)行進(jìn)入下一個(gè)遞歸循環(huán)中。

六、心得體會(huì)：

本次數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)對(duì)我有一定的幫助。通過(guò)這次的實(shí)踐，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程有了更深入地了解。在寫(xiě)程序的過(guò)程中，我重復(fù)地讀課本上的知識(shí)，并且漸漸領(lǐng)悟到數(shù)據(jù)結(jié)構(gòu)編程的方法。在編程中，雖然遇到了一些困難，但我并不氣餒。當(dāng)程序運(yùn)行出來(lái)時(shí)，我感到了快樂(lè)?？傊?，通過(guò)自己地探索和努力，思維得到了鍛煉，編程能力也有了較大地改善。

第二篇：第四次實(shí)驗(yàn)--二叉樹(shù)遍歷

一、二叉鏈表的聲明.BinaryNode public class BinaryNode //二叉樹(shù)的二叉鏈表結(jié)點(diǎn)類(lèi)，泛型T指//定結(jié)點(diǎn)的元素類(lèi)型 {

public T data;

//數(shù)據(jù)域，存儲(chǔ)數(shù)據(jù)元素

public BinaryNode left, right;

//鏈域，分別指向左、右孩子結(jié)點(diǎn)

//構(gòu)造結(jié)點(diǎn)，參數(shù)分別指定元素和左、右孩子結(jié)點(diǎn)

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

{ this.data = data;this.left = left;this.right = right;

}

public BinaryNode(T data)

//構(gòu)造指定值的葉子結(jié)點(diǎn)

{ this(data, null, null);

} publicBinaryNode()

{ this(null, null, null);

}

//可聲明以下方法 public String toString()

{ returnthis.data.toString();

}

public boolean equals(Object obj)

//比較兩個(gè)結(jié)點(diǎn)值是否相等，覆蓋Object

//類(lèi)的equals(obj)方法

{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode)obj).data);

}

public booleanisLeaf()

//判斷是否葉子結(jié)點(diǎn)

{ returnthis.left==null &&this.right==null;

} } 二、二叉樹(shù)中的遍歷方法的聲明.BinaryTree public class BinaryTree {

public BinaryNode root;

//根結(jié)點(diǎn)，結(jié)點(diǎn)結(jié)構(gòu)為二叉鏈表

public BinaryTree()

//構(gòu)造空二叉樹(shù)

{ this.root=null;

}

public booleanisEmpty()

//判斷二叉樹(shù)是否空

{ returnthis.root==null;

}

//二叉樹(shù)的先根、中根和后根次序遍歷算法

public void preOrder()

//先根次序遍歷二叉樹(shù)

{ System.out.print(“先根次序遍歷二叉樹(shù)：

”);preOrder(root);//調(diào)用先根次序遍歷二叉樹(shù)的遞歸方法 System.out.println();

}

public void preOrder(BinaryNode p)

//先根次序遍歷以p結(jié)點(diǎn)為根的子二叉

//遞歸方法

{ if(p!=null)

//若二叉樹(shù)不空

{ System.out.print(p.data.toString()+“ ”);//訪問(wèn)當(dāng)前結(jié)點(diǎn)

preOrder(p.left);

//按先根次序遍歷當(dāng)前結(jié)點(diǎn)的左子樹(shù)，//遞歸調(diào)用 preOrder(p.right);

//按先根次序遍歷當(dāng)前結(jié)點(diǎn)的右子樹(shù)

//遞歸調(diào)用

}

}

public String toString()

//返回先根次序遍歷二叉樹(shù)所有結(jié)點(diǎn)的描述字符串

{ returntoString(root);

}

private String toString(BinaryNode p)

//返回先根次序遍歷以p為根的子樹(shù)描述字

//符串，遞歸算法

{ if(p==null)return “";

return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//遞歸調(diào)用

}

public void inOrder()

//中根次序遍歷二叉樹(shù)

{ System.out.print(”中根次序遍歷二叉樹(shù)：

“);inOrder(root);System.out.println();

}

public void inOrder(BinaryNode p)

//中根次序遍歷以p結(jié)點(diǎn)為根的子二叉

//遞歸方法

{ if(p!=null)

{ inOrder(p.left);

//中根次序遍歷左子樹(shù)，遞歸調(diào)用 System.out.print(p.data.toString()+” “);inOrder(p.right);

//中根次序遍歷右子樹(shù)，遞歸調(diào)用

}

}

public void postOrder()

//后根次序遍歷二叉樹(shù)

{ System.out.print(”后根次序遍歷二叉樹(shù)：

“);postOrder(root);System.out.println();

}

public void postOrder(BinaryNode p)

//后根次序遍歷以p結(jié)點(diǎn)為根的子二叉樹(shù)，//遞歸方法

{ if(p!=null)

{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “);

}

}

public BinaryTree(T[] prelist, T[] inlist)

//以先根和中根序列構(gòu)造二叉樹(shù)

{ this.root = create(prelist, inlist, 0, 0, prelist.length);

} //以先根和中根序列創(chuàng)建一棵子樹(shù)，子樹(shù)根結(jié)點(diǎn)值是prelist[preStart]，n指定子序列長(zhǎng)度.//返回所創(chuàng)建子樹(shù)的根結(jié)點(diǎn)

privateBinaryNode create(T[] prelist, T[] inlist, intpreStart, intinStart, int n)

{ System.out.print(”prelist:“);print(prelist, preStart, n);System.out.print(”，inlist:“);print(inlist, inStart, n);System.out.println();

if(n<=0)return null;

T elem=prelist[preStart];

//根結(jié)點(diǎn)值 BinaryNode p=new BinaryNode(elem);

//創(chuàng)建葉子結(jié)點(diǎn) inti=0;while(i

//在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i);

//創(chuàng)建左子樹(shù) p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//創(chuàng)建右子樹(shù) return p;

} private void print(T[] table, int start, int n)

{ for(inti=0;i

}

public BinaryTree(T[] prelist)

//以標(biāo)明空子樹(shù)的先根序列構(gòu)造二叉樹(shù)

{ this.root = create(prelist);

}

//以標(biāo)明空子樹(shù)的先根序列構(gòu)造一棵子二叉樹(shù)，子樹(shù)的根值是prelist[i]，返回所創(chuàng)建子樹(shù)的根結(jié)點(diǎn) privateinti=0;privateBinaryNode create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因?yàn)門(mén)不一定是String

{

p = new BinaryNode(elem);

//創(chuàng)建葉子結(jié)點(diǎn) p.left = create(prelist);

//創(chuàng)建p的左子樹(shù) p.right = create(prelist);

//創(chuàng)建p的右子樹(shù)

}

} return p;

}

}

三、運(yùn)行程序

.BinaryTree_make //運(yùn)用二叉鏈表及先根和中根遍歷確立并構(gòu)造二叉樹(shù)

public class BinaryTree_make {

public static BinaryTree make()

//構(gòu)造給定的一棵二叉樹(shù)

{ BinaryTreebitree=new BinaryTree();//創(chuàng)建空二叉樹(shù)

BinaryNodechild_f, child_d, child_b, child_c;//創(chuàng)建4個(gè)二叉鏈表域 child_d = new BinaryNode(”D“, null, new BinaryNode(”G“));child_b = new BinaryNode(”B“, child_d, null);child_f = new BinaryNode(”F“, new BinaryNode(”H“), null);child_c = new BinaryNode(”C“, new BinaryNode(”E“), child_f);bitree.root = new BinaryNode(”小唐“, child_b, child_c);//創(chuàng)建根結(jié)點(diǎn) returnbitree;

} public static void main(String args[])

{ BinaryTreebitree = make();bitree.preOrder();

//先根次序遍歷二叉樹(shù) bitree.inOrder();//中根遍歷 bitree.postOrder();

//后根遍歷

String[] prelist = {”A“,”B“,”D“,”G“,”C“,”E“,”F“,”H“};//采用先根中根兩種遍歷

String[] inlist = {”D“,”G“,”B“,”A“,”E“,”C“,”H“,”F"};

//確定一顆二叉樹(shù) BinaryTree bitree1 = new BinaryTree(prelist, inlist);

bitree1.preOrder();// 先根遍歷

bitree1.inOrder();//中根遍歷

bitree1.postOrder();

} }

//后根遍歷

四、運(yùn)行結(jié)果

五、實(shí)驗(yàn)內(nèi)容

1.根據(jù)圖示的二叉樹(shù)，運(yùn)用二叉鏈表及先中根遍歷構(gòu)造二叉樹(shù)，并在控制臺(tái)上顯示出二叉樹(shù)：先中后根遍歷

六、附加實(shí)驗(yàn)內(nèi)容

在上述實(shí)驗(yàn)中，只通二叉鏈表及先根和中根遍歷確立構(gòu)造二叉樹(shù)。沒(méi)有給出中根和后根遍歷二叉樹(shù)的方法?，F(xiàn)要求同學(xué)們寫(xiě)出中根和后根遍歷確立二叉樹(shù)的方法（只寫(xiě)方法）。

七、實(shí)驗(yàn)報(bào)告要求

1.運(yùn)行結(jié)果需要截圖，寫(xiě)出補(bǔ)充方法體的內(nèi)容，附加實(shí)驗(yàn)只給方法即可。

2.心得體會(huì)不可為空（可寫(xiě)對(duì)此次實(shí)驗(yàn)的看法，亦可寫(xiě)自己近來(lái)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的感受等等，內(nèi)容不限）

第三篇：二叉樹(shù)的遍歷學(xué)習(xí)心得

二叉樹(shù)的非遞歸遍歷學(xué)習(xí)心得

對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的新手來(lái)說(shuō)，二叉樹(shù)應(yīng)該是遇到的一個(gè)比較大的難題。對(duì)于二叉樹(shù)的遍歷，如果使用遞歸的方法，代碼非常簡(jiǎn)單，但是有些程序語(yǔ)言不支持遞歸，而且遞歸的執(zhí)行效率偏低，使許多程序設(shè)計(jì)人員望而卻步下面我將與大家分享我在學(xué)習(xí)二叉樹(shù)的非遞歸遍歷的過(guò)程中遇到的困惑與解答，以供學(xué)習(xí)和交流。

鑒于有些數(shù)據(jù)結(jié)構(gòu)資料中沒(méi)有介紹樹(shù)的結(jié)點(diǎn)的棧的結(jié)點(diǎn)的構(gòu)造，首先向大家介紹結(jié)點(diǎn)的構(gòu)造。

typedef struct BitNode { char data;

樹(shù)的結(jié)點(diǎn)的數(shù)據(jù)域（以字符型數(shù)據(jù)為

樹(shù)的結(jié)點(diǎn)的結(jié)構(gòu)

例）

struct BitNode *lchild,*rchild;

樹(shù)的子樹(shù)指針

}BitNode,*BitTree;

typedef struct node { BitNode stack;

棧的數(shù)據(jù)域類(lèi)型為樹(shù)的 結(jié)點(diǎn)

棧的結(jié)點(diǎn)結(jié)構(gòu)

struct node *next;}LinkStack;遍歷的前提當(dāng)然是二叉樹(shù)存在，下面為大家介紹樹(shù)的建立。BitTree Creat_BitTree(){

BitTree bt;

樹(shù)的根結(jié)點(diǎn) char x;scanf(“%c”,&x);

樹(shù)的建立的子函數(shù)類(lèi)型為樹(shù)的指針類(lèi)型

} if(x=='#')bt=NULL;else {

} return bt;

如果輸入為’#’，則返回空結(jié)點(diǎn)

bt=(BitTree)malloc(sizeof(BitNode));若輸入有效，則申請(qǐng)結(jié)點(diǎn)空間 bt->data=x;

裝填結(jié)點(diǎn) 插入左子樹(shù) 插入右子樹(shù) bt->lchild=Creat_BitTree();bt->rchild=Creat_BitTree();

建立二叉樹(shù)的過(guò)程使用了遞歸，如果理解不了，可以自己畫(huà)圖助于理解，建立決定了二叉樹(shù)的形狀，一定要弄清楚。如所要建立的二叉樹(shù)的形狀為

那么輸入應(yīng)該為ABD##EG###。

接下來(lái)是棧的一些操作，因?yàn)槿魏我槐緮?shù)據(jù)結(jié)構(gòu)的資料都會(huì)在棧和隊(duì)列的章節(jié)說(shuō)得很清楚，下面只是做了一些比較小的改動(dòng)，請(qǐng)讀者自行體會(huì)。int Init_Stack(LinkStack **s){

}

int Push_Stack(LinkStack *s,BitNode *x)

*s=(LinkStack*)malloc(sizeof(LinkStack));(*s)->next=NULL;return 1;{

}

int Pop_Stack(LinkStack *s,BitNode *e){

return 0;}

}

int Empty_Stack(LinkStack *s){

}

if(s->next==NULL)return 1;return 0;LinkStack *p;

if(Empty_Stack(s)){ printf(“Stack is NULLn”);p=s->next;s->next=p->next;*e=p->stack;free(p);return 1;LinkStack *p;

p=(LinkStack*)malloc(sizeof(LinkStack));p->stack=*x;p->next=s->next;s->next=p;return 1;先介紹先序遍歷的算法，先建立根結(jié)點(diǎn)，再建立左子樹(shù)再到右子樹(shù)，遍歷是相對(duì)于每一棵子樹(shù)來(lái)說(shuō)的，這一點(diǎn)要格外注意。最重要的是要在腦海里建立模型，在后面的后序遍歷中尤顯模型的重要性。void Pre_Order(BitTree T){

} 以下是主函數(shù)。int main(){

BitTree T;

printf(“nt********************歡迎來(lái)到二叉LinkStack *s;BitTree p;p=T;

Init_Stack(&s);Push_Stack(s,p);while(!Empty_Stack(s)){

Pop_Stack(s,p);

printf(”t[%c]“,p->data);

if(p->rchild)Push_Stack(s,p->rchild);if(p->lchild)Push_Stack(s,p->lchild);} 樹(shù)世界********************n”);

printf(“nt請(qǐng)輸入二叉樹(shù)結(jié)點(diǎn)，”#“為空樹(shù)nt”);T=Creat_BitTree();printf(“n”);

printf(“t先序遍歷二叉樹(shù)如下：”);printf(“n”);

}

Pre_Order(T);printf(“nt”);getch();以下是二叉樹(shù)的中序遍歷的算法，先從左子樹(shù)入棧到底，然后訪問(wèn)棧頂元素，同時(shí)棧頂出棧，再檢測(cè)是否存在右子樹(shù)，如果存在，從它的右子樹(shù)的左子樹(shù)入棧到底，如果不存在，訪問(wèn)棧頂元素，同時(shí)棧頂出棧，如此循環(huán)，直到?？?。void In_Order(BitTree T){

}

LinkStack *s;BitTree p,q;

q=(BitTree)malloc(sizeof(BitNode));p=T;

Init_Stack(&s);

while(p ||!Empty_Stack(s)){ if(p){

} else {

} }

Pop_Stack(s,q);

printf(“t[%c]”,q->data);p=q->rchild;Push_Stack(s,p);p=p->lchild;二叉樹(shù)的遍歷中要數(shù)后序遍歷最為復(fù)雜，它的棧的構(gòu)造與前面兩種遍歷方法有所不同，在棧里加了一個(gè)標(biāo)記元素rvisited用來(lái)標(biāo)記其結(jié)點(diǎn)的右子樹(shù)是否被訪問(wèn)過(guò)，由此來(lái)達(dá)到最后才訪問(wèn)根結(jié)點(diǎn)的效果。由于程序比較復(fù)雜，下面為大家一步步分析。

typedef struct node {

}LinkStack;int Push_Stack(LinkStack *s,BitNode *x){

} void Post_Order(BitTree T){

BitTree p,q;LinkStack *s,*top;Init_Stack(&s);p=T;

q=(BitTree)malloc(sizeof(BitNode));while(p)

從左子樹(shù)插入到底 {

LinkStack *p;

p=(LinkStack *)malloc(sizeof(LinkStack));p->stack=*x;p->rvisited=0;p->next=s->next;s->next=p;return 1;

插入棧的時(shí)候先設(shè)為右子樹(shù)未被訪問(wèn)

int rvisited;BitNode stack;struct node *next;

標(biāo)記元素，記錄右子樹(shù)是否已被訪問(wèn)

}

Push_Stack(s,p);p=p->lchild;

while(!Empty_Stack(s)){

top=s->next;

取棧頂元素

if(!top->stack.rchild || top->rvisited)若棧頂元素的右子樹(shù)不存在或者被訪問(wèn)過(guò)，訪問(wèn)棧頂元素同時(shí)出棧

} else

若棧頂元素的右子樹(shù)存

{

Pop_Stack(s,q);

printf(“t[%c]”,q->data);在而且未被訪問(wèn)過(guò)，先將其rvisited值設(shè)為1再向右檢測(cè)右子樹(shù)

} 二叉樹(shù)的幾種遍歷方法就介紹到這里，以上程序均在ＶＣ++6.0編譯環(huán)境下運(yùn)行通過(guò)，值得注意的是，三種遍歷方法不能放在同一個(gè)程序中使用，因?yàn)闃?shù)的遍歷過(guò)程伴隨著銷(xiāo)毀，遍歷一次以后下一次的遍歷就變得毫無(wú)意義。由于本人水平有限,難免有紕漏差錯(cuò)之處,請(qǐng)諒解.} } } {

top->rvisited=1;p=top->stack.rchild;while(p){

Push_Stack(s,p);p=p->lchild;

從根結(jié)點(diǎn)的左子樹(shù)插入棧到底 參考文獻(xiàn)

(稻草人)[ 1 ] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程[M ].北京: 清華大學(xué)出版社, 1995: 71291.[ 2 ] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M ].北京: 清華大學(xué)出版社, 2000: 962106.[ 3 ] 耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)—C語(yǔ)言描述[M ].西安: 西安電子科技大學(xué) 出版社, 2006: 1012104.[ ４]崔進(jìn)平,郭小春,王霞.數(shù)據(jù)結(jié)構(gòu)(Ｃ語(yǔ)言版)[M ].北京:清華大學(xué)出版社,2011: 245868.(稻草人)

第四篇：數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)的遍歷實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告

課程名：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）實(shí)驗(yàn)名：二叉樹(shù)的遍歷 姓名：

班級(jí)：

學(xué)號(hào)：

時(shí)間：2014.11.03

一 實(shí)驗(yàn)?zāi)康呐c要求

1.掌握二叉樹(shù)的存儲(chǔ)方法 2.掌握二叉樹(shù)的三種遍歷方法

3.實(shí)現(xiàn)二叉樹(shù)的三種遍歷方法中的一種 二 實(shí)驗(yàn)內(nèi)容

? 接受用戶輸入一株二叉樹(shù)

? 輸出這株二叉樹(shù)的前根, 中根, 后根遍歷中任意一種的順序 三 實(shí)驗(yàn)結(jié)果與分析

//*********************************************************** //頭文件

#include #include //*********************************************************** //宏定義

#define OK 1 #define ERROR 0 #define OVERFLOW 0

//***********************************************************

typedef struct BiTNode { //二叉樹(shù)二叉鏈表存儲(chǔ)結(jié)構(gòu) char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序輸入二叉中樹(shù)結(jié)點(diǎn)的值，空格表示空樹(shù) //構(gòu)造二叉鏈表表示的二叉樹(shù)T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，先序遍歷二叉樹(shù)的遞歸算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，中序遍歷二叉樹(shù)的遞歸算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} }

//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，后序遍歷二叉樹(shù)的遞歸算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} }

//*********************************************************** void main(){ //主函數(shù)分別實(shí)現(xiàn)建立并輸出先、中、后序遍歷二叉樹(shù)

printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍歷二叉樹(shù):”);PreOrderTraverse(Tree);printf(“n中序遍歷二叉樹(shù):”);InOrderTraverse(Tree);printf(“n后序遍歷二叉樹(shù):”);PostOrderTraverse(Tree);}

圖1:二叉樹(shù)的遍歷運(yùn)行結(jié)果

第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——中序遍歷二叉樹(shù)

班級(jí)：380911班

學(xué)號(hào)：57000211 姓名：徐敏

實(shí)驗(yàn)報(bào)告

一，實(shí)驗(yàn)?zāi)康模?/p>

·掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)； ·掌握構(gòu)造二叉樹(shù)的方法；

·加深對(duì)二叉樹(shù)的中序遍歷的理解； 二，實(shí)驗(yàn)方法：

·用遞歸調(diào)用算法中序遍歷二叉樹(shù)。三，實(shí)驗(yàn)步驟：

·通過(guò)鏈?zhǔn)酱鎯?chǔ)建立一顆二叉樹(shù)。

·設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)中序遍歷二叉樹(shù)。四，具體實(shí)驗(yàn)步驟：

#include #include #define LEFT 0 #define RIGHT 1 #define TRUE 1 #define FALSE 0

typedef struct _BTNODE{ char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE;

void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p);

void main(){ PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf(“Input the data:”);ConstructBTree(p);PrintBTree(p,0);printf(“Now InorderTraverse:”);InorderTraverse(p);printf(“nPress any key to continue...”);getchar();}

void PrintBTree(PBTNODE p,int depth){

班級(jí)：380911班

學(xué)號(hào)：57000211 姓名：徐敏

int i;if(p==NULL){

return;}else{ for(i=0;i

printf(“--”);} printf(“>”);

printf(“%cn”,p->c);

PrintBTree(p->lchild,depth+1);

PrintBTree(p->rchild,depth+1);} }

void ConstructBTree(PBTNODE p){ int side;char c;side=LEFT;while(TRUE){

scanf(“%c”,&c);

if(c=='n'){

//printf(“EOFn”);

return;

} // printf(“%dn”,c);

switch(c){

case '|':

break;

case')':

return;

case',':

side=RIGHT;

break;

case'(':

if(side==LEFT){

if(p->lchild==NULL){

p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));

}

ConstructBTree(p->lchild);

}else{

if(p->rchild==NULL){

p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));

}

班級(jí)：380911班

學(xué)號(hào)：57000211 姓名：徐敏

ConstructBTree(p->rchild);

}

break;

default:

if(side==LEFT){

p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));

p->lchild->c=c;

}else{

p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));

p->rchild->c=c;

}

} } }

void InorderTraverse(PBTNODE p){ if(p==NULL){

return;}else{

InorderTraverse(p->lchild);

printf(“[%c] ”,p->c);

InorderTraverse(p->rchild);} return;} 五，實(shí)驗(yàn)過(guò)程：

·輸出：Input the date;

·輸入：1(2(3,4),5(6,7));

·輸出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上機(jī)實(shí)驗(yàn)體會(huì)：

·體會(huì)到熟練掌握各種程序算法的重要性；

·通過(guò)上機(jī)練習(xí)，充分理解了鏈?zhǔn)浇⒍鏄?shù)的算法；

·形象的了解二叉樹(shù)的結(jié)構(gòu)，能夠熟練的進(jìn)行先序，中序，后序遍歷二叉樹(shù)。