实验三 二叉树的操作及应用.doc

实验三 二叉树的操作及应用实验课程名： 数据结构与算法成绩:专业班级： 15计科1班 学号： 201540410109 姓名： 刘江 实验时间： 2016.10.24-10.31 实验地点： K4-102 指导教师： 冯珊 一、实验目的及要求1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。二、实验内容任务一：完成下列程序，该程序以二叉链表作存储结构，构建如图1所示的二叉树，并依次进行二叉树的前序、中序、后序及层次遍历。图1解答：（1）源代码：#include#include#define OK 1#define ERROR 0typedef char DataType;/* 二叉树节点的存储类型 */typedef struct Node/define stricture BiTree DataType data; struct Node *lchild,*rchild;Node, *BiTree;/*按先序序列建立一棵二叉树*/BiTree CreatBiTree(BiTree &T)DataType ch;scanf(%c,&ch);if(ch= ) T=NULL;elseif(!(T=(Node*)malloc(sizeof(Node)printf(Overflow.n);exit(0);T-data =ch;CreatBiTree(T-lchild );CreatBiTree(T-rchild );return T;void PrintData(DataType x)printf(%c,x);void PreOrder(BiTree T, void (*Visit)( DataType item)/*前序遍历二叉树T，访问操作为Visit()函数*/if(T!= NULL)Visit(T-data);PreOrder(T-lchild, Visit);PreOrder(T-rchild, Visit);void InOrder(BiTree T, void (*Visit)( DataType item) /*中序t */if(T!= NULL)InOrder(T-lchild, Visit);Visit(T-data);InOrder(T-rchild, Visit); void PostOrder(BiTree T, void (*Visit)( DataType item) /*后序 */if(T!= NULL)PostOrder(T-lchild, Visit);PostOrder(T-rchild, Visit);Visit(T-data);int main()int choice;BiTree root;printf(下面建立一棵二叉树，结点数据输入按先序次序。n);printf(输入数据请注意，每一个非空结点的所有孩子数据都要给出n);printf(若孩子为空，请用空格符表示。n);printf(请输入二叉树结点的数据，这里设定为字符:n);CreatBiTree(root);printf(=n);printf(1：先序序列：n);printf(2：中序序列：n);printf(3：后序序列：n);printf(其它值则退出：n);printf(=n);doprintf(请输入对应的操作码：);scanf(%d,&choice);switch(choice)case 1:printf(n先序序列为：); PreOrder(root,PrintData);printf(n);break;case 2:printf(n中序序列为：); InOrder(root,PrintData);printf(n);break;case 3:printf(n后序序列为：); PostOrder(root,PrintData);printf(n);while(choice0&choice4); return 0;（2） 运行结果： （3）运行结果分析： 运用遍历方法实现二叉树的建立任务二：完成下列程序，该程序以二叉链表作存储结构，构建如图2所示二叉树，计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数。图2解答：（1）源代码：#include#include#define OK 1#define ERROR 0typedef char TElemType;/* 二叉树节点的存储类型 */typedef struct BiTNode/define stricture BiTree TElemType data; struct BiTNode *lchild,*rchild;BiTNode, *BiTree;/*按先序序列建立一棵二叉树*/void CreatBiTree(BiTree &T)TElemType ch;scanf(%c,&ch);if(ch= ) T=NULL;return;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)printf(Overflow.n);exit(0);(T)-data =ch;CreatBiTree(T-lchild );CreatBiTree(T-rchild );void PrintData(TElemType x)printf(%c,x);void PreOrder(BiTree T, void (*Visit)( TElemType item)/*前序遍历二叉树T，访问操作为Visit()函数*/if(T!= NULL)Visit(T-data);PreOrder(T-lchild, Visit);PreOrder(T-rchild, Visit);void InOrder(BiTree T, void (*Visit)( TElemType item) /*中序t */if(T!= NULL)InOrder(T-lchild, Visit);Visit(T-data);InOrder(T-rchild, Visit); void PostOrder(BiTree T, void (*Visit)( TElemType item) /*后序 */if(T!= NULL)PostOrder(T-lchild, Visit);PostOrder(T-rchild, Visit);Visit(T-data);/以上代码与任务一的完全相同，下面是完成任务二的代码/注意这些函数算法的相似性int BTreeDepth(BiTree BT) int leftdep,rightdep; if (BT=NULL) return(0); else leftdep=BTreeDepth(BT-lchild); rightdep=BTreeDepth(BT-rchild); if (leftdeprightdep) return(leftdep+1); else return(rightdep+1); int NodeCount(BiTree BT) if (BT=NULL) return(0); else return(NodeCount (BT- lchild)+ NodeCount (BT- rchild)+1); int LeafCount(BiTree BT) if (BT=NULL) return(0); else if (BT- lchild =NULL & BT- rchild =NULL) return(1); else return(LeafCount (BT- lchild)+ LeafCount (BT- rchild); int NotLeafCount(BiTree BT) if (BT=NULL) return(0); else if (BT- lchild =NULL & BT- rchild =NULL) return(0); else return(NotLeafCount (BT- lchild)+ NotLeafCount (BT- rchild)+1); int OneChildCount(BiTree BT) if (BT=NULL) return(0); else if (BT- lchild =NULL & BT- rchild!=NULL) |(BT- lchild!=NULL & BT- rchild =NULL) return(OneChildCount (BT- lchild)+ OneChildCount (BT- rchild)+1); else return(OneChildCount (BT- lchild)+ OneChildCount (BT- rchild); int TwoChildCount(BiTree BT) if (BT=NULL) return(0); else if (BT- lchild =NULL | BT- rchild =NULL) return(TwoChildCount (BT- lchild)+ TwoChildCount (BT- rchild); else if (BT- lchild!=NULL & BT- rchild!=NULL) return(TwoChildCount (BT- lchild)+ TwoChildCount (BT- rchild)+1);/主函数在任务一的基础上进行适当的增添int main()int choice;BiTree root;printf(下面建立一棵二叉树，结点数据输入按先序次序。n);printf(输入数据请注意，每一个非空结点的所有孩子数据都要给出n);printf(若孩子为空，请用空格符表示。n);printf(请输入二叉树结点的数据，这里设定为字符:n);CreatBiTree(root);printf(=n);printf(1：先序序列：n);printf(2：中序序列：n);printf(3：后序序列：n);printf(4：二叉树的深（高）度：n);printf(5：二叉树的结点数：n);printf(6：二叉树的叶子结点数：n);printf(7：二叉树的度为2的结点数：n);printf(8：二叉树的度为1的结点数：n);printf(其它值则退出：n);printf(=n);doprintf(请输入对应的操作码：);scanf(%d,&choice);switch(choice)case 1:printf(n先序序列为：); PreOrder(root,PrintData);printf(n);break;case 2:printf(n中序序列为：); InOrder(root,PrintData);printf(n);break;case 3:printf(n后序序列为：); PostOrder(root,PrintData);printf(n);break;case 4:printf(二叉树的深度是：%dn,BTreeDepth(root);break;case 5:printf(二叉树的结点数是：%dn,NodeCount(root);break;case 6:printf(二叉树的叶子数是：%dn,LeafCount(root);break;case 7:pri