第一篇：二叉樹遍歷課程設計】

數據結構程序設計報告

學院： 班級： 學號：

姓名：

實驗名稱：二叉樹的建立與遍歷

一、實驗目的：

1.掌握二叉樹的二叉鏈表存儲結構； 2.掌握二叉樹創建方法；

3.掌握二叉樹的先序、中序、后序的遞歸實現方法。

二、實驗內容和要求：

創建二叉樹，分別對該二叉樹進行先序、中序、后序遍歷，并輸出遍歷結果。

三、叉樹的建立與遍歷代碼如下：

#include #include struct tnode//結點結構體 {

};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;//初始隊列中需要的變量front、rear和計數器counter char ch;printf(“建立二叉樹，請輸入結點:（#表示虛節點,!表示結束)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;//把非#的元素入隊

if(rear==0)//如果是第一個元素，則作為根節點 {

} else {

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

}

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

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

}

}

}

}

front++;

counter++;

else//為#時，計數，但不連接結點 {

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;

四、程序運行結果：

五、程序設計指導：

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

2.void preorder(TNODE *bt)函數：利用遞歸的思想，不斷嵌套循環，讀取結點元素，在每個循環中每次先讀取，再進行進入下一個遞歸循環中。

3.void inorder(TNODE *bt)函數 ：利用遞歸的思想，不斷嵌套循環，讀取結點元素，在每個循環中每次先左子樹，再讀取結點元素，再進行進入下一個遞歸循環中。

4.void postorder(TNODE *bt)函數：利用遞歸的思想，不斷嵌套循環，讀取結點元素，在每個循環中每次先分別進入左右子樹，再進行讀取，再進行進入下一個遞歸循環中。

六、心得體會：

本次數據結構程序設計對我有一定的幫助。通過這次的實踐，使我對數據結構這門課程有了更深入地了解。在寫程序的過程中，我重復地讀課本上的知識，并且漸漸領悟到數據結構編程的方法。在編程中，雖然遇到了一些困難，但我并不氣餒。當程序運行出來時，我感到了快樂?？傊?，通過自己地探索和努力，思維得到了鍛煉，編程能力也有了較大地改善。

第二篇：第四次實驗--二叉樹遍歷

一、二叉鏈表的聲明.BinaryNode public class BinaryNode //二叉樹的二叉鏈表結點類，泛型T指//定結點的元素類型 {

public T data;

//數據域，存儲數據元素

public BinaryNode left, right;

//鏈域，分別指向左、右孩子結點

//構造結點，參數分別指定元素和左、右孩子結點

publicBinaryNode(T data, BinaryNode left, BinaryNode right)

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

}

public BinaryNode(T data)

//構造指定值的葉子結點

{ this(data, null, null);

} publicBinaryNode()

{ this(null, null, null);

}

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

{ returnthis.data.toString();

}

public boolean equals(Object obj)

//比較兩個結點值是否相等，覆蓋Object

//類的equals(obj)方法

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

}

public booleanisLeaf()

//判斷是否葉子結點

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

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

public BinaryNode root;

//根結點，結點結構為二叉鏈表

public BinaryTree()

//構造空二叉樹

{ this.root=null;

}

public booleanisEmpty()

//判斷二叉樹是否空

{ returnthis.root==null;

}

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

public void preOrder()

//先根次序遍歷二叉樹

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

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

}

public void preOrder(BinaryNode p)

//先根次序遍歷以p結點為根的子二叉

//遞歸方法

{ if(p!=null)

//若二叉樹不空

{ System.out.print(p.data.toString()+“ ”);//訪問當前結點

preOrder(p.left);

//按先根次序遍歷當前結點的左子樹，//遞歸調用 preOrder(p.right);

//按先根次序遍歷當前結點的右子樹

//遞歸調用

}

}

public String toString()

//返回先根次序遍歷二叉樹所有結點的描述字符串

{ returntoString(root);

}

private String toString(BinaryNode p)

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

//符串，遞歸算法

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

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

}

public void inOrder()

//中根次序遍歷二叉樹

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

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

}

public void inOrder(BinaryNode p)

