btreebl.c

用树的层号表示生成一棵树

#include<stdio.h>
#include<malloc.h>
#define MAXM 10
#define MAXN 100
struct node
{
	int lev;
	char data;
	struct node *child[MAXM];
	struct node *parent;
};
typedef struct node NODE;
NODE *t;
typedef struct dnode 
{
	int lev;
	char data;
}DNODE;
DNODE a[MAXN];
int m,n;
NODE *lev_tree(a,m,n)     //用树的层号表示生成一棵树
DNODE a[];
int m,n;
{
	int i,j;
	NODE *root,*p,*q;
	if(n<1)return(NULL);
	root=(NODE *)malloc(sizeof(NODE));
	root->lev=a[0].lev;
	root->data=a[0].data;
	for(i=0;i<m;i++)
		root->child[i]=NULL;
	root->parent=NULL;
	p=root;
	for(i=1;i<n;i++)
	{
		q=(NODE *)malloc(sizeof(NODE));
		q->lev=a[i].lev;
		q->data=a[i].data;
		for(j=0;j<m;j++)
			q->child[j]=NULL;
		while(q->lev<=p->lev)
			p=p->parent;
		q->parent=p;
		j=-1;
		while(p->child[++j]!=NULL);
		p->child[j]=q;
		p=q;
	}
	return(root);
}
void r_preorder(t,m)       //树的前序遍历的递归算法
NODE *t;
int m;
{
	int i;
	if(t!=NULL)
	{
		printf("The child of %c is :\t",t->data);
		for(i=0;i<m&&t->child[i]!=NULL;i++)           //打印各个结点的孩子结点值
			printf("%c",t->child[i]->data);
		printf("\t");
		printf("The node is:\t%c\n",t->data);
		for(i=0;i<m;i++)                             //打印前序遍历的结点值
			r_preorder(t->child[i],m);
	}
}
void s_preorder(t,m)                    //树的前序遍历的非递归算法
NODE *t;
int m;
{
	NODE *s[100];
	int top,i;
	if(t==NULL)return;
	s[0]=t;
	top=1;
	while(top>0)
	{
		printf("The stack is:\t");
		for(i=0;i<top;i++)              //打印尚未遍历完的子树的根结点值
			printf("%c",s[i]->data);
		printf("\t");
		t=s[--top];
		printf("The node is:\t%c\n",t->data);
		for(i=m-1;i>=0;i--)              //打印前序遍历的结点值
			if(t->child[i]!=NULL)
				s[top++]=t->child[i];
	}
}
void main()
{

	DNODE t[MAXN];
	NODE *x;
	int i;
	printf("Please enter the times of the tree:m=");        //树的次数
	scanf("%d",&m);
    printf("Please enter the size of the array:n=");        //树中的结点数
	scanf("%d",&n);
	printf("Now,please create the tree:\n");                //在存贮数组中输入各结点对应的层号
    for(i=0;i<n;i++)
		scanf("%d",&t[i].lev);
	getchar();                //因为下边要输入字符，不能将回车当作字符，用此函数接收回车字符
	for(i=0;i<n;i++)          //输入结点的值 
	{
		printf("input the data %d:\n",i+1);
        scanf("%c",&t[i].data);
		getchar();            //避免将回车符当作结点字符
	}
	printf("The tree is:\n");
	x=lev_tree(t,m,n);
	r_preorder(x,m);
	printf("\n");
	s_preorder(x,m);
	printf("\n");
}