按給定的先序序列來建立二叉樹

1、課程題目:按給定的先序序列來建立二叉樹班級：10計算機2班 姓名：熊蕓蕓 學號：10070518完成日期：12月2日星期五1、 需求分析1、題目要求1.1 存儲結構: 以二叉鏈表作為二叉樹的存儲結構1.2 二叉樹的創(chuàng)建：以給定的先序序列來創(chuàng)建二叉樹1.3 輸出二叉樹: 以中序和后序序列輸出二叉樹的結點2、測試數據：A B $ D G $ $ $ C E $ H $ $ F $ $（$表示空格符號）二、概要設計ADT BinaryTree 數據對象D： D是具有相同特性的數據元素的集合。 數據關系： R1 <ai-1 ,ai >|ai-1 ,ai D, i=2,.,n 數據關系 R：

2、若D為空集，則稱為空樹； 否則:(1) 在D中存在唯一的稱為根的數據元素root, (2) 當n>1時，其余結點可分為m (m>0)個互不相交的有限集T1, T2, , Tm, 其中每一個子集本身又是一棵樹,稱為根root的子樹。 基本操作： InitStack(SqStack &s) /初始化棧 StackElemty(SqStack &s) /判斷棧是否為空 Push(SqStack &s,BiTree e) /將元素e進棧 Pop(SqStack &s,BiTree &e) /出棧，棧頂元素返回給e CreateBiTree(BiTre

3、e &t) /用先序建立一個二叉樹，空格表示空樹 InOrderTraverse(BiTree t,Status(* Visit)(TElemType e)/用非遞歸方式實現中序遍歷，對每個元素調用函數visit PostorderTraverse(BiTree t) /用遞歸方式實現后序遍歷 ADT BinaryTree3、 詳細設計#include <stdio.h>#include <stdlib.h>typedef int Status;typedef char TElemType;#define OK 1#define ERROR 0#define O

4、VERFLOW -2#define STACK_INIT_SIZE 50#define STACKINCREMENT 10typedef struct BiTNode/樹二叉鏈表的存儲結構TElemType data;struct BiTNode *lchlid,*rchlid;BiTNode,*BiTree;typedef struct /棧的存儲結構 BiTree *base;BiTree *top;int stacksize;SqStack;Status InitStack(SqStack &s)/初始化棧s.base=(BiTree *)malloc(STACK_INIT_SI

5、ZE * sizeof(BiTree);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;Status StackElemty(SqStack &s)/判斷棧是否為空if(s.base!=s.top)return ERROR;return OK;Status Push(SqStack &s,BiTree e)/將元素e進棧if(s.top-s.base>=s.stacksize) /追加分配s.base=(BiTree *)realloc(s.base,(s.stac

6、ksize+STACKINCREMENT)*sizeof(BiTree); if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status Pop(SqStack &s,BiTree &e)/出棧，棧頂元素返回給e if(s.top=s.base) return ERROR;e=*-s.top;return OK;Status CreateBiTree(BiTree &t)/用先序建立一個二叉樹，空格表示空樹TElemTy

7、pe ch;scanf("%c",&ch);if(ch=' ') t=NULL;elseif(!(t=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);t->data=ch; /生成根結點CreateBiTree(t->lchlid); /構造左子樹CreateBiTree(t->rchlid); /構造右子樹return OK;Status Visit(TElemType e)/訪問函數printf("%c",e);return OK;Status InOrder

8、Traverse(BiTree t,Status(* Visit)(TElemType e)/用非遞歸方式實現中序遍歷，對每個元素調用函數visitSqStack s;InitStack(s); /建立一個棧存儲二叉樹的結點BiTree p=t;while(p|!StackElemty(s)if(p)/根指針進棧，遍歷左子樹Push(s,p); p=p->lchlid;else /根指針退棧，訪問根結點，遍歷右子樹Pop(s,p);if(!Visit(p->data) return ERROR;p=p->rchlid;printf("n");return

9、OK;Status PostorderTraverse(BiTree t)/用遞歸方式實現后序遍歷 if(t) PostorderTraverse(t->lchlid); /遍歷左子樹 PostorderTraverse(t->rchlid); /遍歷右子樹 printf("%c",t->data); /訪問結點 return OK;void main()BiTree t;printf("請輸入一串字符:n");CreateBiTree(t);printf("中序遍歷結果為:n");InOrderTraverse(t

10、,Visit);printf("后序遍歷結果為:n"); PostorderTraverse(t);printf("n");4、 調試分析 1、調用基本函數時要注意函數參數類型的變化，如此程序中Pop和Push 2、運行程序時要正確輸入，才能有結果 3、define一個常量時，后面不用加分號 4、關于后序遍歷，用非遞歸的方式編寫時出現錯誤，改寫成遞歸調用了5、要注意一些細節(jié)，比如分號，引號、還有書寫問題6、編程時一定要耐心，程序不可能一次編寫成功，需要經過不斷調試才能發(fā)現并改正錯誤 7、時間復雜度： InitStack( ) O(1)StackElemty