//中根次序遍歷以p結點為根的子二叉

//遞歸方法

{ if(p!=null)

{ inOrder(p.left);

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

//中根次序遍歷右子樹，遞歸調用

}

}

public void postOrder()

//后根次序遍歷二叉樹

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

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

}

public void postOrder(BinaryNode p)

//后根次序遍歷以p結點為根的子二叉樹，//遞歸方法

{ if(p!=null)

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

}

}

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

//以先根和中根序列構造二叉樹

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

} //以先根和中根序列創建一棵子樹，子樹根結點值是prelist[preStart]，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];

//根結點值 BinaryNode p=new BinaryNode(elem);

//創建葉子結點 inti=0;while(i

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

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

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

{ for(inti=0;i

}

public BinaryTree(T[] prelist)

//以標明空子樹的先根序列構造二叉樹

{ this.root = create(prelist);

}

//以標明空子樹的先根序列構造一棵子二叉樹，子樹的根值是prelist[i]，返回所創建子樹的根結點 privateinti=0;privateBinaryNode create(T[] prelist)

{ BinaryNode p = null;if(i

{

T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因為T不一定是String

{

p = new BinaryNode(elem);

//創建葉子結點 p.left = create(prelist);

//創建p的左子樹 p.right = create(prelist);

//創建p的右子樹

}

} return p;

}

}

三、運行程序

.BinaryTree_make //運用二叉鏈表及先根和中根遍歷確立并構造二叉樹

public class BinaryTree_make {

public static BinaryTree make()

//構造給定的一棵二叉樹

{ BinaryTreebitree=new BinaryTree();//創建空二叉樹

BinaryNodechild_f, child_d, child_b, child_c;//創建4個二叉鏈表域 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);//創建根結點 returnbitree;

} public static void main(String args[])

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

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

//后根遍歷

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

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

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

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

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

bitree1.postOrder();

} }

//后根遍歷

四、運行結果

五、實驗內容

1.根據圖示的二叉樹，運用二叉鏈表及先中根遍歷構造二叉樹，并在控制臺上顯示出二叉樹：先中后根遍歷

六、附加實驗內容

在上述實驗中，只通二叉鏈表及先根和中根遍歷確立構造二叉樹。沒有給出中根和后根遍歷二叉樹的方法?，F要求同學們寫出中根和后根遍歷確立二叉樹的方法（只寫方法）。

七、實驗報告要求

1.運行結果需要截圖，寫出補充方法體的內容，附加實驗只給方法即可。

2.心得體會不可為空（可寫對此次實驗的看法，亦可寫自己近來學習數據結構的感受等等，內容不限）

第三篇：二叉樹的遍歷學習心得

二叉樹的非遞歸遍歷學習心得

對于學習數據結構的新手來說，二叉樹應該是遇到的一個比較大的難題。對于二叉樹的遍歷，如果使用遞歸的方法，代碼非常簡單，但是有些程序語言不支持遞歸，而且遞歸的執行效率偏低，使許多程序設計人員望而卻步下面我將與大家分享我在學習二叉樹的非遞歸遍歷的過程中遇到的困惑與解答，以供學習和交流。

鑒于有些數據結構資料中沒有介紹樹的結點的棧的結點的構造，首先向大家介紹結點的構造。

typedef struct BitNode { char data;

樹的結點的數據域（以字符型數據為

樹的結點的結構

例）

struct BitNode *lchild,*rchild;

樹的子樹指針

}BitNode,*BitTree;

typedef struct node { BitNode stack;

棧的數據域類型為樹的 結點

棧的結點結構

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

BitTree bt;

樹的根結點 char x;scanf(“%c”,&x);

樹的建立的子函數類型為樹的指針類型

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

} return bt;

如果輸入為’#’，則返回空結點

bt=(BitTree)malloc(sizeof(BitNode));若輸入有效，則申請結點空間 bt->data=x;

裝填結點 插入左子樹 插入右子樹 bt->lchild=Creat_BitTree();bt->rchild=Creat_BitTree();

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

那么輸入應該為ABD##EG###。

