数据结构实验报告：递归和非递归遍历二叉树.doc

实 验 报 告 课程名称： 数据结构 实验名称：递归和非递归遍历二叉树 任课教师： 专业： 计网类 班 级: 2007级1班 学号： 姓名： 完成日期：2008年12月10日一、实验目的：掌握二叉树的如下内容：二叉树的二叉链表存储方式、结点结构和类型定义；二叉树上的建立、遍历运算及应用。二、主要实验内容及要求：使用VC+语言编写程序：（1）实现二叉树的二叉链表存储方式和数据类型。（2）编写程序实现二叉树上的建立和遍历算法，编译运行程序。（3）编写程序实现基于二叉树的一个应用实例，编译运行程序。（试编写算法，求二叉树上叶子结点的数量，分别采用递归和非递归的方式。二叉树用二叉链表存贮。）三、程序说明：(算法设计思路)第1个程序：首先构造二叉树链表的存储结构，然后定义CreateTree(BiTree &T)函数用于创建二叉树，并按先序次序输入二叉树结点的值，如果想停止输入某节点的值，则输入#。通过Visit(BiTree p)函数来访问节点值。通过outputTree(BiTree pbnode,int totalSpace)输出二叉树结构图。通过main()函数来调用这些方法。第2个程序：首先构造二叉树链表的存储结构和栈的顺序存储表示，然后定义CreateTree(BiTree &T)函数用于创建二叉树，并按先序次序输入二叉树结点的值，如果想停止输入某节点的值，则输入#。再定义下列函数：StackEmpty(SqStack &S)（判断S是否是空栈）、Push(SqStack & S,BiTree p)（将P压入栈S）、Pop(SqStack &S,BiTree &p)（退栈）、CountLeaf(BiTree &T,int Count) （先序递推遍历二叉树的递推算法求叶子节点数）、InOrderTraverAndCountLeaf(BiTree &T) (非递推遍历二叉树求叶子节点数) 先按先序顺序从根节点开始将节点压入栈，若为空节点则不压入栈，P退栈，输出其节点值，如此循环，一直到遍历完为止，在此期间，如果遇到某节点左右孩子均为空，则计为一个叶子节点数。 通过outputTree( )输出二叉树结构图。以上方法通过main()实现。具体步骤看源程序代码。四、实验结果与结论：（经调试正确的源程序和程序的运行结果）1：实现二叉树上的建立和遍历算法编程员：lghgxu程序源代码：#include stdio.h# include stdlib.h# define OVERFLOW -2# define STACK_INIT_SIZE 100# define STACKINCREMENT 10typedef struct BiTNode/二叉树链表的存储结构 char data; struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;/创建二叉树，并按先序次序输入二叉树结点的值。void CreateTree(BiTree &T) char ch;scanf(%c,&ch);if(ch=#) T=NULL;else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);/存储分配失败 T-data=ch; printf(请输入 %c 的左子树 ,否则输入#n,T-data); CreateTree(T-lchild); printf(请输入 %c 的右子树 ,否则输入#n,T-data); CreateTree(T-rchild);/else / CreateTree/访问二叉树节点Visit(BiTree p) if(p) printf( %c ,p-data); return true;/if else return false;/Visit/先序遍历二叉树的递推算法 PreOrderTraverse(BiTree &T) if(T) if(Visit(T) if(PreOrderTraverse(T-lchild) if(PreOrderTraverse(T-rchild) return true; return false; /if else return true; void outputTree(BiTree pbnode,int totalSpace)/*输出二叉树*/ if(pbnode!=NULL)totalSpace+=8;/*右子树与根节点相距8个空格*/ outputTree(pbnode-rchild,totalSpace); for(int i=0;idata); outputTree(pbnode-lchild,totalSpace);/*递归调用左子树*/ void main()/主函数 BiTree t; int totalSpace=0; printf(如果创建一棵树，请输入根节点数据,否则输入#n); CreateTree(t); printf(二叉树的结构图如下：n); printf(左边第一个节点是二叉树的根节点nn); printf(其上方是右子树，下方是左子树nn); outputTree(t,totalSpace); printf(先序遍历二叉树的结果如下：n); PreOrderTraverse(t); printf(n恭喜你，遍历成功!：n);2：应用实例 递推和非递推法求二叉树叶子结点数编程员：lghgxu程序源代码：#include stdio.h# include stdlib.h# define OVERFLOW -2# define STACK_INIT_SIZE 100# define STACKINCREMENT 10/二叉树链表的存储结构typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;/栈的顺序存储表示 typedef struct BiTNode *base; /栈底指针 BiTNode *top; /栈顶指针 int stacksize; /当前已分配的存储空间 SqStack; /建立一个空栈 void InitStack(SqStack &S) S.base=(BiTree)malloc(STACK_INIT_SIZE * sizeof(BiTNode); if(!S.base) exit(OVERFLOW );/存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; /InitStack /压入栈 void Push(SqStack & S,BiTree p) if(S.top-S.base=S.stacksize)/满栈，追加存储结构 S.base= (BiTree)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(BiTNode); if(!S.base) exit(OVERFLOW );/存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; /if *(+S.top)=*p; /Push /退出栈 Pop(SqStack &S,BiTree &p) if( S.top=S.base) printf(空栈n); return false; p=(BiTree)malloc( sizeof(BiTNode); *p=*S.top; -S.top; return true; /Pop /判断是否是空栈 StackEmpty(SqStack &S) if( S.top=S.base) return true; else return false ; /创建二叉树void CreateTree(BiTree &T) char ch;scanf(%s,&ch);if(ch=#) T=NULL;else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);/存储分配失败 T-data=ch; printf(请输入 %c 的左子树 ,否则输入#n,T-data); CreateTree(T-lchild); printf(请输入 %c 的右子树 ,否则输入#n,T-data); CreateTree(T-rchild);/else / CreateTree/访问二叉树节点字符Visit(BiTree p) if(p) printf( %c ,p-data); return true; else return false;/Visit/先序递推遍历二叉树的递推算法求叶子节点数int CountLeaf(BiTree &T,int Count) int count=Count;/Count记录叶子节点数if(!T) return count;else count=CountLeaf(T-lchild,count);count=CountLeaf(T-rchild,count); if(!(T-lchild)&!(T-rchild) return (+count); return count; /if/非递推遍历二叉树int InOrderTraverAndCountLeaf(BiTree &T) int j=0,count=0;BiTree p;p=(BiTNode *)malloc( sizeof(BiTNode);/关键一步p=T; SqStack s;InitStack(s);while(p|!StackEmpty(s) if(p) Push(s,p);/如果p为非空，将p压入栈 if(!(p-lchild)&!(p-rchild) +count;/记录叶子节点数 p=p-lchild;/if else Pop(s,p);/如果p为空，则p退栈 Visit(p); p=p-rchild; /else/while return count;/InOrderTravervoid outputTree(BiTree pbnode,int totalSpace)/*输出二叉树*/ if(pbnode!=NULL) totalSpace+=8;/*右子树与根节点相距8个空格*/ outputTree(pbnode-rchild,totalSpace); for(int i=0;idata); outputTree(pbnode-lchild,totalSpace);/*递归调用左子树*/ /主函数void main() BiTree t; int totalSpace=0,count1=0,count2=0; printf(如果创建一棵树，请输入根节点数据,否则输入#n); CreateTree(t); printf(二叉树的结构图如下:n); printf(左边第一个节点是二叉树的根节点nn); printf(其上方是右子树，下方是左子树nn); outputTre