二叉树实验报告

1、二叉树的创建与遍历一、试验内容 根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后 序遍历序列。二、运行环境Visual C+三、需求分析1、建立一棵用二叉链表方式存储的二叉树。2、从键盘接受扩展先序序列，以二叉链表作为存储结构。3、建立二叉树，并将遍历结果打印输出。采用递归和非递归两种 方法实现。四、设计概要/二叉树的二叉链表存储表示typedef struct BiTBodeTElemType data;Struct BiTNode *lchild, *rchild /左右孩子指针BiTNode, *BiTree;/基本操作的函数原型说明Status CreateBiTree(B

2、iTree &T); /按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树。/构造二叉树链表表示的二叉树 T。Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e);采用二叉链表存储结构，visit是对结点操作的应用函数。先序遍历二叉树T,对每个结点调用函数visit一次且仅以次。一旦visit ()失败，则操作失败。Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e);采用二叉链表存储结构，visit是对结点操作的应用函数。后序遍历二叉树T,对

3、每个结点调用函数visit一次且仅以次。一旦visit ()失败，则操作失败。先序遍历二叉树基本操作的递归算法Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)采用二叉链表存储结构，visit是对数据元素操作的应用函数，/先序遍历二叉树 T 的递归算法，对每个数据元素调用函数 visit。/最简单的 visit 函数是：/ Status PrintElement(TElemType e) /输出元素 e 的值/ printf(e);/实用时，加上格式窜/ return OK;/ 调用实例：PreOrderTraverse(T

4、,PrintElement); if(T) if (visit(T-data)if(PreOrderTraverse(T-lchild,visit) if(PreOrderTraverse(T-rchild,visit) return OK;return ERROR;else return OK; /PreOrderTraverse五、源程序代码#include#includetypedef struct BiTNode char data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;void CreatBiTree(BiTree &T) /

5、 先序创建二叉树 char ch;if(ch=getchar()=n) T=NULL;else T=(BiTNode*)malloc(sizeof(BiTNode); if(!T) exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);void PreTravel(BiTree &T) / 先序遍历 if(T)printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);void PostTravel(BiTree &T) / 后序遍历if(T)PostTravel(T-lchild);PostTravel(T-rchild); printf(%c,T-data);void main() BiTree T;printf(请输入字符串:n);CreatBiTree(T);printf (“先序遍历序列:n);PreTravel(T);printf(n);printf (“后序遍历序列:n);Po