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