数据结构课程设计--树的应用.docVIP

数据结构 课程设计报告 设计题目：树的应用 年 级 2010级 班 级 计科105 姓 名 聂永胜 赵攀攀 张姣姣 学 号 20101515506 20101515526 20101515511 指导教师 李晓辉 起止时间 12—9—24-----------9—28 2012--2013 年 一 学期 一．实习目的 更加深入的理解、掌握数据结构的一些算法并加以实现，提高自身的地动手实践能力，培养更好的团队合作能力。 二．问题描述（具体任务） 设计、创建一棵树，实现树与二叉树的互相转换以及对树的递归 非递归先序遍历，树的递归非递归后序遍历以及树的非递归层次遍历的操作。 三．需求分析 1、本演示程序中，可以输入任意个节点构造你想要的树，本程序构造时默认的是一个三度的树，也就是在创建树时所默认的是每个节点都有三个孩子，但是你可以通过键盘输入#号来让某些节点为空，以此来创建让您满意的树。 2、程序以用户和计算机对话的形式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入要创建树的节点值，然后通过程序执行输出结果。 3、程序的执行命令包括： （1）树的创建模块 （2）树与二叉树相互转换模块 （3）树的先序、后序、层次遍历（递归与非递归算法） 4、测试数据： （1）测试数据由用户从键盘上任意输入。 四．算法设计思想及流程图 （1）根据老师所提供的课程设计题目及要求我们将程序分了9个模块，通过主程序调用相应的模块来实现课程的操作。 五．C++语言源代码 #include iostream using namespace std; #define m 3 typedef char ElemType; typedef struct Node { ElemType data; struct Node* child[m]; }Node,*Tree; typedef struct BiTNode{ ElemType data; struct BiTNode*lchild,*rchild; }BiTNode,*BiTree; typedef struct stack { //栈结构定义 BiTree data[100]; //data 元素类型为 指针 int top; //栈顶指针 }seqstack; // 按前序遍历 创建一棵度数为3的树的递归算法 void createtree(Tree p) { int i; char ch; if((ch=getchar())==#) p=NULL; //建立一棵空树 else { p=(Tree)malloc(sizeof(Node)); p-data=ch; for(i=0;im;i++) createtree(p-child[i]); } } //树转化为二叉树 BiTree TreetoBiTree(Tree p) { int i; if(p==NULL) return NULL; BiTNode* q=(BiTNode*)malloc(sizeof(ElemType)) ;//创建根节点------------------------------------------------------------ q-data =p-data; q-lchild=NULL; q-rchild=NULL; if(p-child[0]!=NULL){ q-lchild=TreetoBiTree(p-child[0]);//把树的第一个孩子赋给二叉树的左孩子 BiTNode* r=q-lchild; if(p-child[1]!=NULL) { for(i=1;im;i++) { if(p-child[i]!=NULL) { r-rchild=TreetoBiTree(p-child [i]); r=r-rchild; } else return q; } } else if(p-child[2]!=NULL){ r-rchild=TreetoBiTree(p-child [2]); r=r-rchild; } else return q; } else if((p-ch