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

广西工学院计算机学院数据结构课程实验报告书实验六 二叉树的基本操作及其应用 学生姓名： 学 号： 班级： 指导老师： 专 业：计算机学院软件学院提交日期：2013年6月22日1 实验目的1） 了解二叉树的特点、掌握二叉树的主要存储结构。2） 掌握二叉树的基本操作，能针对二叉树的具体应用选择相应的存储结构。3） 掌握递归算法的设计方法。2.实验内容（1）二叉链表表示二叉树，建立一棵二叉树，实现下列基本操作,通过数据测试每个操作的正确性，包括：1. CreateBinTree(&T)： 建立一颗二叉树：。2. BinTreeEmpty(T): 判断一棵二叉树是否为空树。3. PreOrderTraverse(T): 先序遍历二叉树T，并输出节点序列。4. InOrderTraverse(T): 中序遍历二叉树T，并输出节点序列。5. PostOrderTraverse(T):后序遍历二叉树T，并输出节点序列。6. LevelOrderTraverse(T):层次遍历二叉树T，并输出节点序列。7. Value(T,e):查找值为e的节点，并返回该节点的地址。8. BinTreeDepth(T):返回二叉树的深度。9. Parent(T,e):查找二叉树T中值为e的节点的双亲，若e为根节点，操作失败。（流程图）10. LeftChild(T,e):查找二叉树T中值为e的节点的左孩子，若e没有左孩子，则操作失败。（流程图）11.RightChild(T,e):查找二叉树T中值为e的节点的右孩子，若e没有右孩子，则操作失败。12. CountNode(T):计算二叉树中节点的个数。13. Leaf(T): 计算二叉树中叶子节点的个数。 14. OneChild(T): 计算二叉树中度为1的节点个数。 3实验要求（1） 上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。（2） 用一切你能想到的办法解决遇到的问题，培养解决问题的能力。（3） 实验课上进行答辩。（4） 实验报告当场交。报告内容包括 ：实验目的、实验内容、实验代码、实验运行结果以及实验体会供五部分。3主要算法3.1 顺序存储结构（1） 结构定义：#include#include#include #include/各头文件#define OK 1#define ERROR 0#define OVERFLOW -2typedef 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;elseT=(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，反之返回0if(!T)return 1;elsereturn 0;/先序遍历二叉树void PreorderTraverse(BinTree T)/初始条件:二叉树已存在 /操作结果：先序递归遍历Tif(T) printf(%c,T-data); PreorderTraverse(T-lchild); PreorderTraverse(T-rchild);return;/中序遍历二叉树void InorderTraverse(BinTree T)/初始条件:二叉树已存在 /操作结果:中序递归遍历Tif(T) InorderTraverse(T-lchild); printf(%c,T-data); InorderTraverse(T-rchild);return;/后序遍历二叉树void PostorderTraverse(BinTree T)/初始条件:二叉树已存在 /操作结果:后序递归遍历Tif(T) PostorderTraverse(T-lchild); PostorderTraverse(T-rchild); printf(%c,T-data); return;/初始化链式队列void InitQueue(QUEUE *q)/初始条件:队列不存在/操作结果：建立一个队列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-rear;/判断空队列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);/建立新结点pif(!p)exit(0); p-data=e; p-next=NULL; q-rear-next=p; q-rear=p; /出队列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);/层次遍历二叉树void LevelTraverse(BinTree T) /初始条件:二叉树已存在 /操作结果:层次递归遍历TQUEUE q;BinTree a;if(T)InitQueue(&q);/初始化链式队列EnQueue(&q,T);/入队列while(!QueueEmpTy(q)DeQueue(&q,&a);/出队列printf(%c,a-data); if(a-lchild)/有左孩子 EnQueue(&q,a-lchild );if(a-rchild )/有右孩子 EnQueue(&q,a-rchild );return;/查找值为e的节点BinTree value(BinTree T, TElemType e)/初始条件:二叉树已存在 /操作结果：返回二叉树T中指向元素值为e的结点的指针QUEUE q; BinTree a;if(T)InitQueue(&q);/初始化链式队列EnQueue(&q,T);/入队列while(!QueueEmpTy(q)DeQueue(&q,&a);/出队列if(a-data =e) return a; if(a-lchild)/有左孩子 EnQueue(&q,a-lchild );if(a-rchild )/有右孩子 EnQueue(&q,a-rchild );return NULL;/计算二叉树的深度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中指向元素值为e的结点的双亲的指针QUEUE q; BinTree a;if(T)InitQueue(&q);/初始化链式队列EnQueue(&q,T);/入队列while(!QueueEmpTy(q)DeQueue(&q,&a);/出队列if(a-lchild&a-lchild-data=e|a-rchild&a-rchild-data=e)return a;else if(a-lchild)/有左孩子 EnQueue(&q,a-lchild ); if(a-rchild )/有右孩子 EnQueue(&q,a-rchild ); return NULL;/查找值为e的节点的左孩子BinTree Leftchild(BinTree T,TElemType e)/初始条件:二叉树已存在 /操作结果：返回二叉树T中指向元素值为e的结点的左孩子的指针BinTree p;p=value(T,e);if(p)if(p-lchild)return p-lchild;else return NULL; return NULL;/查找值为e的节点的右孩子BinTree Rightchild(BinTree T,TElemType e)/初始条件:二叉树已存在 /操作结果：返回二叉树T中指向元素值为e的结点的右孩子的指针 BinTree p; p=value(T,e);if(p)if(p-rchild)return p-rchild;else return NULL; return NULL;/计算二叉树中节点的个数int CountNode(BinTree T)/初始条件:二叉树已存在 /操作结果：输出二叉树中节点的个数static int sum=0;if(NULL!=T)+sum; CountNode(T-lchild); CountNode(T-rchild);return sum;/计算二叉树中叶子节点的个数int Leaf(BinTree T)/初始条件:二叉树已存在 /操作结果：输出二叉树中叶子节点的个数if(!T)return 0;if(!T-lchild&!T-rchild)return 1;return Leaf(T-lchild)+Leaf(T-rchild);/计算二叉树中度为1的节点个数int Onechild(BinTree T)/初始条件:二叉树已存在 /操作结果：输出二叉树中度为1的节点个数 if(!T)return 0; if(T-lchild&!T-rchild|!T-lchild &T-rchild) return 1+ Onechild(T-lchild)+ Onechild(T-rchild); return Onechild(T-lchild)+ Onechild(T-rchild);/主函数void main()BinTree t,p;char e; int j,k;while(1) system(cls);/清屏 printf(nt*); printf(nt* 二叉树的基本操作及其应用 *); printf(nt*n); printf(t * 1.建立二叉树 2.先序遍历 *n); printf(t * 3.中序遍历 4.后序遍历 * n); printf(t * 5.层次遍历 6.二叉树层数 * n); printf(t * 7.结点个数 8.叶子结点数 * n); printf(t * 9.单孩子结点数 10.查找结点左孩子 *n); printf(t * 11.查找结点右孩子 12.查找结点双亲 *n); printf(t * 13.清空二叉树 0.退出 *n); printf(t*n); printf(请选择选项: ); scanf( %d,&k); if(k13) printf(输入有误，请重新输入!);printf(n);printf(nttt按任意键进行重新操作!); getch(); continue; switch(k) case 1: system(cls);/清屏 printf(按先序遍历建立一棵二叉树，输入相应的数据序号：n); printf(比如: AAA_A_n); printf(=n); printf( ( 1 ); printf(n); printf( / ); printf(n); printf( ( 2 ) ( 4 ); printf(n); printf( / / ); printf(n); printf( ( 3 ) ( ) ( ) ( ); printf(n); printf(=n); printf(n); printf(你的输入为：); CreateBinTree(t); printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 2: printf(先序遍历二叉树的序列为：); PreorderTraverse(t);/调用先序遍历函数 printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 3: printf(中序遍历二叉树的序列为：); InorderTraverse(t);/调用中序遍历函数 printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 4: printf(后序遍历二叉树的序列为：); PostorderTraverse(t);/调用后序遍历函数 printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 5: printf(层次遍历二叉树的序列为：); LevelTraverse(t);/调用层次遍历函数 printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 6: printf(二叉树共有%d层!n,BinTreeDepth(t); printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 7: printf(二叉树的结点数为：%dn,CountNode(t); printf(nttt按任意键进行重新操作!); getch(); break; case 8: printf(二叉树的叶子结点数为：%dn,Leaf(t); printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 9: printf(二叉树的单孩子结点数为：%dn,Onechild(t); printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 10: printf(请输入要查找结点的值：); e=getchar(); scanf(%c,&e); p=Parent(t,e); if(p) printf(n值为%c的结点的双亲结点的值为:%c,e,p-data); else printf(n这结点无双亲!); printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 11: printf(请输入要查找结点的值：); e=getchar(); scanf(%c,&e); p=Leftchild(t,e); if(p) printf(n值为%c的结点的左孩子结点的值为:%c,e,p-data); else printf(n这结点无左孩子!); printf(n); pr