《数据结构实验报告-二叉树的实现与遍历》由会员分享，可在线阅读，更多相关《数据结构实验报告-二叉树的实现与遍历（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。2) 输出树的深度，最大元，最小元。二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子 递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结 束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法：首先介绍先序遍历： 先序遍历的顺序是根 左 右，也就是说先访问根结点然后访问其左子再然后 访问其右子。具体算
2、法实现如下：如果结点的指针不为空，结点指针入栈， 输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左 子树访问结束， 栈顶结点指针出栈， 指针指向其右子， 对其右子树进行访问， 如此循环，直至结点指针和栈均为空时，遍历结束。再次介绍中序遍历：中序遍历的顺序是左 根 右，中序遍历和先序遍历思想差不多，只是打印顺 序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指 向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并 输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循 环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历： 后序遍历的顺
3、序是左 右 根，后序遍历是比较难的一种，首先需要建立两个 栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点， 如果结点的指针不为空， 根结点入栈，与之对应的标志位也随之入标志位栈， 并赋值 0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结 点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出 栈，如果相应的标志位值为 0，表示右子树还没有访问，指针指向其右子， 父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为 1，表示右子树已经访问完成，此时要 输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结
4、点指针和 栈均为空，遍历结束。三、详细设计源代码：#include#define MAX 100 / 表示栈的最大容量 #define FULL 99/ 表示栈满#define EMPTY -1/ 表示栈空typedef struct Tnode / 定义结点char data;/存储结点数据struct Tnode *left;/ 定义结点左子指针 struct Tnode *right;/ 定义右子指针 Tnode,*Pnode;/ 声明 Tnode 类型的变量和指针 typedef struct Stack/ 定义栈Pnode pnodeMAX;/ 存放数据int p ; /栈顶指针St
5、ack,*Pstack;定义Stack类型的变量和指针 void Push (Pstack pstack,Pnode pnode)/入栈 pstack-p +;pstack-pnodepstack-p = pnode;/ 赋值Pnode Pop(Pstack pstack)/出 栈return pstack-pnodepstack-p-;Pnode Top (Pstack pstack)/看 栈顶元素return pstack-pnodepstack-p;int Isempty (Pstack pstack)/ 栈判空if(pstack-p=EMPTY)return 1;elsereturn
6、0;int Isfull (Pstack pstack )/栈满if (pstack -p=FULL)return 1;elsereturn 0;void Initstack (Pstack pstack)/ 初始化栈pstack-p=EMPTY;void Inittnode(Pnode root,Pnode left,Pnode right,char data)/ 初始化结点 root-left=left;root-right = right;root-data = data;void PreorderR(Pnode proot)/ 递归先序遍历算法if(proot)printf(%2c,p
7、root-data);PreorderR(proot-left);PreorderR(proot-right);void InorderR(Pnode proot)/ 递归中序遍历算法if(proot)InorderR(proot-left); printf(%2c,proot-data);InorderR(proot-right);void PostorderR(Pnode proot)/ 递归后序遍历算法if(proot)PostorderR(proot-left);PostorderR(proot-right);printf(%2c,proot-data);void PreorderI(
8、Pnode proot,Pstack pstack)/ 非递归先序遍历算法 Initstack(pstack);/ 初始化栈 while(proot|!Isempty(pstack)/ 如果栈空并且结点指针空，则结束循环 if(proot)printf(%2c,proot-data);if(Isfull(pstack)/ 如果栈满不能执行入栈操作printf( 栈满，不能执行入栈操作！ );return;Push(pstack,proot); 入栈proot=proot-left;/ 指针指向左子elseif(Isempty(pstack)/ 栈空时不能出栈printf( 栈空，不能执行出栈操
9、作！ );return;proot = Pop(pstack);/ 执行出栈操作proot=proot-right;/ 指针指向右子void lnorderl(Pnode proot,Pstack pstack)/ 非递归中序遍历算法Initstack(pstack);/ 初始化栈while(proot|!lsempty(pstack)/ 循环结束条件if(proot)if(Isfull(pstack)printf( 栈满，不能执行入栈操作！ );return;Push(pstack,proot); 执行入栈操作proot = proot-left;/ 指针指向左子elseif(Isempty
10、(pstack)printf( 栈空，不能执行出栈操作！ );return ;proot = Pop(pstack);/ 出栈printf(%2c,proot-data);/ 打印数据proot=proot-right;/ 指针指向右子void PostorderI(Pnode proot,Pstack pstack)/ 非递归后续遍历算法int flagsMAX;/ 定义标志位栈int p =-1;/ 初始化标志位栈int flag;/ 存放标志位Initstack(pstack);/ 初始化栈 while(proot|!Isempty(pstack)/ 循环结束条件 if(proot)if
11、(Isfull(pstack)printf( 栈满，不能执行入栈操作！ );return ;flags+p = 0;/ 标志位置 0，并入栈Push(pstack,proot); 结点入栈 proot=proot-left;/ 指针指向左子elseproot = Pop(pstack);/ 指针出栈flag = flagsp-;/ 相应标志位出栈if(flag=0)/ 如果标志位为 0 表示右子还未访问过flag =1;/将标志位置 1，右子已访问flags+p = flag;/ 标志位入栈Push(pstack,proot); 结点入栈proot = proot-right;/ 指针指向右子
12、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,NULL,D);Inittnode(&E,NULL,NULL,E);Inittnode(&F,&G ,NULL,F);Inittnode(&G ,NULL,NULL,G); printf(
13、你定义的树的结构是： n);/* 一下是调用相应的函数输出遍历结果*/printf(A(B(D)C(E F(G)n);printf(= 下面是遍历结果 =n); printf(= 递归先序遍历： =n); PreorderR(&A);printf(n);printf(= 非递归先序遍历： =n); PreorderI(&A,&stack);printf(n);printf(= 递归中序遍历： =n); InorderR(&A);printf(n);printf(= 非递归中序遍历： =n); InorderI(&A,&stack);printf(n);printf(= 递归后序遍历： =n); PostorderR(&A);printf(n);printf(= 非递归后序遍历： =n); PostorderI(&A,&stack);printf(n);五、遇到的问题及解决办法 这部分我主要遇到如下两个问题，其内容和解决方法如下所列： 执行程序时程序停止运行，其
