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

1、課程題目：按給定的先序序列來建立二叉樹班級：10計(jì)算機(jī)2班 姓名：熊蕓蕓 學(xué)號：10070518完成日期：12月2日星期五一、需求分析1、題目要求1.1存儲結(jié)構(gòu)：以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)1.2二叉樹的創(chuàng)建：以給定的先序序列來創(chuàng)建二叉樹1.3輸出二叉樹：以中序和后序序列輸出二叉樹的結(jié)點(diǎn)2、測試數(shù)據(jù)：A B $ D G $ $ $ C E $ H $ $ F $ $二、概要設(shè)計(jì)ADT BinaryTree (數(shù)據(jù)對象D: D是具有相同特性的數(shù)據(jù)元素的集合。£ D, i=2,.,n 數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素 root,(2)當(dāng)n

2、>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集 T1, T2, -,Tm,其中每一個(gè)子集本身又是一棵樹基本操作：InitStack(SqStack &s) /StackElemty(SqStack &s) /Push(SqStack &s,BiTree e) /Pop(SqStack &s,BiTree &e) /CreateBiTree(BiTree &t) /（$表示空格符號）數(shù)據(jù)關(guān)系：R1 = ( <ai-1 ,a i >|a i-1 ,a i，稱為根root的子樹。InOrderTraverse(BiTree

3、 t,Status(* Visit)(TElemType e)/序遍歷，對每個(gè)元素調(diào)用函數(shù)visitPostorderTraverse(BiTree t) / ADT BinaryTree三、詳細(xì)設(shè)計(jì)#include <stdio.h>初始化棧判斷棧是否為空將元素e進(jìn)棧出棧，棧頂元素返回給 e用先序建立一個(gè)二叉樹，空格表示空樹用非遞歸方式實(shí)現(xiàn)中用遞歸方式實(shí)現(xiàn)后序遍歷#include <stdlib.h>typedef int Status;typedef char TElemType;#define OK 1#define ERROR 0#define OVERFLOW

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

5、izeof(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進(jìn)棧if(s.top-s.base>=s.stacksize)( /追加分配s.base=(BiTree*)realloc(s.base,(s.stacksiz

6、e+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)(/出棧，棧頂元素返回給eif(s.top=s.base) return ERROR;e=*-s.top;return OK;Status CreateBiTree(BiTree &t)(/用先序建立一個(gè)二叉樹，空格表示空樹TElemType c

7、h;scanf("%c”,&ch);if(ch=' ') t=NULL;else(if(!(t=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);t->data=ch; /生成根結(jié)點(diǎn)CreateBiTree(t->lchlid); /構(gòu)造左子樹CreateBiTree(t->rchlid); /構(gòu)造右子樹return OK;Status Visit(TElemType e)(/訪問函數(shù)printf("%c”,e);return OK;Status InOrderTraverse(BiT

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

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

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