数据结构实验报告-二叉树的实现与遍历

1、-!数据结构第六次实验报告学生姓名 学生班级 学生学号 指导老师一、实验内容1）采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。2）输出树的深度，最大元，最小元。二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子 递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结 束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根 左右，也就是说先访问根结点然后访问其左子再然后 访问其右子。具体算法

2、实现如下：如果结点的指针不为空，结点指针入栈， 输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左 子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问， 如此循环，直至结点指针和栈均为空时，遍历结束。再次介绍中序遍历：中序遍历的顺序是左 根右，中序遍历和先序遍历思想差不多，只是打印顺 序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指 向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并 输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循 环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历：后序遍历的顺序是左 右

3、根，后序遍历是比较难的一种，首先需要建立两个 栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点， 如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈， 并赋值0,表示该结点的右子还没有访问，指针指向该结点的左子，如果结 点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出 栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子， 父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1,表示右子访问过。如果相应的标志位值为 1,表示右子树已经访问完成，此时要 输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和 栈均为空

4、，遍历结束。三、详细设计源代码：#includevstdio.h>#define MAX 100 /表示栈的最大容量#define FULL 99 表示栈满#define EMPTY -1 表示栈空typ edef struct Tnode / 定义结点char data;/存储结点数据struct Tnode *left;/定义结点左子指针struct Tnode *right;/ 定义右子指针 Tnode,*Pnode;/声明Tnode类型的变量和指针 typ edef struct Stack/ 定义栈Pnode pnodeMAX;/ 存放数据int p;/栈顶指针Stack,*P

5、stack;/定义Stack类型的变量和指针 void Push (P stack p stack ,Pn ode pn ode)/入栈 p stack- >p +;p stack- >pn ode p stack- >p = pn ode;/ 赋值Pnode Pop(P stack p stack)/出 栈return p stack- >pn ode p stack- >p-;Pnode Top (P stack pstack)/看栈顶元素return p stack- >pn ode pstack- >p;int Ise mpty (P stac

6、k p stack)/ 栈判空if(p stack-> p=E MPTY) return 1;elsereturn 0;int Isfull (Pstack pstack )/ 栈满if (p stack ->p=FULL)return 1;elsereturn 0;void Initstack (Pstack pstack)/ 初始化栈p stack-p=EMPTY;void Inittnode(Pnode root,Pnode left,Pnode rightchar data)/ 初始化结点root->left=left;root->right = right;r

