课程设计（数据结构）
院、系专业。
姓名学号。指导教师。
2010 年月日。
树的应用。摘要：
关键词：树；二叉树；转换；遍历；递归和非递归。
1．实验题目
实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。
2．实验分析。
2．1总体分析。
2.1.1本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。
2.1.2本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。
2.1.3本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。
2.2具体分析。
2.2.1二叉树创建。
用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 binode creat()，binode stree_creat(char *a,int k)。
2.2.2先序遍历二叉树的递归算法。
若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void preorder(binode root)。
2.2.3中序遍历二叉树的递归算法。
若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。void inorder(binode root)。
2.2.4后序遍历二叉树的递归算法。
若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void postorder(binode root)。
2.2.5先序非递归算法。
binode根指针，若 binode!= null对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取 binode的右子树的根指针？void f_preorder(binode root)
2.2.6中序非递归算法。
binode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取binode指针？void f_inorder(binode root)。
2.2.7后序非递归算法。
binode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void f_postorder(binode root)。
2.2.8层次序遍历算法。
按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void levelorder(binode root)。
2.2.9树与二叉树的转换算法。
转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩子。void exchange()，class tree.
3.实验步骤。
3.1流程图。
图 1、二叉树的创建。
图2、前序递归遍历。
图3、中序递归遍历。
图4、后序递归遍历。
图5、前序非递归遍历。
图6、中序非递归遍历。
图7、后序非递归遍历。
图8、层序遍历。
3.2**：
#include
using namespace std;
#include<>
#include<>
#define maxsize 100
#include ""
#define len sizeof(struct btree)
int max=1;
typedef struct btree //二叉树节点结构体。
btree *lchild,*rchild;
char data;
*binode;
typedef struct stackelemtype//栈的结构体。
binode ptr;
int flag;
stackelemtype;
binode p ;
/二叉树的建立。
binode stree_creat(char *a,int k)
binode root; max++;
if(a[k]==0'||k>maxsize)
return null; /判断树是否为空。
else root=(binode)malloc(len);/动态申请节点。
root->data=a[k];
root->lchild=stree_creat(a,2*k+1); 递归调用为左孩子赋值。
root->rchild=stree_creat(a,2*k+2); 递归调用为右子赋值。
return root;//返回根节点指针。
void print(binode root) /输出所创建的二叉树。
binode h[maxsize]=;
int top=0,base=0,j=0,k=0,n=0,m=0;
h[top]=root;
j=log(max+1)/log(2)-1;
if(pow(2,j+1)-1 cout<<"你刚输入的是：";
while(h[base]!=null) /把二叉树的值依次存入数组。
h[++top]=h[base]->lchild;
h[++top]=h[base]->rchild;
base++;
for(top=0;h[k]!=null;top++)按层输出。
cout<<"n";
for(n=0;n<(m-1);n++)
cout<<"
for(base=0;basecout<<"
cout<<"n";
//二叉树的后序遍历递归算法。
void postorder(binode root)
if(root==null)return;//递归调用的约束条件。
elsepostorder(root->lchild);
postorder(root->rchild);
if(root->data=='0')
else cout<<"data<<"
/二叉树的中序遍历递归算法。
void inorder(binode root)
if(root==null)return;//递归调用的约束条件。
elseinorder(root->lchild);
if(root->data=='0')
else cout<<"data<<"
inorder(root->rchild);
/二叉树的前序递归遍历算法。
void preorder(binode root)while(root!=null||top>0);
/中序非递归遍历算法。
void f_inorder(binode root)
binode s[maxsize]; 申请一个binode数组。
int top=0; /采用顺序栈，并假定不会发生上溢。
do{while(root!=null) /当结点不为空时。
s[++top] =root; /依次将结点压入栈。
root = root->lchild; /根赋值为它的左孩子。
if(top>0) /当节点为空但栈顶不为零时。
root = s[top]; 把栈顶元素负给根结点。
if(root->data=='0')
else cout<<"data<<"输出根结点。
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...