《实验三二叉树的基本运算.doc》由会员分享，可在线阅读，更多相关《实验三二叉树的基本运算.doc（19页珍藏版）》请在金锄头文库上搜索。
1、中原工学院 数据结构实验报告软件 111-臧丽实验三 二叉树的基本运算一、实验目的与实验内容1.实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。2.实验内容建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做）二、程序设计1.总体设计int n=0; /全局变量typedef struct BiTNode /二叉树节点定义char
2、data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void CreateBiTree(BiTree &T); /创建二叉树int Visit(char e); /打印函数int PreOrderTraverse(BiTree T); /先序遍历二叉树int InOrderTraverse(BiTree T); / 中序遍历二叉树 int PostOrderTraverse(BiTree T); / 后序遍历二叉树void LevelOrderTraverse(BiTree T); /层次遍历二叉树int Nodesum(BiTree &T)
3、; /二叉树节点总数int BiTreeDepth(BiTree T ); / 返回二叉树的深度void LeafCount(BiTree T); /统计叶子数并输出叶子结点typedef struct QNode /队列节点定义BiTree bt;struct QNode *next;QNode,*QueuePtr; struct LinkQueue /队列类型定义QueuePtr front; /队头指针QueuePtr rear; /队尾指针;void InitQueue(LinkQueue &Q); / 构造一个空队列 Q int EmptyQueue(LinkQueue &Q); /
4、判断队列是否空void EnQueue(LinkQueue &Q,BiTree &e );/ 进队void DeQueue(LinkQueue &Q,BiTree &e );/出队void DestroyQueue(LinkQueue *Q); /销毁队列2详细设计l void CreateBiTree(BiTree &T)函数是用来先序建立二叉树ch= if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=ch;CreateBiTree(T-lchild); CreateBiTree(T-rchild);T=NULL;图表 1l void
5、 LevelOrderTraverse(BiTree T)是用来层次遍历二叉树。在函数中，开辟一个树结点指针数组，用来存放遍历到的元素地址，且使B0=T，用来存放树根if(Bi-lchild)Bj=Bi-lchild;j+; if(Bi-rchild) Bj=Bi-rchild;j+; i+ilchild); h2=BiTreeDepth(T-rchild);if(h1h2)return h1+1;elsereturn h2+1;return 0图表 33，调试及问题解决二叉树涉及到队列的基本操作，还需要先序，中序遍历，后序遍历，层次遍历，涉及的到的知识面广，需要了解各个方面，还要对二叉树的逻
6、辑结构进行详细的了解并掌握。初步完编程的工作时，在输入二叉树的发现只能输入一个字符，而且程序不再进行，最后是自己的不小心将语句char a; scanf(%c,&a);中的%c写为%d导致的。在编写元素入栈和出栈的时候，程序报如下的错误：语法有错误。，经过检查原来是定义的时候的类型使用错/测试代码int main()printf(*1.先序建立一个二叉树*n);printf(*2.先序遍历二叉树 *n);printf(*3.中序遍历二叉树 *n);printf(*4.后序遍历二叉树 *n);printf(*5.层次遍历二叉树 *n);printf(*6.二叉树总结点数 *n);printf(*
7、7.二叉树深度 *n);printf(*8.统计叶子数并输出叶子结点*n);printf(*其他键退出 *n);printf(*请选择你的功能 *n);int a;BiTree T;while(1)scanf(%d,&a);switch(a)case 1:scanf(%c,&a);CreateBiTree (T);break; case 2:printf(先序遍历二叉树:);PreOrderTraverse (T);break;case 3:printf(中序遍历二叉树:);InOrderTraverse (T);break;case 4:printf(后序遍历二叉树:);PostOrderT
8、raverse (T);break;case 5:printf(层次遍历二叉树:);LevelOrderTraverse(T);break; case 6:printf(二叉树的总结点:);Nodesum(T);printf(%dn,n);break;case 7:printf(二叉树的深度:);printf(%dn,BiTreeDepth(T);break;case 8:printf(二叉树的叶子节点:);LeafCount(T); printf(n);default:exit(0);return 0;运行时会出现窗口如图表四图表 4当选择1来建立二叉树，输入如：abcdegf（其中表示空格
9、字符），就此建立一个二叉树，当一次输入2,3,4,5时，对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；运行如图表5所示图表 5在上面的基础上，依次输入6,7,8时，出现图表6，二叉树的深度，结点数目，叶结点数目依次显示出来图表 6三源代码#include#include#includehead.hvoid CreateBiTree(BiTree &T) /先序建立二叉树char ch;scanf(%c,&ch);if (ch= ) T=NULL; else if (!(T=(BiTNode *)malloc(sizeof(BiTNode)exit(1);T-dat
10、a=ch;CreateBiTree(T-lchild); CreateBiTree(T-rchild); int Visit(char e)printf(%c ,e);return 0;int PreOrderTraverse(BiTree T)/先序遍历二叉树if(T) printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); return 0;int InOrderTraverse(BiTree T) / 中序遍历二叉树 if(T)InOrderTraverse(T-lchild);printf(%c,
11、T-data); InOrderTraverse(T-rchild); return 0; int PostOrderTraverse(BiTree T) /后序遍历二叉树if(T) PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(%c,T-data); return 0;void LevelOrderTraverse(BiTree T)/层次遍历二叉树BiTNode *B100;/树结点指针数组，用于存放遍历到的元素地址if(T=NULL)printf(空的二叉树n);B0=T; /存入树根int i;int j=1; /j为总结点for(i=0;ilchild) /如果有左孩子，存入地址，j加1 Bj=Bi-lchild;j+; if(Bi-rchild) /如果有右孩子，存入地址，j加1 Bj=Bi-rchild;j+; for(i=0;idata);int Nodesum(BiTree &T)
