《二叉树的基本操作及其应用》由会员分享，可在线阅读，更多相关《二叉树的基本操作及其应用（25页珍藏版）》请在金锄头文库上搜索。
1、广西工学院计算机学院广西工学院计算机学院数数据据结结构构课课程程实实验验报报告告书书实验六实验六 二叉树的基本操作及其应用二叉树的基本操作及其应用学生姓名：学生姓名：学学 号：号：班级：班级：指导老师：指导老师：专专 业：业：计算机学院软件学院计算机学院软件学院提交日期：2013 年 6 月 22 日- 1 -1 1实验目的实验目的1） 了解二叉树的特点、掌握二叉树的主要存储结构。2） 掌握二叉树的基本操作，能针对二叉树的具体应用选择相应的存储结构。3） 掌握递归算法的设计方法。 2.2.实验内容实验内容（1 1）二叉链表表示二叉树，建立一棵二叉树，实现下列基本操作）二叉链表表示二叉树，建立一
2、棵二叉树，实现下列基本操作, ,通过数据测试每通过数据测试每个操作的正确性，包括：个操作的正确性，包括：1. CreateBinTree(/定义宏参定义宏参/二叉树链表的类型定义二叉树链表的类型定义typedef struct BiTNodeTElemType data;/二叉树元素元素类型定义二叉树元素元素类型定义struct BiTNode *lchild,*rchild;/定义左右孩子指针定义左右孩子指针BiTNode,*BinTree;typedef BinTree ElemType;/队列元素类型定义队列元素类型定义/定义链式队列类型定义链式队列类型typedef struct QN
3、odeElemType data;/元素类型定义元素类型定义struct QNode *next;/指向下个结点指向下个结点QNode,*QueuePtr;- 3 -/队列指针定义队列指针定义typedef struct QueuePtr front;/队列头指针队列头指针QueuePtr rear;/队列尾指针队列尾指针QUEUE;/先序建立二叉树先序建立二叉树void CreateBinTree(BinTree scanf(“%c“,if(ch= )T=NULL;elseT=(BinTree)malloc(sizeof(BiTNode);/建立头结点建立头结点if(!T)exit(0);T
4、-data=ch;CreateBinTree(T-lchild);CreateBinTree(T-rchild);return;- 4 -/清空二叉树清空二叉树void ClearBinTree(BinTree /赋域空值赋域空值ClearBinTree(T-lchild);ClearBinTree(T-rchild);return;/判断空二叉树判断空二叉树int BinTreeEmpty(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果操作结果:若空返回值若空返回值 1，反之返回，反之返回 0if(!T)return 1;elsereturn 0;/先序遍历二叉树
5、先序遍历二叉树void PreorderTraverse(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果：先序递归遍历操作结果：先序递归遍历 Tif(T)- 5 -printf(“%c“,T-data);PreorderTraverse(T-lchild);PreorderTraverse(T-rchild);return;/中序遍历二叉树中序遍历二叉树void InorderTraverse(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果操作结果:中序递归遍历中序递归遍历 Tif(T)InorderTraverse(T-lchild);
6、printf(“%c“,T-data);InorderTraverse(T-rchild);return;/后序遍历二叉树后序遍历二叉树void PostorderTraverse(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果操作结果:后序递归遍历后序递归遍历 Tif(T)- 6 -PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(“%c“,T-data); return;/初始化链式队列初始化链式队列void InitQueue(QUEUE *q)/初始条件初始条件:队列不存在队列不存在
7、/操作结果：建立一个队列操作结果：建立一个队列q-front=q-rear=(QueuePtr)malloc(sizeof(QNode);/建立头尾结点建立头尾结点if(!(q-front)/头结点指向头结点指向 NULLexit(0);q-front-next=NULL;/销掉链式队列销掉链式队列void DestroyQueue(QUEUE *q)/初始条件初始条件:队列已存在队列已存在/操作结果：销掉链式队列操作结果：销掉链式队列while(q-front)/头结点还没指向头结点还没指向 NULLq-rear=q-front-next;free(q-front);q-front=q-re
8、ar;- 7 -/判断空队列判断空队列int QueueEmpTy(QUEUE q)/初始条件初始条件:队列已存在队列已存在/操作结果：若为空队列返回操作结果：若为空队列返回 1，否则返回，否则返回 0if(q.front=q.rear)/头指针等于尾指针头指针等于尾指针return 1;else return 0;/入队列入队列void EnQueue(QUEUE *q ,ElemType e)/初始条件初始条件:队列已存在队列已存在/操作结果：元素操作结果：元素 e 从队尾入队从队尾入队QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);/建立新结点建立
9、新结点 pif(!p)exit(0);p-data=e;p-next=NULL;q-rear-next=p;q-rear=p; /出队列出队列- 8 -void DeQueue(QUEUE *q,ElemType *e)/初始条件初始条件:队列已存在队列已存在/操作结果：元素操作结果：元素 e 从队头输出从队头输出QueuePtr p;if(q-rear!=q-front)/头指针不等于尾指针头指针不等于尾指针p=q-front-next;*e=p-data;q-front-next=p-next;if(q-rear=p)q-rear=q-front;free(p);/层次遍历二叉树层次遍历二
10、叉树void LevelTraverse(BinTree T) /初始条件初始条件:二叉树已存在二叉树已存在/操作结果操作结果:层次递归遍历层次递归遍历 TQUEUE q;BinTree a;if(T)InitQueue(/初始化链式队列初始化链式队列EnQueue(/入队列入队列while(!QueueEmpTy(q)DeQueue(/出队列出队列printf(“%c“,a-data);- 9 -if(a-lchild)/有左孩子有左孩子EnQueue(if(a-rchild )/有右孩子有右孩子EnQueue(return;/查找值为查找值为 e 的节点的节点BinTree value(B
11、inTree T, TElemType e)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果：返回二叉树操作结果：返回二叉树 T 中指向元素值为中指向元素值为 e 的结点的指针的结点的指针QUEUE q;BinTree a;if(T)InitQueue(/初始化链式队列初始化链式队列EnQueue(/入队列入队列while(!QueueEmpTy(q)DeQueue(/出队列出队列if(a-data =e)return a;if(a-lchild)/有左孩子有左孩子EnQueue(if(a-rchild )/有右孩子有右孩子EnQueue(- 10 -return NULL;/计算二叉树
12、的深度计算二叉树的深度int BinTreeDepth(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果操作结果:输出二叉树的深度输出二叉树的深度int i,j;if(!T)return 0;i= BinTreeDepth(T-lchild);j=BinTreeDepth(T-rchild);return i=j?i+1:j+1;/查找值为查找值为 e 的节点的双亲的节点的双亲BinTree Parent(BinTree T,TElemType e)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果操作结果:返回二叉树返回二叉树 T 中指向元素值为中指向元素值为
13、e 的结点的双亲的指针的结点的双亲的指针QUEUE q;BinTree a;if(T)InitQueue(/初始化链式队列初始化链式队列EnQueue(/入队列入队列- 11 -while(!QueueEmpTy(q)DeQueue(/出队列出队列if(a-lchildelseif(a-lchild)/有左孩子有左孩子EnQueue(if(a-rchild )/有右孩子有右孩子EnQueue(return NULL;/查找值为查找值为 e 的节点的左孩子的节点的左孩子BinTree Leftchild(BinTree T,TElemType e)/初始条件初始条件:二叉树已存在二叉树已存在/操
14、作结果：返回二叉树操作结果：返回二叉树 T 中指向元素值为中指向元素值为 e 的结点的左孩子的指针的结点的左孩子的指针BinTree p;p=value(T,e);if(p)if(p-lchild)return p-lchild;elsereturn NULL;return NULL;- 12 -/查找值为查找值为 e 的节点的右孩子的节点的右孩子BinTree Rightchild(BinTree T,TElemType e)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果：返回二叉树操作结果：返回二叉树 T 中指向元素值为中指向元素值为 e 的结点的右孩子的指针的结点的右孩子的指针B
15、inTree p;p=value(T,e);if(p)if(p-rchild)return p-rchild;elsereturn NULL;return NULL;/计算二叉树中节点的个数计算二叉树中节点的个数int CountNode(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果：输出二叉树中节点的个数操作结果：输出二叉树中节点的个数static int sum=0;if(NULL!=T)+sum;CountNode(T-lchild);CountNode(T-rchild);- 13 -return sum;/计算二叉树中叶子节点的个数计算二叉树中叶子节点的个数int Leaf(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果：输出二叉树中叶子节点的个数操作结果：输出二叉树中叶子节点的个数if(!T)return 0;if(!T-lchildreturn Leaf(T-lchild)+Leaf(T-rchild);/计算二叉树中度为计算二叉树中度为 1 的节点个数的节点个数int Onechild(BinTree T)/初始条件初始条件:二叉树已存在二叉树已存在/操作结果：输出二叉树中度为操作结果：输出二叉树中
