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

衡阳师范学院
《数据结构》课程设计

题 目： 树与二叉树的转换
系 别： 计算机科学系
专 业： 计算机科学与设计
班 级： 1302
学生姓名： 戴志豪
学 号： 13190217
指导老师： 赵磊
完成日期： 2015年1月3号

目 录
一．需求分析.…………………………………………………………………3
二．概要设析………………………………………………………………….3
三．详细设计………………………………………………………………….5
1.树的建立………………………………………………………………..5
2.一般树转化成二叉树…………………………………………………..6
3.先序遍历树的递归算法………………………………………………..7
4.后序遍历树的递归算法………………………………………………..7
5.先序遍历树的非递归算法……………………………………………..7
6.后序遍历树的非递归算法……………………………………………..8
7.层次序非递归的算法…………………………………………………..9
四．设计与调试分析………………………………………………………….10
五．用户手册………………………………………………………………….10
六．测试结果………………………………………………………………….11
七．附录（源程序）………………………………………………………….14
八．总结……………………………………………………………………….20

一.需求分析
本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现树的非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。

二．概要设计
对于本次设计，需要用到树的建立,树与二叉树的转换算法先序后序二叉树的递归算法;先序后序非递归算法;层次序遍历算法
1树的建立
用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。
开始
参数数组是否空或越界
把数组的值赋给结点的数据域
返回根指针
结束
返回空指针
Y
N
递归的给左子树赋值参数变为a[2i+1]

递归的给右子树赋值参数变为a[2i+2]

2一般树转化成二叉树
转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。void exchange()，class Tree
3先序遍历树的递归算法
若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。
开始
判断结点是否空
访问根结点
结束
按前根遍历方式遍历左子树
按前根遍历方式遍历左子树

Y
N

4后序遍历树的递归算法
若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。

开始
判断结点是否空

按后根遍历方式遍历左子树

结束
按后根遍历方式遍历右子树

访问根结点

Y
N

5先序遍历树的非递归算法
若二叉树为空，则空操作；否则（1）先将根节点进栈，在栈不为空时循环；(2)出栈p，访问*p若其右孩子节点不空将右孩子节点进栈若其左孩子节点不空时再将其左孩子节点进栈。

6后序遍历树的非递归算法
采用一个栈保存需要返回的指针，先扫描根节点所有的左孩子节点并一一进栈，出栈一个节点*b作为当前节点，然后扫描该节点的右子树。当一个节点的左右孩子节点均访问后再访问该节点，如此重复操作，直到栈空为止。
7层次序的非递归遍历
按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。