7、oot->data = data;void P reorderR( Pnode p root)/ 递归先序遍历算法if(p root)p rintf("%2c", proot->data);P reorderR (p root->left);P reorderR (p root->right);void InorderR(Pnode proot)/ 递归中序遍历算法if(p root)InorderR (p root->left);p rintf("%2c", proot->data);InorderR (p root

8、->right);void Po storderR( Pnode p root)/ 递归后序遍历算法if(p root)Po storderR (p root->left);Po storderR (p root->right);p rintf("%2c", proot->data);void P reorderI( Pnode p root, Pstack p stack)/ 非递归先序遍历算法Initstack( pstack);/ 初始化栈while(proot|!lsempty(pstack)/如果栈空并且结点指针空，则结束循环if(p ro

9、ot)p rintf("%2c", proot->data);if(Isfull(pstack)/如果栈满不能执行入栈操作printf("栈满，不能执行入栈操作！")；return;Push( pstack ,p root);/ 入栈 proot=proot->left;/ 指针指向左子 elseif(Isempty(pstack)/栈空时不能出栈printf("栈空，不能执行出栈操作！")；return;proot = Pop(p stack);/ 执行出栈操作 proot=proot->right;/ 指针指向右

10、子void InorderI( Pnode p root, Pstack p stack)/ 非递归中序遍历算法lnitstack( pstack);/ 初始化栈while(proot|!lsempty(pstack)/ 循环结束条件if(p root)if(Isfull( pstack)printf("栈满，不能执行入栈操作！")；return;Push( pstack ,p root);/ 执行入栈操作proot = proot->left;/ 指针指向左子 elseif(Ise mp ty( pstack)printf("栈空，不能执行出栈操作！&qu

11、ot;)；return ;p root = Pop(p stack);/ 出栈printf("%2c",proot->data);/ 打印数据proot=proot->right;/ 指针指向右子void PostorderI( Pnode p root, Pstack p stack)/ 非递归后续遍历算法 int flagsMAX;/定义标志位栈int p =-1;/初始化标志位栈int flag;/存放标志位Initstack( pstack);/ 初始化栈while(proot|!lsempty(pstack)/ 循环结束条件if(p root)if(I

12、sfull( pstack)printf("栈满，不能执行入栈操作！"); return ;flags+p = 0;/标志位置0,并入栈 Push( pstack ,p root);/ 结点入栈 proot=proot->left;/ 指针指向左子elseproot = Pop(p stack);/ 指针出栈flag = flagsp-;/相应标志位出栈if(flag=0)/如果标志位为0表示右子还未访问过 flag =1;/将标志位置1，右子已访问 flags+p = flag;/ 标志位入栈Push( pstack ,p root);/ 结点入栈proot = p

13、root->right;/ 指针指向右子 elseprintf("%2c",proot->data);/ 打印数据 proot = NULL;/将结点指针置空void main ()Tnode A,B,C,D,E,F,G;/ 声明结点变量Stack stack;/声明栈Inittnode(&A,&B,&C,'A');/ 初始化结点Inittnode(&B,NULL,&D,'B');Inittnode(&C,&E,&F,C);Inittnode(&D,NULL,

14、NULL,'D');lnittnode(&E,NULL,NULL,'E');lnittnode(&F,&G ,NULL,'F');Inittnode(&G ,NULL,NULL,'G'); printf("你定义的树的结构是：n");*/* 一下是调用相应的函数输出遍历结果p rintf("A(B(D)C(E F(G)n");下面是遍历结果 递归先序遍历:P reorderR(&A);p rintf("n");p rintf(

15、9;"非递归先序遍历:n");P reorderl(&A,&stack);p rintf("n");p rintf('"递归中序遍历:n");InorderR(&A);P rintf("n");p rintf('"非递归中序遍历:An");InorderI(&A,& stack);p rintf("n");p rintf("递归后序遍历:An");PostorderR(&A);p rintf(

16、"n");p rintf("非递归后序遍历:n");P ostorderl(&A,& stack);p rintf("n");五、遇到的问题及解决办法这部分我主要遇到如下两个问题，其内容和解决方法如下所列:执行程序时程序停止运行，其效果如图: = *匚应卯叭WFL勺De加Q円MPTTcthn日偿琥茁中、二列和殴二叉词却lS0,DcbLig=冏的逅-.,1回,琏 你定爛树的结构是=ACB（D）CCE F（G）I=二二二=下面是遍历結甲=二f J二叉删遍历exe已停It工作Wmdowi可检查该问S妁翼姿方星哗联机检直孵决方

17、案并黃®该桎序X垂看眉題详铝星E解决方法：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不合理，因此对调用的自定义函数进行相应的改动， 将参数由具体类型改为指针类型后，程序正常运行。程序不停的输出同一个结点的数据，其效果入图:*_ C：U$ei 典VJ FpXkgp'mnMj nSS哼结吃1 二 H 1?r的童邱二盘悄胴词预 by 趴tnyprog g” 10湎£心枕1£五赢01)115阪£|0帀五

18、五顽DDDDEE匸EiDDDDEWJjDDDDDODI®丽而dSdDUDDDBDODD *DODDDEDDDDDDDDDDDDDDDDDDDDDDODDDEDDDDDDDEDrDDDDDDODEDDDDDDDDDDDDDDDDDDEDDDODDDD DODODEDDUDDDDEljDBDlJDDmEDElJJDDDlDiiUDDDDIDLDDDDLDOEEDDlJDDjmDlJDlJDDDDDEDDDJDDDD MDDDDDDDDDDDDDDDDDDDDDDDDDMrnTDDDDDDDBrDDDDJDDDDDDDDDDDDDMDDDDDKWDDDDKTD lJDJHJiJlJDDUD

19、UDUDLLiUDUUUiJULlJDDDJD-JLlDiiUDUDUElJLlJDDUJLlDUlJlJDWDDJUl；LDUDUUULDDljUDD2)l>JUD ©MDODDDDDDDDDrJDDDDDDDDDDDD 梵iDODMDDDDDDBrDDDDDDDDDDDDDDDDCDDDDDDDDDDDDDinnODD pD；)XlJDLiDUDUDDDlJDUDDODDDLDDDU：)D.JDLDIiUDDODEDLDDDDDXIDLiDUDUDDLDIiDDUODDCl!DDDU：)I>DDD 'bMDOnmDMDDDEUDDDDDDDPnDTlDMMDn

20、DDnDDDDBirDDDDDDODMiDDDDDmiDDDDDDDWtiriDTlTimX J)DDDC)DCDPDDDDDEBDDDDDDXEDDDD：)JDDtDI'DDDDDDDLDDDDJ)DODDDDDDDDDDDDDDDDDDDDCDDD：)I>3DD bmnDTwriD 皿 rorrnDDDDDDnDnDnDTnmrTriDDDDDmiiTiDnDTinfjmnDDDDDrriiDriDDDDnDriDBEiraTDDD DDDXDEDDDDDDDDDDDDDD0XDDDDDJ)>JDEDDDDDDDCELDDDDDXnDDDDDDDDCDDDDDDDXDC

21、DDDBI>3DD t)D3DrrrTiBnDmnErirmDT)DDnDrrDDD0DTriDTinDr)DDnirrDr)DPD0DrTiDnDninErriTiDT)DDDPDrnDD0WD. DDDDODCDDDDDDDLEDDDDDDXEDDDDOCrDDtDIjDDDDDCDLDDDDDDODCDDDDDDOLEDDDDDDXDCDDDOEFJDDi" I)DDDrjDriDBDDDDDLEDDDDDDDC'DiDDDD：)DDDriD'DDDDDDn)DirDDDBDGDriDDDDDDDEEPDDDDDDODiEDDD：3D3DD UDODGDE

22、DDDDDaDDEDDDDDDDC'EDDEDJDJDLiDDDDDDDEErEDDDBDGDLiDDDDDDDLEDDDDDDDODEDDDODDDIj toODDDEDDDDDaDDEDDDDDDnODEDrDDDDDrDDDDDDDrTrDDDDDDODEDDDDDODDEDDDDDDDODEDPDOroDr ijD3mEDnuDDDDDEDDDBDDDt)L'DDLLr3DJD£DliUDDDDClJJDlLDDDJJDGDLilJElJDD0DDEDUD.UDDDDLEDDlJ3D3DD toD：5DDDEDDDDDDDE-DDDDDDDDDDDDDD：)>DIiDDDDDDCrDDDDDDDDEDDDDDDDCCDDDDDDDDDEDDD)I>DD lJDJDL)iJlJDBDDUJULLD.UDUDDiX)LlJUDUJDJDLDiiUDUDULlJLlJDDDJ)DULlJUDUDDJULLD.UDUDDLX)iJlJUDDJDJ