数据结构二叉树遍历实验二

《数据结构二叉树遍历实验二》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浙江理工大学《数据结构算法》实验报告2016~2017学年第1学期学院信息学院班级姓名学号任课教师：孙树森数字媒体技术专业2016年11月12日实验2树的二叉链表表示及其遍历实验目的：掌握二叉树的链式存储结构及其遍历实验重点：二叉树的链式存储实现方法实验内容：用二叉链表存储结构表示下图所示二叉树的，并用递归方法输出三种遍历结果。1.源代码:#include#include#defineMAXSIZE30typedefstructbnode{chardata;structb

2、node*lchiId,*rchiId;}Bnode,*BTree;typedefBTreeDataType;typedefstruet{DataTypedata[MAXSIZE];inttop;}SeqStack,*PseqStack;//定义一个线性表栈PseqStackInit_SeqStack(void){PseqStackS;S=(PseqStack)maIIoc(sizeof(SeqStack));if(S)S->top=-1;return(S);}//初始化栈。intEmpty_SeqStack

3、(PseqStackS)if(S->top=-1)return⑴;eIsereturn(0);}//判断是否栈空intPush_SeqStack(PseqStackS,DataTypex){_if(S->top二二MAXSIZET)return(0);eIse{S_>top++;S->data[S->top]=x;return⑴;}}〃入栈intPop_SeqStack(PseqStackS,DataType*x){"if(Empty_SeqStack(S))return(0);eIse{*x=S->data

4、[S-〉top];S_>top—;return(1);}//出栈。BTreeCreateBinTree(void)BTreet;charch;ch=getchar();if(ch='和)t二NULL;t=(Bnode*)maIIoc(sizeof(Bnode));t~>data二ch;t->IchiId=CreateBinTree();t->rchiId=CreateBinTree();returnt;}//创建一个二叉树。voidVisit(BTreet)printf("%c”，t~>data);}//访问

5、结点t。voidPostOrder(BTreet){if(t){PostOrder(t->IchiId);PostOrder(t->rchiId);Visit(t);}}//后序遍历voidInOrder(BTreet){if(t){InOrder(t->lchiId);Visit(t);InOrder(t->rchiId);}}//中序遍历。voidPreOrder(BTreet){PseqStackS;BTreep二t;S=lnit_SeqStack();whiIe(p

6、

7、!Empty_SeqStack(

8、S)){~if(p){Visit(p);Push_SeqStack(S,p);p=p->lchiId;}eIse{Pop_SeqStack(S,&p);p=p->rchiId;}}}//先序遍历。voidmain()BTreeT;inta;printf(H输入二叉树的先序排列(空的地方输入*):H);T=CreateBinTree();printf("输出先序遍历：");PreOrder(T);printfCXn");printf("输出中序遍历：");InOrder(T);printfCAn");print

9、f("输出后序遍历：");PostOrder(T);printfCAn");}1.结果展示：12**346***5**申216Processreturned10(OxA)executiontime:3・925sPressanykeytocontinue・彳0^SC:UsersadminDesktop88binDebug88.exe歹364旳551仝633(445H122••••t的历历历逋叉二先中后入岀出岀2.知识分桁(1)先序遍历：先访问根结点，再遍历左子树，最后遍历右子树。而所谓的先，中，后

10、序遍历，是对于根节点来说的。(2)代码具体实现遍历的三种顺序PostOrder(t->IchiId);PostOrder(t->rchiId);Visit(t);//后序InOrder(t->IchiId);Visit(t);InOrder(t~>rchiId);//中序PseqStackS;BTreep二t;S二Init_SeqStack();whiIe(p

11、

12、!Empty_SeqStack(S)