Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1384675
  • 博文数量: 370
  • 博客积分: 10654
  • 博客等级: 中将
  • 技术积分: 4396
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-07 15:44
文章分类

全部博文(370)

文章存档

2012年(36)

2011年(195)

2010年(139)

分类: C/C++

2011-05-19 20:29:25

#include <iostream>
using namespace std;

#define MAX_NODE_SIZE 100 //二叉树的最大节点数
typedef
char SqBiTree[MAX_NODE_SIZE+1]; //0号单元节点个数

//创建二叉树
void creat_tree(SqBiTree &t)
{
int i=0;
char ch;
while((ch=getchar())!='$')
{
i
++;
t[i]
=ch;
}
t[
0]=i;
}

//获取给定结点(位置)的左孩子的结点位置
int LeftChild_locate(SqBiTree &t,int node)
{
if ((2 * node) > t[0])
return -1;
else
return 2 * node;
}
//获取给定结点(位置)的右孩子的结点位置
int RightChild_locate(SqBiTree &t,int node)
{
if ((2 * node+1) > t[0])
return -1;
else
return 2 * node+1;
}

//层序遍历
void level_order(SqBiTree &t)
{
for(int i=1;i<=t[0];i++)
if(t[i]!='#')
cout
<<t[i]<<" ";
}
//先序遍历
void pre_order(SqBiTree &t,int i)
{
if(t[0]<=0)
{
cout
<<"空树!"<<endl;
}
else
{
if(t[i]!='#')
cout
<<t[i]<<" ";
if(LeftChild_locate(t,i)!=-1) //如果左子结点存在,递归
pre_order(t,LeftChild_locate(t,i));
if(RightChild_locate(t,i)!=-1) //如果右子结点存在,递归
pre_order(t,RightChild_locate(t,i));
}
}
//中序遍历
void mid_order(SqBiTree &t,int i)
{
if(t[0]<=0)
{
cout
<<"空树!"<<endl;
}
else
{
if(LeftChild_locate(t,i)!=-1) //如果左子结点存在,递归
mid_order(t,LeftChild_locate(t,i));
if(t[i]!='#')
cout
<<t[i]<<" ";
if(RightChild_locate(t,i)!=-1) //如果右子结点存在,递归
mid_order(t,RightChild_locate(t,i));
}
}
//后序遍历
void back_order(SqBiTree &t,int i)
{
if(t[0]<=0)
{
cout
<<"空树!"<<endl;
}
else
{
if(LeftChild_locate(t,i)!=-1) //如果左子结点存在,递归
back_order(t,LeftChild_locate(t,i));
if(RightChild_locate(t,i)!=-1) //如果右子结点存在,递归
back_order(t,RightChild_locate(t,i));
if(t[i]!='#')
cout
<<t[i]<<" ";
}
}
int main()
{
cout
<<"创建二叉树:"<<endl;
SqBiTree sbt;
//创建顺序二叉树
creat_tree(sbt);
//层序遍历
level_order(sbt);
cout
<<endl;
//先序遍历
pre_order(sbt,1);
cout
<<endl;
//中序遍历
mid_order(sbt,1);
cout
<<endl;
//后续遍历
back_order(sbt,1);
cout
<<endl;

cout
<<LeftChild_locate(sbt,3);
return 0;
}
阅读(2652) | 评论(0) | 转发(0) |
0

上一篇:zenity

下一篇:C语言常见的出错信息

给主人留下些什么吧!~~