三． 详细设计
1树的建立：
PTree CreatTree(PTree T)
{
int i=1;
int fa,ch;
PTNode p;
for(i=1;ch!=-1;i++)
{
printf("输入第%d结点:\n",i);
scanf("%d,%d",&fa,&ch);
printf("\n");
p.data=ch;
p.parent=fa;
T.count++;
T.node[T.count].data = p.data;
T.node[T.count].parent = p.parent;
}
printf("\n");
printf("创建的树具体情况如下:\n");
print_ptree(T);
return T;

2一般树转换成二叉树
BTNode *change(PTree T)
{
int i,j=0;
BTNode p[MAX_TREE_SIZE];
BTNode *ip,*is,*ir,*Tree;
ip=(BTNode *)malloc(sizeof(BTNode));
is=(BTNode *)malloc(sizeof(BTNode));
ir=(BTNode *)malloc(sizeof(BTNode));
Tree=(BTNode *)malloc(sizeof(BTNode));
for(i=0;i<T.count;i++)
{
p[i]=GetTreeNode(T.node[i].data);
}
for(i=1;i<T.count;i++)
{
ip=&p[i];
is=&p[j];
while(T.node[i].parent!=is->data)
{
j++;
is=&p[j];

}
if(!(is->firstchild))
{
is->firstchild=ip;
ir=ip;
}
else
{
ir->rightsib=ip;
ir=ip;
}
}
Tree=&p[0];
return Tree;

}

3先序遍历树的递归算法：
void preorder(BTNode *T)
{
if(T!=NULL)
{
printf("%d ",T->data);
preorder(T->firstchild);
preorder(T->rightsib);
}
}
4.先序遍历树的非递归算法
void preOrder2(BinTree *root) //非递归先序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
5.后序遍历树的递归算法
void inoeder(BTNode *T)
{
if(T!=NULL)
{
inoeder(T->firstchild);
printf("%d ",T->data);
inoeder(T->rightsib);
}
}
6后序遍历树的非递归算法
void postOrder2(BinTree *root) //非递归后序遍历
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //第二次出现在栈顶
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
7层次序树的非递归算法
void initqueue(linkqueue &q) //初始化一个带头结点的队列
{
q.front=q.rear=(queueptr)malloc(sizeof(queuenode));
q.front->next=NULL;
}

void enqueue(linkqueue &q,bitrees p) //入队列
{
queueptr s;
int first=1;
s=(queueptr)malloc(sizeof(queuenode));
s->ch=p;
s->next=NULL;
q.rear->next=s;
q.rear=s;
}
void dequeue(linkqueue &q,bitrees &p) //出队列
{
int data;
queueptr s;
s=q.front->next;
p=s->ch;
data=p->data;
q.front->next=s->next;
if(q.rear==s)
q.rear=q.front;
free(s);
printf("%d\t",data);
}
int queueempty(linkqueue q) //判断队列是否为空
{
if(q.front->next==NULL)
return 1;
return 0;
}
void traverse(bitrees bt) //按层次遍历树中结点
{
linkqueue q;
bitrees p;
initqueue(q);
p=bt;
enqueue(q,p);
while(queueempty(q)!=1)
{
dequeue(q,p);
if(p->lchild!=NULL)
enqueue(q,p->lchild);
if(p->rchild!=NULL)
enqueue(q,p->rchild);
}
四． }设计与调试分析
1.二叉树遍历中用到的最重要的一个思想就是递归调用，这次作业使我们对递归有了深入的理解，程序调试比较顺利。
2.用栈同样可以实现二叉树的遍历，这是我们认识到解决问题可以由多种不同的途径，应随时将以前学过的只是灵活应用起来，解决新问题。
3.因为遍历二叉树的基本操作是访问结点，所以无论哪一种遍历方式，对含有n个结点的二叉树，其时间复杂度为O（n），所需辅助空间最大容量为树的深度，最坏为n，所以空间复杂度为O（n）。
4.因该程序对应不同的遍历定义了不同的结构，使每种结构的通用性降低，可以往在递归和非递归中使用同一种结构这一方面做进一步的思考。

五．用户手册
运行程序，首先出现主界面。主界面有七个选项。
选项一、以双亲法创建一棵树。
选项二、此选项可以对所创建的树采用递归算法进行前序遍历。
选项三、此选项可以对所创建的树采用递归算法进行后序遍历。
选项四、此选项可以对所创建的树采用非递归算法进行先序遍历。
选项五、此选项可以对所创建的树采用非递归算法进行后序遍历。
选项六、此选项可以退出程序。

六．测试结果
程序开始

一般树转换成二叉树的情况

副菜单选择：选择9继续操作
运用各种遍历形式遍历树

副菜单选择0结束程序

七．附录（源程序）
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//设置常量：
#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;

//初始化树(双亲表示法)
void init_ptree(PTree *tree)
{
tree->count=-1;
}

//初始化树结点(孩子兄弟表示法)
BTNode GetTreeNode(int x)
{
BTNode t;
t.data=x;
t.firstchild=t.rightsib=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<T.count;i++)
{
printf("%d ",T.node[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=T.count-1;i>=0;i--)
{
printf("%d ",T.node[i]);
}

}

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

}

//水平输出二叉树
void PrintBTree(BTNode *root,int level)
{
int i;
if(root!=NULL)
{
PrintBTree(root->rightsib,level+1);
for(i=1;i<=8*level;i++)
printf(" ");
printf("-------%d\n",root->data);
PrintBTree(root->firstchild,level+1);
}
}

//输出树
void print_ptree(PTree tree)
{
int i;
printf(" 序号 结点 双亲\n");
for(i=0;i<=tree.count;i++)
{
printf("%8d%8d%8d",i,tree.node[i].data,tree.node[i].parent);
printf("\n");
}
}

/*用双亲表示法创建树*/
PTree CreatTree(PTree T)
{
int i=1;
int fa,ch;
PTNode p;
for(i=1;ch!=-1;i++)
{
printf("输入第%d结点:\n",i);
scanf("%d,%d",&fa,&ch);
printf("\n");
p.data=ch;
p.parent=fa;
T.count++;
T.node[T.count].data = p.data;
T.node[T.count].parent = p.parent;
}
printf("\n");
printf("创建的树具体情况如下:\n");
print_ptree(T);
return T;
}

/*一般树转换成二叉树*/
BTNode *change(PTree T)
{
int i,j=0;
BTNode p[MAX_TREE_SIZE];
BTNode *ip,*is,*ir,*Tree;
ip=(BTNode *)malloc(sizeof(BTNode));
is=(BTNode *)malloc(sizeof(BTNode));
ir=(BTNode *)malloc(sizeof(BTNode));
Tree=(BTNode *)malloc(sizeof(BTNode));
for(i=0;i<T.count;i++)
{
p[i]=GetTreeNode(T.node[i].data);
}
for(i=1;i<T.count;i++)
{
ip=&p[i];
is=&p[j];
while(T.node[i].parent!=is->data)
{
j++;
is=&p[j];

}
if(!(is->firstchild))
{
is->firstchild=ip;
ir=ip;
}
else
{
ir->rightsib=ip;
ir=ip;
}
}
Tree=&p[0];
return Tree;

}

/*主菜单*/
void Menu()
{
printf("=================主菜单=======================\n");
printf("***输入1-------------以双亲法创建一棵一般树***\n");
printf("***输入2-------------树的先序遍历(递归)*******\n");
printf("***输入3-------------树的后序遍历(递归)*******\n");
printf("***输入4-------------树的先序遍历(非递归)*****\n");
printf("***输入5-------------树的后序遍历(非递归)*****\n");
printf("***输入6-------------层次序的非递归遍历*******\n");
printf("***输入0-------------退出程序*****************\n");
printf("==============================================\n");
printf("请输入执行的指令:");
}

/*副菜单*/
void Menu2()
{
printf("*****************副菜单*******************\n");
printf("***9-------------返回主菜单继续操作*******\n");
printf("***0-------------退出程序*****************\n");
}

/*主函数*/
int main()
{
int i=0,c1,c2;
PTree T;
BTNode *Tree;
init_ptree(&T);
loop:
Menu();
scanf("%d",&c1);
switch(c1)
{
case 1:
printf("建立一般树,依次输入各个结点情况:\n");
printf("输入结点方式:双亲数据,整型数据(第一个结点双亲数据为-1,最后以-1,-1结束)\n例子:-1,1 1,3\n");
T=CreatTree(T);
Tree=change(T);
printf("一般树转换成二叉树后的情况:\n");
PrintBTree(Tree,i);
getchar();
break;

case 2:
printf("树的前序遍历(递归):\n");
preorder(Tree);
printf("\n");
break;

case 3:
printf("树的后序遍历(递归):\n");
inoeder(Tree);
printf("\n");
break;

case 4:
printf("树的前序遍历(非递归):\n");
preorder2(T);
printf("\n");
break;

case 5:
printf("树的后序遍历(非递归):\n");
inoeder2(T);
printf("\n");
break;

case 6:
printf("树的层次遍历:\n");
level(T);
printf("\n");
break;

case 0:
exit(1);
break;
}
Menu2();
scanf("%d",&c2);
if(c2==9)
goto loop;
else if(c2==0)
exit(1);

}

八．课程设计心得

通过本次程序设计，让我更深层次地了解到了树各种函数的运用，如何运用各种存储结构创建树，以及在实验中还涉及到递归的运用，递归的思想省去了复杂的算法设计。在实验中不可避免的出现了大大小小的问题，在调试中领悟各种算法的真谛，同样的错误在下次遇到时就可以避免了,也让我懂得了自己动手比去做去看书要好的多，还有编程运行的时候都是不能够粗心大意的。

第 21 页 共 21 页