数据结构课程设计之-树与二叉树的转换.doc

纲要
一 程序设计要求与目的
二 存储结构设计
三 算法设计（流程图）
四 详细设计（源代码）
五 调试与分析
六 实验总结
七 参考文献
第一章 程序设计要求与目的
题目：树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。
第二章 存储结构设计
引入头文件：
#include <>
#include <>
#include <>
设置常量：
#define MAX_TREE_SIZE 100
一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：
/*树的双亲表示结点结构定义*/
typedef struct
{
int data;
int parent; //双亲位置域
}PTNode;
/*双亲表示法树结构*/
typedef struct
{
PTNode node[MAX_TREE_SIZE];
int count; //根的位置和节点个数
}PTree;
/*树的孩子兄弟表示结点结构定义*/
typedef struct node{
int data;
struct node *firstchild;
struct node *rightsib;
}BTNode,*BTree;
第三章 算法设计（流程图）
流程图：
退出程序
层次遍历
开始
双亲法
建树
按照格式输入各个结点
输出树的结点情况
1
主菜单
前序遍历
（递归）
后序遍历
（递归）
前序遍历
（非递归）
后序遍历
（非递归）
输出遍历结果
副菜单
退出程序
2
3
5
4
0
0
6
9
第四章 详细设计（源代码）
详细设计共有以下函数的实现：
树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，树的前序遍历函数（递归和非递归两种），树的后序遍历函数(递归和非递归两种）,树的层次遍历函数，一般树和二叉树的转换函数。
主菜单和副菜单。
主函数。
具体代码如下：
//初始化树(双亲表示法)
void init_ptree(PTree *tree)
{
tree->count=-1;
}
//初始化树结点(孩子兄弟表示法)
BTNode GetTreeNode(int x)
{
BTNode t;
=x;
==NULL;
return t;
}
//树的前序遍历(递归)
void preorder(BTNode *T)
{
if(T!=NULL)
{
printf("%d ",T->data);
preorder(T->firstchild);
preorder(T->rightsib);
}
}
//树的前序遍历(非递归)
void preorder2(PTree T)
{
int i;
for(i=0;i<;i++)
{
printf("%d ",[i]);
}
}
//树后序遍历(递归)
void inoeder(BTNode *T)
{
if(T!=NULL)
{
inoeder(T->firstchild);
printf("%d ",T->data);
inoeder(T->rightsib);
}
}
//树后序遍历(非递归)
void inoeder2(PTree T)
{
int i;
for(i=-1;i>=0;i--)
{
printf("%d ",[i]);
}

}
//层次遍历
void level(PTree T)
{
int i;
for(i=0;i<;i++)
{
printf("%d ",[i]);
}

}
//水平输出二叉树
void PrintBTree(BTNode *root,int level)
{
int i;
if(root!=NU