《树的基本操作实验报告》由会员分享，可在线阅读，更多相关《树的基本操作实验报告（16页珍藏版）》请在金锄头文库上搜索。
1、实验报告数据结构课程设计存储结构与基本运算的算法要求：实现树与二叉树的转换的实现。以及树的前序、后序的递 归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。目录1. 课程设计的目的32. 问题描述33. 需求分析34. 模块设计35. 系统主要子程序的详细设计36. 调试分析7总结68、参考文献：69、程序清单:610、程序运行结果101. 课程设计的目的(1) 熟练使用C语言编写程序，解决实际问题；(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计 能力；(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基 本方法和技能；(4) 提高综合运用所学的
2、理论知识和方法独立分析和解决问题的能力；2. 问题描述(1) 存储结构与基本运算的算法要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算 法，层次序的非递归算法的实现，应包含建树的实现。3. 需求分析1. 建立树2. 树与二叉树的转换3. 树的先序遍历(递归和非递归算法)4. 树的后序遍历(递归和非递归算法)5. 层次序的非递归算法的实现4. 模块设计(1) void CreateTree(Tree *tr)/建立树(2) void PreOrder(Tree root) /先序遍历树递归算法(3) void PreOrderTraverse(Tree T)/先序遍历树非递归
3、算法(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
4、=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)-RChi
5、ld); /(2)树型打印二叉树 void TranslevelPrint(BiTree bt) 本算法实现二叉树的按层打印BiTree vecMAXLEN;int layerMAXLEN;int locateMAXLEN;int front,rear;q;int i,j,k;int nLocate; j = 1;k = 0;struct node/存放树结点结点所在的层/打印结点的位置/定义队列qq.front = 0; /初始化队列q队头，队尾q.rear = 0; printf( ); q.vecq.rear = bt; / 将二叉树根节点入队列q.layerq.rear = 1; q.
6、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-LCh
7、ild;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)先
8、序遍历树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-
9、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); V
10、isit(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语言版）
11、严蔚敏，吴伟民编著.（2）程序设计与C语言马鸣远编著（3）数据结构课程设计（C/C+）阮宏一、鲁静主编（4）网上搜索相关程序作为参考9、程序清单:“T.h”文件#include#include#include#include /定义二叉树节点结构#define SIZE 100 typedef struct BiTNode char data;struct BiTNode *LChild,*RChild;BiTNode,*BiTree;BiTree T;typedef struct TNode定义树的节点结构，孩子兄弟表示法 char data; struct TNode *firstchil
12、d,*nextsibling;TNode,*Tree;Tree Tr;typedef Tree elemtype;typedef struct sqstackelemtype stackSIZE; int top;sqstack;void Initstack(sqstack *s)s-top=0;bool StackEmpty(sqstack S ) 若S为空栈，则返回TRUE,否则返回FALSEif( S.top = 0 ) return true;else return false;void Push(sqstack *s,elemtype x)if(s-top=SIZE-1)printf
13、(ERROR,Overflow!n);elses-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;elsereturn 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;/不是指针，
