二叉树的顺序存储和三种遍历（代码）

//二叉树的顺序存储，三种遍历的代码
# include <stdlib.h>
# include <iostream.h>

# define chuzhi 50 //初始一维数组的大小
# define zengzhi 50 //一维数组的增量

typedef struct //定义树的头结点的数据类型
{
char *sz;//存放一维数组的头地址
int i;//存放一维数组的下标
int max;//存放一维数组的大小
}shu;

//初始化顺序表的头结点
void chushihua(shu &s)
{//分配相应空间，并给相应元素赋初值
int i;
s.sz=(char *)malloc(chuzhi * sizeof(char));//开辟存放元素的空间
s.i=0;//初始的下标为0
s.max=chuzhi;
for(i=0;i<chuzhi;i++)//给一维数组赋初值，是为了真确的输出树的结点元素
*(s.sz+i)='$';
cout<<"表头的初始化完成！\n";
}

//向一维数组中输入树的信息
void shuru(shu &s)
{
int j;//j的值代表着一维数据的下标和结点在树中的序号（按层次排）
char ch;
j=0;
while(j!=-1)
{
//输入结点在树中的序号或退出
cout<<"请按结点在树中的序号的大小顺序输入（退出请输入-1）：";
cin>>j;

if(j!=-1)//输入结点字符
{
cout<<"请输入结点字符：";
cin>>ch;
}

while(j>s.max)//如果一维数组不够大的操作
{
int n;
s.sz=(char *)realloc(s.sz,zengzhi+s.max);
for(n=s.max;n<s.max+zengzhi;n++)//初始化新开辟的空间
*(s.sz+n)='$';
s.max=zengzhi+s.max;
}

if(j!=-1)//存放元素值
{
s.i=j;//s.i中存放的是用到的一维数组下标的最大值
*(s.sz+j)=ch;//向一维数组中存放，把结点在树中的序号和一维数组的序号相对应
}
}
cout<<"你的输入以完成！\n";
}


//先序遍历的实现，后面的几种遍历的思想一样，后面的就不做过多解释
void shuchu1(shu &s,int i)
{
if(s.i==0)//判断是否为
{
cout<<"次树为空树！\n";
return;
}
if(*(s.sz+i)!='$')//当用到一维下标是17但没用一维下标为16时，就不输出一维下标为16存放的值
cout<<*(s.sz+i);
if(2*i<=s.i)//二叉树的性质
shuchu1(s,2*i);//迭代的思想
if((2*i+1)<=s.i)//二叉树的性质
shuchu1(s,2*i+1);//迭代的思想
}

//后序遍历的实现
void shuchu2(shu &s,int i)
{
if(s.i==0)//判断是否为空
{
cout<<"次树为空树！\n";
return;
}

if(2*i<=s.i)
shuchu2(s,2*i);
if((2*i+1)<=s.i)
shuchu2(s,2*i+1);
if(*(s.sz+i)!='$')
cout<<*(s.sz+i);
}

//中序遍历的实现
void shuchu3(shu &s,int i)
{
if(s.i==0)//判断是否为
{
cout<<"次树为空树！\n";
return;
}

if(2*i<=s.i)
shuchu3(s,2*i);
if(*(s.sz+i)!='$')
cout<<*(s.sz+i);
if((2*i+1)<=s.i)
shuchu3(s,2*i+1);
}

//主函数

void main()
{
int option1;//用户菜单的选择
int option2;//用户子菜单的选择
shu s;//定义表头

chushihua(s);//初始化表头
option1=0;
while(option1!=3)
{
cout<<"\n\n\n\n 菜单\n\n";
cout<<" 1、输入树的信息\n";
cout<<" 2、遍历树并显示\n";
cout<<" 3、退出\n\n";
cout<<"请输入您的操作：";
cin>>option1;

switch(option1)
{
case 1:
shuru(s);
break;
case 2:
cout<<" 1、先序遍历\n";
cout<<" 2、后序遍历\n";
cout<<" 3、中序遍历\n\n";
cout<<"请选择遍历的方式：";
cin>>option2;
switch(option2)
{
case 1:
shuchu1(s,1);
break;
case 2:
shuchu2(s,1);
break;
case 3:
shuchu3(s,1);
break;
default:
break;
}

break;

default:

break;

}
}

}

心得：不管是顺序存储还是链式存储，首先，考虑，结点的数据类型（有时还要考虑结点的结点的数据类型），表头的数据类型；初始化表头；数据怎么样输入到内存中；数据怎么从内存中输出来；这样分块的想问题，会让我们心里有底，即使遇到困难了，也不会慌。