1、;實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)實驗名稱二叉樹的遍歷日期2013/05/30學生學號B11050226姓名枯天蝎班級B110502實驗目的：掌握二叉樹的結(jié)構(gòu)特征，掌握用指針類型描述、遍歷二叉樹的運算。實驗條件：電腦一臺 Vc+6.0實驗內(nèi)容與算法思想：內(nèi)容：P213 實習題 1建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序、中序、和后序），打印輸出遍歷結(jié)果?；疽笕缦拢簭逆I盤接受輸入線序序列，以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立）并對其進行遍歷（先序、中序、后序），然后將遍歷結(jié)果打印輸出。要求采用遞歸和非遞歸兩種方法實現(xiàn)。算法思想：定義二叉樹結(jié)構(gòu)體類型時，也定義了一個順序棧結(jié)

2、構(gòu)體類型，用以輔助完成二叉樹的非遞歸遍歷。由鍵盤輸入二叉樹先序序列，用擴展線序序列函數(shù)接受并創(chuàng)建二叉鏈表。遍歷前先判斷二叉樹是否為空，若為空，執(zhí)行空操作；否則依次執(zhí)行各遍歷函數(shù)相應操作。先序遍歷算法思想，先訪問根節(jié)點，然后按先序遍歷左子樹，再按先序遍歷右子樹。中序遍歷算法思想，先按中序遍歷左子樹，再訪問根節(jié)點，然后按中序訪問右子樹。后序遍歷算法思想，先按后序遍歷左子樹，接著按中序遍歷右子樹，然后訪問根節(jié)點。運行結(jié)果：遞歸算法： 非遞歸算法：實驗總結(jié)（結(jié)論或問題分析）：通過實驗，加深了對C語言尤其是函數(shù)調(diào)用部分的認識和掌握。沒有找到在實驗運行結(jié)果上明確區(qū)分遞歸算法實現(xiàn)的遍歷和非遞歸算法實現(xiàn)的遍歷

3、的方法。實驗成績?nèi)握n教師簽名張紅霞附：源程序：遞歸算法程序#include #include #include #define maxsize 100#define FALSE 0#define TRUE 1typedef struct node /二叉樹結(jié)構(gòu)體類型定義char data;struct node *lchild;struct node *rchild;bitnode,*bitree;/*擴展先序序列創(chuàng)建二叉鏈表*/void cteatebitree(bitree *bt)char ch;ch=getchar();if(ch=.)*bt=NULL;else *bt=(bitree

4、)malloc(sizeof(bitnode);(*bt)-data=ch;cteatebitree(&(*bt)-lchild);cteatebitree(&(*bt)-rchild);/*先序遞歸遍歷*/void preorder(bitree root)if(root!=NULL)printf(%c ,root-data);preorder(root-lchild);preorder(root-rchild);/*中序遞歸遍歷*/void inorder(bitree root)if(root!=NULL)preorder(root-lchild);printf(%c ,root-dat

5、a);preorder(root-rchild);/*后序遞歸遍歷*/void postorder(bitree root)if(root!=NULL)preorder(root-lchild);preorder(root-rchild);printf(%c ,root-data);void main()bitree bt;cteatebitree(&bt);printf(先序遞歸遍歷序列：n);preorder(bt);printf(n);printf(中序遞歸遍歷序列：n);inorder(bt);printf(n);printf(后序遞歸遍歷序列：n);postorder(bt);pri

6、ntf(n);非遞歸算法程序#include #include #include #define FALSE 0#define TRUE 1#define maxsize 100typedef struct node /二叉樹結(jié)構(gòu)體定義char data;struct node *lchild;struct node *rchild;bitnode,*bitree;typedef struct /順序棧結(jié)構(gòu)體定義bitree elemmaxsize;int top;seqstack;int push(seqstack *s,bitree x) /入棧if(s-top=maxsize-1)ret

7、urn(FALSE);s-top+;s-elems-top=x;return(TRUE);bitree pop(seqstack *s,bitree x) /出棧if(s-top=-1) return NULL;elsex=s-elems-top;s-top-;return x;int gettop(seqstack *s,bitree *x) /讀取棧頂元素if(s-top=-1) return FALSE;else*x=s-elems-top;return TRUE;void createbitree(bitree *bt) /擴展先序序列創(chuàng)建二叉鏈表char ch;ch=getchar(

8、);if(ch=.)*bt=NULL;else *bt=(bitree)malloc(sizeof(bitnode);(*bt)-data=ch;createbitree(&(*bt)-lchild);createbitree(&(*bt)-rchild);void preorder1(bitree root,seqstack s) /先序遍歷bitnode *p;p=root;while(p!=NULL|!(s.top=-1)while(p!=NULL)printf(%c,p-data);push(&s,p);p=p-lchild;if(!(s.top=-1)p=pop(&s,p);p=p-

9、rchild;void inorder1(bitree root,seqstack s) /中序遍歷bitnode *p;s.top=-1;p=root;while(p!=NULL|!(s.top=-1)if(p!=NULL)push(&s,p);p=p-lchild;elsep=pop(&s,p);printf(%c,p-data);p=p-rchild;void postorder1(bitree root) /后序遍歷bitnode *p,*q;seqstack s;q=NULL;p=root;s.top=-1;/printf(%c,p-data);while(p!=NULL|!(s.top=-1)while(p!=NULL)push(&s,p); p=p-lchild;if(!(s.top=-1)gettop(&s,&p); if(p-rchild=NULL)|(p-rchild=q)printf(%c,p-data);q=p;p=pop(&s,p);p=NULL;else p=p-rchild;void main() printf(先序序列創(chuàng)建二叉樹n);seqstack s;s.top=-1;bitree root;cr