www.pudn.com > gc.rar > GC_861.C

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