二叉树递归非递归遍历.doc

文档介绍：西安邮电大学(计算机学院) 课内实验报告实验名称: 二叉树遍历专业名称: 通信工程班级: 通工 1309 学生姓名: 张睿学号( 8位): 03131304 指导教师: 季树滨实验日期: 2014 年 11月 17 日一. 实验目的及实验环境 1, 实验目的: 二叉树的遍历。 2, 实验环境: VC++ 二. 实验内容从键盘接受输入先序序列,一二叉链表作为存储结构,建立二叉树(以先序来建立) ,并对其进行遍历,然后将遍历结果打印输出。 typedef struct BiTNode { // 二叉树结点结构 char data; // 结点数据 struct BiTNode *lchild; // 左孩子 struct BiTNode *rchild; // 右孩子}BiTNode,*BiTree; typedef BiTree SElemType; typedef struct {// 栈结构定义 SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack *S); // 构造一个空栈 S Status DestroyStack(SqStack *S); // 销毁栈 S,S 不再存在 Status ClearStack(SqStack *S); // 把栈 S 置为空栈 Status StackEmpty(SqStack S); // 若栈 S 为空栈,则返回 TRUE ,否则返回 FALSE int StackLength(SqStack S); // 返回 S 元素的个数,即栈的长度 Status GetTop(SqStack S,SElemType *e); // 若栈不为空,则用 e 返回 S 的栈顶元素,并返回 OK ;否则返回 FALSE Status Push(SqStack *S,SElemType e); // 插入元素 e 为新的栈顶元素 Status Pop(SqStack *S,SElemType *e); // 若栈 S 不为空,则删除 S 的栈顶元素,用 e 返回其值,并返回 OK, 否则返回 ERROR Status StackTraverse(const SqStack *S); // 从栈底到栈顶依次对每个元素进行访问 BiTree CreateBiTree(BiTree T); // 按先后次序输入二叉树中结点的值(一个字符) ,空格表示空树// 构造二叉链表表示的二叉树 T Status PreOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构, Visit 是对数据元素操作的应用函数// 先序遍历二叉树 T 的递归算法,对每个数据元素调用函数 Visit Status InOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构, Visit 是对数据元素操作的应用函数// 中序遍历二叉树 T 的递归算法,对每个数据元素调用函数 Visit Status PostOrderRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构, Visit 是对数据元素操作的应用函数// 后序遍历二叉树 T 的递归算法,对每个数据元素调用函数 Visit Status PreOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构, Visit 是对数据元素操作的应用函数// 先序遍历二叉树 T 的非递归算法,对每个数据元素调用函数 Visit Status InOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构, Visit 是对数据元素操作的应用函数// 中序遍历二叉树 T 的非递归算法,对每个数据元素调用函数 Visit Status PostOrderNonRecursionTraverse(BiTree T,Status (*Visit)(ElemType e)); // 采用二叉链表存储结结构, Visit 是对数据元素操作的应用函数// 后序遍历二叉树 T 的非递归算法,对每个数据元素调用函数 Visit Status Visit(ElemType e); // 对二叉树中的数据元素访