第一篇：二叉樹(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)，直到?？铡oid 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ù)遍歷課程設(shè)計(jì)】
數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)告
學(xué)院： 班級(jí)： 學(xué)號(hào)：
姓名：
實(shí)驗(yàn)名稱：二叉樹(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
};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 T data;
//數(shù)據(jù)域，存儲(chǔ)數(shù)據(jù)元素
public BinaryNode
//鏈域，分別指向左、右孩子結(jié)點(diǎn)
//構(gòu)造結(jié)點(diǎn)，參數(shù)分別指定元素和左、右孩子結(jié)點(diǎn)
publicBinaryNode(T data, BinaryNode
{ 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
}
public booleanisLeaf()
//判斷是否葉子結(jié)點(diǎn)
{ returnthis.left==null &&this.right==null;
} } 二、二叉樹(shù)中的遍歷方法的聲明.BinaryTree
public BinaryNode
//根結(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結(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為根的子樹(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結(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結(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
{ 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
//創(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 { BinaryNode { T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因?yàn)門(mén)不一定是String { p = new BinaryNode //創(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 //構(gòu)造給定的一棵二叉樹(shù) { BinaryTree BinaryNode } public static void main(String args[]) { BinaryTree //先根次序遍歷二叉樹(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.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í)驗(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 #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é)果 班級(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 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ù)。第四篇：數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)的遍歷實(shí)驗(yàn)報(bào)告
第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——中序遍歷二叉樹(shù)
點(diǎn)擊咨詢 