树的基本操作实验报告.doc

实验报告 -数据结构课程设计存储结构与基本运算的算法要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。学院： 专业：班级：学号： 姓名： 目录1.课程设计的目的32.问题描述33.需求分析34.模块设计35.系统主要子程序的详细设计36.调试分析7总结68、参考文献：69、程序清单:610、程序运行结果101.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.问题描述 (1) 存储结构与基本运算的算法要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。3.需求分析1.建立树2.树与二叉树的转换3.树的先序遍历（递归和非递归算法）4.树的后序遍历（递归和非递归算法）5. 层次序的非递归算法的实现4.模块设计（1）void CreateTree(Tree *tr)/建立树（2）void PreOrder(Tree root) /先序遍历树递归算法（3）void PreOrderTraverse(Tree T)/ 先序遍历树非递归算法（4）void InOrder(Tree root)/ 后序遍历树递归算法（5）void InOrderTraverse(Tree T)/ 后序遍历树非递归算法（6）void LevelOrder(Tree T)/ 层次遍历树（7）void mainwork( )/主函数。创建树，调用工作区模块函数5.系统主要子程序的详细设计（1）void CreateTree(Tree *tr) / 按照先序char ch; scanf(%c,&ch); if(ch=#) *tr=NULL; else *tr=(Tree)malloc(sizeof(TNode); / 生成一个新结点 (*tr)-data=ch; CreateTree(&(*tr)-firstchild); / 生成左子树 CreateTree(&(*tr)-nextsibling); / 生成右子树void Tree_to_BiTree(Tree *tr,BiTree *bt)if(*tr=NULL) *bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=(*tr)-data; Tree_to_BiTree(&(*tr)-firstchild),&(*bt)-LChild); Tree_to_BiTree(&(*tr)-nextsibling),&(*bt)-RChild); /(2) 树型打印二叉树void TranslevelPrint(BiTree bt) /本算法实现二叉树的按层打印struct nodeBiTree vecMAXLEN; / 存放树结点int layerMAXLEN; / 结点所在的层int locateMAXLEN; / 打印结点的位置int front,rear;q; / 定义队列qint i,j,k;int nLocate;j = 1;k = 0;q.front = 0; / 初始化队列q队头，队尾q.rear = 0; printf( );q.vecq.rear = bt; / 将二叉树根节点入队列q.layerq.rear = 1;q.locateq.rear = 20;q.rear = q.rear + 1;while(q.front q.rear) bt = q.vecq.front;i = q.layerq.front; nLocate = q.locateq.front;if(j i) / 进层打印时换行printf(n);printf(n);j = j + 1;k = 0;while(k nLocate)printf( );k+;while(k data);q.front = q.front + 1;if(bt-LChild != NULL) / 存在左子树，将左子树根节点入队列q.vecq.rear = bt-LChild;q.layerq.rear = i + 1;q.locateq.rear =(int)(nLocate - pow(2, NLAYER-i-1);q.rear = q.rear +1;if(bt-RChild != NULL) / 存在右子树，将右子树根节点入队列q.vecq.rear = bt-RChild;q.layerq.rear = i + 1;q.locateq.rear =(int)(nLocate + pow(2, NLAYER-i-1);q.rear = q.rear +1;/(3) 输出结点void Visit(char ch)printf(%c ,ch); /(4) 先序遍历树void PreOrder(Tree root) /递归算法if (root!=NULL)Visit(root-data); / 访问根结点PreOrder(root -firstchild); / 先遍历孩子PreOrder(root -nextsibling); / 后遍历兄弟void PreOrderTraverse(Tree T)/非递归算法sqstack S;Initstack(&S);Tree p=T;while(p|!StackEmpty(S)if(p)Visit(p-data);Push(&S,p);p=p-firstchild;elsePop(&S,&p);p=p-nextsibling; /(5) 后序遍历树void InOrder(Tree root)/递归算法 if (root!=NULL)InOrder(root -firstchild); / 先遍历孩子Visit(root -data); / 访问根结点InOrder(root -nextsibling); / 后遍历兄弟void InOrderTraverse(Tree T)/非递归算法sqstack S;Initstack(&S);Tree p=T;while(p|!StackEmpty(S)if(p)Push(&S,p);p=p-firstchild;elsePop(&S,&p);Visit(p-data);p=p-nextsibling; /(6) 层次遍历树void LevelOrder(Tree T)if (!T) exit(0); SqQueue Q; InitQueue(Q); Tree p=T; while(p|!QueueEmpty(Q)if(p)Visit(p-data);EnQueue(Q,p);p=p-nextsibling;elseDeQueue(Q,p);p=p-firstchild; 6.调试分析7总结设计算法以及调试过程中出现了很多问题，语法以及算法上的问题，通过查阅书籍以及上网查找得到解决，收获了很多。8、参考文献：（1）数据结构(C 语言版) 严蔚敏，吴伟民 编著.（2）程序设计与C语言 马鸣远编著（3）数据结构课程设计（C/C+）阮宏一、鲁静主编（4）网上搜索相关程序作为参考9、程序清单:“T.h”文件#include#include#include#include #define SIZE 100typedef struct BiTNode / 定义二叉树节点结构char data; struct BiTNode *LChild,*RChild; BiTNode,*BiTree;BiTree T;typedef struct TNode /定义树的节点结构，孩子兄弟表示法char data;struct TNode *firstchild,*nextsibling;TNode,*Tree;Tree Tr;typedef Tree elemtype;typedef struct sqstack elemtype stackSIZE; int top;sqstack;void Initstack(sqstack *s) s-top=0;bool StackEmpty(sqstack S ) /若S为空栈，则返回TRUE, 否则返回FALSEif( S.top = 0 )return true;elsereturn false;void Push(sqstack *s,elemtype x) if(s-top=SIZE-1) printf(ERROR,Overflow!n); else s-top+; s-stacks-top=x; void Pop(sqstack *s,elemtype *x) if(s-top=0) printf(ERROR,Underflow!n); else *x=s-stacks-top; s-top-; elemtype Gettop(sqstack s) if(s.top=0) printf(ERROR,underflown); return 0; else return s.stacks.top;#define MAX 10typedef int Status;typedef Tree QElemType;typedef structQElemType *base;int front;int rear;SqQueue;Status InitQueue(SqQueue &Q)/初始化Q.base=(QElemType *)malloc(MAX*sizeof(QElemType);if(!Q.base) exit(0);Q.front=Q.rear=0;return 1;Status EnQueue(SqQueue &Q,QElemType e)/插入if(Q.rear+1)%MAX=Q.front) return 0;/Q.rear+=e;/不是指针，所以错误！Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAX;return 1;Status DeQueue(SqQueue &Q,QElemType &e)/逐出if(Q.front=Q.rear) return 0;e=Q.baseQ.front;Q.front=(Q.front+1)%MAX;return 1;Status QueueEmpty(SqQueue &Q)if(Q.front=Q.rear) return 1;/队列为空else return 0;/各个子程序详见5.系统主要子程序的详细设计void mainwork()int yourchoice; printf(n-欢迎使用-n);printf(n 菜 单 选 择 nn);printf( 1. 输出树转化成的二叉树 2. 先序遍历树（递归方法） n);printf( 3. 后序遍历树（递归方法） 4. 先序遍历树（非递归方法） n);printf( 5. 后序遍历树（非递归方法） 6. 层次遍历树（非递归方法） n);printf( 7. 退出 n);printf(n-n); printf(请输入你的选择：);scanf(%d,&yourchoice);while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6|yourchoice=7)printf(输入选择不明确，请重输n);scanf(%d,&yourchoice);while(1)switch(yourchoice)case 1:printf(树的形状为:n);TranslevelPrint(T); getch();break;case 2:printf(先序遍历树（递归方法）序列为:); PreOrder(Tr);break;case 3:printf(n后序遍历树（递归方法）序列为:);InOrder(Tr); break;case 4:printf(n先序遍历树（非递归方法）序列为:);PreOrderTraverse(Tr);break;case 5:printf(n后序遍历树（非递归方法）序列为:); InOrderTraverse(Tr); break; case 6:printf(n层次遍历树（非递归方法）序列为:); LevelOrder(Tr); break;case 7: system(cls);exit(0); break;default: break; printf(n-欢迎使用二叉树基本操作程序-n); printf(n 菜 单 选 择 nn); printf( 1. 输出树转化成的二叉树 2. 先序遍历树（递归方法） n); printf( 3. 后序遍历树（递归方法） 4. 先序遍历树（非递归方法） n); printf( 5. 后序遍历树（非递归方法） 6. 层次遍历树（非递归方法） n); printf( 7. 退出 n); printf(n-n); printf(n请输入你的选择：); scanf(%d,&yourchoice);/endwhile