武汉理工数据结构实验3 二叉树创建和遍历.doc

实验3 二叉树创建、遍历操作与应用 1实验目的 掌握使用先序方式创建二叉树； 掌握使用递归的方式对二叉树进行先序、中序和后序遍历操作； 掌握层次遍历； 二叉树的具体应用，如计算叶子结点个数，计算二叉树的深度。 2实验内容 以先序方式创建二叉链表存储结构的二叉树； 对二叉树进行先序、中序和后序遍历操作； 层次遍历二叉树。 求二叉树的深度以及叶子结点个数； 【测试数据】自定 3实验结果 按照学校实验格式要求撰写实验报告，内容主要包括1）实验目的；2）实验内容；3）实验环境和方法；4）实验过程描述；5）实验心得体会 参考程序如下： 实验内容（1）（2）（3）的参考程序 /* biTree.h 文件 */ typedef char TElemType; typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; enum Status { ERROR = 0, OK = 1, OVERFLOW = 2 }; /* biTreeOp.h 文件 */ #include biTree.h //按先序次序输入二叉树中结点中的值，以链式存储 Status CreateBiTree(BiTree T); //对链式存储的二叉树先序遍历 Status PreOrderTraverse(BiTree T); //对链式存储的二叉树中序遍历 Status InOrderTraverse(BiTree T); //对链式存储的二叉树后序遍历 Status PostOrderTraverse(BiTree T); //对链式存储的二叉树层序遍历 Status LevelOrderTraverse(BiTree T); //对链式存储的二叉树非递归的中序遍历 Status Inorder_fdg(BiTree T); //对链式存储的二叉树先序遍历 Status FreeBiTree(BiTree T); /* biTreeOp.cpp 文件 */ #include stdio.h #include stdlib.h #include biTreeOp.h //#include sqQueueOp.h //按先序次序输入二叉树中结点中的值，以链式存储 Status CreateBiTree(BiTree T){ char ch; scanf(%c,ch); if( # == ch ) T = NULL; else { if(!(T = (BiTNode *) malloc(sizeof(BiTNode)))) exit(OVERFLOW); T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); } return OK; } //对链式存储的二叉树先序遍历 Status PreOrderTraverse(BiTree p){ if ( p!= NULL ) { printf(%c ,p-data); PreOrderTraverse(p-lchild); PreOrderTraverse(p-rchild); return OK; } else return OK; }//PreOrderTraverse //对链式存储的二叉树中序遍历 Status InOrderTraverse(BiTree p){ if ( p!= NULL ) { InOrderTraverse(p-lchild); printf(%c ,p-data); InOrderTraverse(p-rchild); return OK; } else return OK; }//InOrderTraverse //对链式存储的二叉树后序遍历 Status PostOrderTraverse(BiTree p){ if ( p!= NULL ) { PostOrderTraverse(p-lchild); PostOrderTraverse(p-rchild); printf(%c ,p-data); return OK; } else return OK; }//PostOrderTraverse //对链式存储的二叉树层序遍历 //需要使用队列进行辅助 Status LevelOrderTr