接下來是棧的一些操作，因為任何一本數據結構的資料都會在棧和隊列的章節說得很清楚，下面只是做了一些比較小的改動，請讀者自行體會。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;先介紹先序遍歷的算法，先建立根結點，再建立左子樹再到右子樹，遍歷是相對于每一棵子樹來說的，這一點要格外注意。最重要的是要在腦海里建立模型，在后面的后序遍歷中尤顯模型的重要性。void Pre_Order(BitTree T){

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

BitTree T;

printf(“nt********************歡迎來到二叉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);} 樹世界********************n”);

printf(“nt請輸入二叉樹結點，”#“為空樹nt”);T=Creat_BitTree();printf(“n”);

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

}

Pre_Order(T);printf(“nt”);getch();以下是二叉樹的中序遍歷的算法，先從左子樹入棧到底，然后訪問棧頂元素，同時棧頂出棧，再檢測是否存在右子樹，如果存在，從它的右子樹的左子樹入棧到底，如果不存在，訪問棧頂元素，同時棧頂出棧，如此循環，直到棧空。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;二叉樹的遍歷中要數后序遍歷最為復雜，它的棧的構造與前面兩種遍歷方法有所不同，在棧里加了一個標記元素rvisited用來標記其結點的右子樹是否被訪問過，由此來達到最后才訪問根結點的效果。由于程序比較復雜，下面為大家一步步分析。

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)

從左子樹插入到底 {

LinkStack *p;

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

插入棧的時候先設為右子樹未被訪問

int rvisited;BitNode stack;struct node *next;

標記元素，記錄右子樹是否已被訪問

}

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

while(!Empty_Stack(s)){

top=s->next;

取棧頂元素

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

} else

若棧頂元素的右子樹存

{

Pop_Stack(s,q);

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

} 二叉樹的幾種遍歷方法就介紹到這里，以上程序均在ＶＣ++6.0編譯環境下運行通過，值得注意的是，三種遍歷方法不能放在同一個程序中使用，因為樹的遍歷過程伴隨著銷毀，遍歷一次以后下一次的遍歷就變得毫無意義。由于本人水平有限,難免有紕漏差錯之處,請諒解.} } } {

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

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

從根結點的左子樹插入棧到底 參考文獻

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

第四篇：數據結構-二叉樹的遍歷實驗報告

實驗報告

課程名：數據結構（C語言版）實驗名：二叉樹的遍歷 姓名：

班級：

學號：

時間：2014.11.03

一 實驗目的與要求

1.掌握二叉樹的存儲方法 2.掌握二叉樹的三種遍歷方法

3.實現二叉樹的三種遍歷方法中的一種 二 實驗內容

? 接受用戶輸入一株二叉樹

? 輸出這株二叉樹的前根, 中根, 后根遍歷中任意一種的順序 三 實驗結果與分析

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

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

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

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

typedef struct BiTNode { //二叉樹二叉鏈表存儲結構 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序輸入二叉中樹結點的值，空格表示空樹 //構造二叉鏈表表示的二叉樹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){ //采用二叉鏈表存儲結構，先序遍歷二叉樹的遞歸算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉鏈表存儲結構，中序遍歷二叉樹的遞歸算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} }

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

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

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

圖1:二叉樹的遍歷運行結果

第五篇：數據結構實驗報告——中序遍歷二叉樹

班級：380911班

學號：57000211 姓名：徐敏

實驗報告

一，實驗目的：

·掌握二叉樹的鏈式存儲結構； ·掌握構造二叉樹的方法；

·加深對二叉樹的中序遍歷的理解； 二，實驗方法：

·用遞歸調用算法中序遍歷二叉樹。三，實驗步驟：

·通過鏈式存儲建立一顆二叉樹。

·設計一個算法實現中序遍歷二叉樹。四，具體實驗步驟：

#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){

班級：380911班

學號：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));

}

班級：380911班

學號：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;} 五，實驗過程：

·輸出：Input the date;

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

·輸出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上機實驗體會：

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

·通過上機練習，充分理解了鏈式建立二叉樹的算法；

·形象的了解二叉樹的結構，能夠熟練的進行先序，中序，后序遍歷二叉樹。