gc_861.c

gc:高级程序员考试用书的c程序源文件

#include <stdio.h>
#include <stdlib.h>
# define M 4            //存储树的次数
/*树的标准存储结构*/
typedef struct tnode {
	char data;              /*树结点的数据信息*/
	struct tnode *child[M]; /*树结点的子结点指针*/
}TNODE;                     /*树结点的数据类型*/
TNODE *root;                /*树的根结点指针*/


/*这个存储结构我就不编程实现了*/
/*树的带逆存贮结构*/
typedef struct rtnode {
	char data;                  /*树结点的数据信息*/
	struct rtnode *child[M];    /*树结点的子结点指针*/
	struct rtonde *father;        /*父结点指针*/
}RTNODE;                        /*树结点的数据类型*/
RTNODE *r_root;                   /*树的根结点指针*/


/*函数,建立树*/
void Creat_tree(TNODE **T)    //TNODE *为根指针,这里要用到根指针的指针
{
	//int m=3;                 /*树的次数,初定义有每棵树四个孩子*/
	int i=0;
	char ch;
	if((ch = getchar()) == ' ')
		*T = NULL;             //读入空格,将相应指针置空*/
	else {  /*读入非空格*/
		*T = (TNODE *)malloc(sizeof(TNODE));          /*生成结点*/
		(*T)->data=ch;
		for (i=0; i<M; i++)
		Creat_tree(&((*T)->child[i]));
	}
}



/*函数,树的前序遍历(用递归实现)*/
void re_preorder(TNODE *t,int m)   /*t:树根指针         m:树的次数*/
{
	int i;
	if (t != NULL)  {
		printf("%c",t->data);            /*访问树结点*/
		for(i = 0; i<m; i++)               /*前序遍历各子树*/
			re_preorder(t->child[i],m);
	}
}


/*函数:前序遍历(用堆栈实现)*/
# define SN 100
void st_preorder(TNODE *t,int m)
{
	TNODE *s[SN];                       /*栈*/
	int top = 0,                        /*栈顶指针,初始时,为空栈*/
	    i;                             /*工作变量*/
	if(t==NULL) return;                 /*空指针情况,立即返回*/
	s[top++] = t;                       /*树的根结点指针进栈*/
	while (top > 0) {                   /*栈中有未处理的子树,继续循环*/
		t = s[--top];                   /*取出栈顶子树的根结点指针*/
		printf("%c",t->data);           /*访问子树的根结点*/
		/*子树的子树按逆序进栈,使它们以后能顺序出栈*/
		for(i = m-1; i>=0; i--)
			if(t->child[i] != NULL)
				s[top++] = t->child[i];
	}
}


/*函数,层次遍历*/
#define QN 100
int lev_order(TNODE *t,int m)
{
	TNODE *q[QN];
	TNODE *p;
	int head=0,                    /*下一个出队结点的存储下标*/
	tail=0,                        /*下一个进队结点的存贮下标*/
	i;                             /*工作变量*/
	q[tail++] = t;                 /*t 进队*/
	while (head != tail) {          /*队列非空*/
		p = q[head];                 /*取出队首结点*/
		head = (head+1)%QN;
		printf("%c",p->data);         /*访问队首结点*/
		for (i=0; i<m; i++)           /*被访问结点的子结点顺序入队*/
			if(p->child[i] != NULL)  {
				if((tail+1)%QN == head)return 0;
				q[tail]= p->child[i]; tail = (tail+1)%QN;
			}
	}
	return 1;
}



void main()
{
	//int m=3;
	TNODE *root=NULL;
	printf("建立树,次数为4,就是一颗树4个孩子\n");
	printf("按前序输入,没有的输入空格,  (用空格代替NULL)  \n");
	printf("例子: 如这样的一颗树,我用|代替空格,你要输入的时候把|换成空格就行了\n");
	printf("输入有些麻烦,你正确输入的话,刚好对齐\n");
	printf("ABE||||G||||H||||I||||CJ|||||||D|K||||L|||||F||||\n");
	Creat_tree(&root);
	/*前序遍历*/
	printf("\n");
	printf("前序遍历,用堆栈实现\n");
	st_preorder(root,M);


	printf("\n\n前序遍历,用递归算法实现\n");
	re_preorder(root,M);

	/*层次遍历*/
	printf("\n\n层次遍历,用队列实现\n");
	lev_order(root,M);
}