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

实报 告 实验名称：任课教师：：名：完成日期： 二、主要实验内容及要求：使用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 10 typedef 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(