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

《实验三 二叉树的操作及应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三二叉树的操作及应用实验课程名：数据结构与算法成绩:专业班级：15计科1班学号：201540410109姓名：刘江实验时间：2016.10.24-10.31实验地点：K4-102指导教师：冯珊一、实验目的及要求1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。二、实验内容任务一：完成下列程序，该程序以二叉链表作存储结构，构建如图1所示的二叉树，并依次进行二叉树的前序、中序、后序及层次遍历。图1解答：（1）源代码：#include

2、.h>#include#defineOK1#defineERROR0typedefcharDataType;/*二叉树节点的存储类型*/typedefstructNode//definestrictureBiTree{DataTypedata;structNode*lchild,*rchild;}Node,*BiTree;/*按先序序列建立一棵二叉树*/BiTreeCreatBiTree(BiTree&T){DataTypech;scanf("%c",&ch);if(ch==''){T=NULL;}else9{if(!(

3、T=(Node*)malloc(sizeof(Node)))){printf("Overflow.");exit(0);}T->data=ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}returnT;}voidPrintData(DataTypex){printf("%c",x);}voidPreOrder(BiTreeT,void(*Visit)(DataTypeitem))/*前序遍历二叉树T，访问操作为Visit()函数*/{if(T!=NULL){Visit(T->data)

4、;PreOrder(T->lchild,Visit);PreOrder(T->rchild,Visit);}}voidInOrder(BiTreeT,void(*Visit)(DataTypeitem))/*中序t*/{if(T!=NULL){InOrder(T->lchild,Visit);Visit(T->data);InOrder(T->rchild,Visit);}}voidPostOrder(BiTreeT,void(*Visit)(DataTypeitem))/*后序*/{if(T!=NULL){PostOrder(T->lch

5、ild,Visit);PostOrder(T->rchild,Visit);Visit(T->data);}}9intmain(){intchoice;BiTreeroot;printf("下面建立一棵二叉树，结点数据输入按先序次序。");printf("输入数据请注意，每一个非空结点的所有孩子数据都要给出");printf("若孩子为空，请用空格符表示。");printf("请输入二叉树结点的数据，这里设定为字符:");CreatBiTree(root);printf("==========================

6、======");printf("1：先序序列：");printf("2：中序序列：");printf("3：后序序列：");printf("其它值则退出：");printf("================================");do{printf("请输入对应的操作码：");scanf("%d",&choice);switch(choice){case1:printf("先序序列为：");PreOrder(root,PrintData);printf("");break;case2:pri

7、ntf("中序序列为：");InOrder(root,PrintData);printf("");break;case3:printf("后序序列为：");PostOrder(root,PrintData);printf("");}}while(choice>0&&choice<4);return0;}（2）运行结果：9（3）运行结果分析：运用遍历方法实现二叉树的建立任务二：完成下列程序，该程序以二叉链表作存储结构，构建如图2所示二叉树，计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数。图2解答：（1

8、）源代码：#include#include#defineOK1#defineERROR0typedefcharTElemType;9/*二叉