二叉树的基本操作和其应用.doc

广西工学院计算机学院 《数据结构》课程实验报告书 实验六 二叉树的基本操作及其应用 学生姓名： 学 号： 班级： 指导老师： 专 业：计算机学院软件学院 提交日期：2013年6月22日 实验目的 1） 了解二叉树的特点、掌握二叉树的主要存储结构。 2） 掌握二叉树的基本操作，能针对二叉树的具体应用选择相应的存储结构。 3） 掌握递归算法的设计方法。 2.实验内容 （1）二叉链表表示二叉树#includestdio.h #includestdlib.h #include conio.h #includemalloc.h//各头文件 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char TElemType;//定义宏参 //二叉树链表的类型定义 typedef struct BiTNode { TElemType data;//二叉树元素元素类型定义 struct BiTNode *lchild,*rchild;//定义左右孩子指针 }BiTNode,*BinTree; typedef BinTree ElemType;//队列元素类型定义 //定义链式队列类型 typedef struct QNode { ElemType data;//元素类型定义 struct QNode *next;//指向下个结点 }QNode,*QueuePtr; ////队列指针定义 typedef struct { QueuePtr front;//队列头指针 QueuePtr rear;//队列尾指针 }QUEUE; //先序建立二叉树 void CreateBinTree(BinTree T) {//初始条件:二叉树不存在 //操作结果：建立一棵二叉树，二叉链表的数据域类型待定 TElemType ch; scanf(%c,ch); if(ch== ) T=NULL; else { T=(BinTree)malloc(sizeof(BiTNode));//建立头结点 if(!T) exit(0); T-data=ch; CreateBinTree(T-lchild); CreateBinTree(T-rchild); } return; } //清空二叉树 void ClearBinTree(BinTree T) {//初始条件:二叉树已存在 //操作结果：将链表都赋值为空 if(T) { T-data= ;//赋域空值 ClearBinTree(T-lchild); ClearBinTree(T-rchild); } return; } //判断空二叉树 int BinTreeEmpty(BinTree T) {//初始条件:二叉树已存在 //操作结果:若空返回值1，反之返回0 if(!T) return 1; else return 0; } //先序遍历二叉树 void PreorderTraverse(BinTree T) {//初始条件:二叉树已存在 //操作结果：先序递归遍历T if(T) { printf(%c,T-data); PreorderTraverse(T-lchild); PreorderTraverse(T-rchild); } return; } //中序遍历二叉树 void InorderTraverse(BinTree T) {//初始条件:二叉树已存在 //操作结果:中序递归遍历T if(T) { InorderTraverse(T-lchild); printf(%c,T-data); InorderTraverse(T-rchild); } return; } //后序遍历二叉树 void PostorderTraverse(BinTree T) {//初始条件:二叉树已存在 //操作结果:后序递归遍历T if(T) { PostorderTraverse(T-lchild); PostorderTraverse(T-rchild); printf(%c,T-data); } return; } //初始化链式队列 void InitQueue(QUEUE *q) {//初始条件:队列不存在