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

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

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

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

3、ntf("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);PreOrder(T->lchild,Visit);PreOrder(T->rchild,Visit);

4、}}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->lchild,Visit);PostOrder(T->rchild,Visit);Visit(T->data);}Word文档.}intmain()

5、{intchoice;BiTreeroot;printf("下面建立一棵二叉树，结点数据输入按先序次序。");printf("输入数据请注意，每一个非空结点的所有孩子数据都要给出");printf("若孩子为空，请用空格符表示。");printf("请输入二叉树结点的数据，这里设定为字符:");CreatBiTree(root);printf("================================");printf("1：先序序列：");printf("2：中序序列：");printf("3：后序序列：");printf("其它值则

6、退出：");printf("================================");do{printf("请输入对应的操作码：");scanf("%d",&choice);switch(choice){case1:printf("先序序列为：");PreOrder(root,PrintData);printf("");break;case2:printf("中序序列为：");InOrder(root,PrintData);printf("");break;case3:printf("后序序列为：");PostOrder(root,Pr

7、intData);printf("");}}while(choice>0&&choice<4);return0;}（2）运行结果：Word文档.（3）运行结果分析：运用遍历方法实现二叉树的建立任务二：完成下列程序，该程序以二叉链表作存储结构，构建如图2所示二叉树，计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数。图2解答：（1）源代码：#include#include#defineOK1#defineERROR0typedefcharTE