刚刚接触二叉树的同学一很想学习如何构建一颗简单的二叉树,下面我用C语言来实现一个简单的二叉树,并且用先序、中序和后序的方法来遍历它。
#include
#include
#include
#include
typedef struct node
//定义二叉树的节点
/*
可能有人不知道typedef是干什么用的
写了typedef后在定义结构体时就不用写struct node a;
直接写node a;就行了,比较方便
*/
{
int data;
struct node *ltree,*rtree;
}node;
node *cNode(int n)
{
node *p;
p=(node*)malloc(sizeof(node));//申请内存空间
p->data=n;
p->ltree=p->rtree=0;//左孩子与右孩子都为空
return p;// 返回所创建节点(结构体)的指针
}
void mtree(node *par,node *lc,node *rc)//par父节点,lc左孩子,rc右孩子
{
par->ltree=lc;
par->rtree=rc;
}
void ztr(node *t)//中序遍历
{
/*
因为遍历左子树的方式与遍历左子树的左子树方式类似,所以可以用递归很方便的写出来
代码很少,想着也简单,但计算机执行的过程是很复杂的
*/
if (t!=0)
{
ztr(t->ltree);//遍历左子树
printf("%d",t->data);//输出根节点
ztr(t->rtree);//遍历右子树
}
}
void xtr(node *t)//先序遍历
{
if (t!=0)
{
printf("%d",t->data); //输出根节点
xtr(t->ltree);//遍历左子树
xtr(t->rtree);//遍历右子树
}
}
void htr(node *t)//后序遍历
{
if (t!=0)
{
htr(t->ltree);//遍历左子树
htr(t->rtree);//遍历右子树
printf("%d",t->data);//输出根节点
}
}
int main()
{
int i,j,n;
node *a,*b,*c,*d,*e,*f,*g;
a=cNode(1);//创建一个节点,值为1;
b=cNode(2);
c=cNode(3);
d=cNode(4);
e=cNode(5);
f=cNode(6);
g=cNode(7);
mtree(e,0,g); //e的做孩子为空,右孩子为g
mtree(d,e,f);//将e和f分别作为d的左右孩子
mtree(b,c,d);
mtree(a,b,0);
/*
二叉树的样子应该是下面的样子(不知道能不能正常显示):
a=1
/
b=2
/
c=3 d=4
/
e=5 f=6
g=7
*/
printf("中序遍历:");
ztr(a);puts("");//中序遍历,再输出一个回车 ,puts("");是换行
//
printf("先序遍历:");
xtr(a);puts("");
//
printf("后序遍历:");
htr(a);puts("");
system("pause");
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net