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

# include  
# include  
typedef struct node2 {  /*标准存储结构*/ 
	char data; 
	struct node2 *lchild; 
	struct node2 *rchild; 
}TNODE2; 
 
 
//TNODE2 *  可表示根指针的类型 
/*函数,建立二叉树*/ 
void CreateBinTree(TNODE2 **T) 
{ 
	/*构造二叉链表,T是指向根指针的指针,故修改*T就是修改了实参(根指针)本身*/ 
	char ch; 
	if ((ch = getchar()) == ' ') 
		*T = NULL;   //读入空格,将相应指针置空 
	else {   //读入非空格 
		*T = (TNODE2 *)malloc(sizeof(TNODE2));   //生成结点 
		(*T)->data = ch; 
		CreateBinTree(&(*T)->lchild);          //构造左子树 
		CreateBinTree(&(*T)->rchild);           //构造右子树 
	} 
} 
 
 
 
 
 
/*函数,前序遍历*/ 
void re_preorder(TNODE2 *t) 
{ 
	if(t != NULL)  {             /*非空二叉树*/ 
		printf("%c",t->data); 
		re_preorder(t->lchild); 
		re_preorder(t->rchild); 
	} 
} 
 
/*函数,中序遍历*/ 
void re_midorder(TNODE2 *t) 
{ 
	if (t != NULL)  {           /*非空二叉树*/ 
		re_midorder(t->lchild); 
		printf("%c",t->data); 
		re_midorder(t->rchild); 
	} 
} 
 
/*函数,后序遍历*/ 
void re_posorder(TNODE2 *t) 
{ 
	if (t != NULL) { 
		re_posorder(t->lchild); 
		re_posorder(t->rchild); 
		printf("%c",t->data); 
	} 
} 
 
/*函数,中序遍历(非递归,采用链接栈)*/ 
typedef struct snode {                      /*栈元类型*/ 
	TNODE2 * tnodept;                       /*栈结点为指向二叉树结点的指针*/ 
	struct snode *link;                     /*栈结点链接指针*/ 
}SNODE; 
void st_midorder(TNODE2 *t) 
{ 
	SNODE *top = NULL,                       /*栈顶指针*/ 
	       *p;                                /*工作变量*/ 
	while(t != NULL || top != NULL) {         /*二叉树未访问完,或栈非空*/ 
		while(t!=NULL) {                       /*一颗二叉树未访问完,循环*/ 
			/*根结点进栈*/ 
			p = (SNODE *)malloc(sizeof(SNODE)); 
			p->tnodept = t; 
			p->link = top; 
			top = p; 
			/*沿着左子树前进,将经过的结点依次进栈*/ 
			t=t->lchild; 
		} 
		if(top != NULL) {                     /*如栈非空*/ 
			t = top->tnodept;                   /*栈顶结点出栈*/ 
			p = top; 
			top = top->link; 
			free(p);                         /*释放栈顶结点的空间*/ 
			printf("%c",t->data);             /*访问根结点*/ 
			t=t->rchild;                        /*向右子树前进*/ 
		} 
	} 
} 
 
 
 
void main() 
{ 
	TNODE2 *root=NULL;          //二叉树的根 
	printf("首先建立二叉树\n"); 
	printf("请按照前序输入二叉树,子树为空就输入空格\n"); 
	printf("如以下序列:ABDH(NULL)(NULL)(NULL)EI(NULL)(NULL)(NULL)CF(NULL)(NULL)G(NULL)(NULL)"); 
	printf("就是以下形式,你所输入的对齐就可以了,注意最后还有两个空格:\nABDH   EI   CF  G  \n"); 
	CreateBinTree(&root); 
 
	printf("\n函数,前序遍历\n"); 
	/*函数,前序遍历	*/ 
	re_preorder(root); 
 
	/*函数,中序遍历*/ 
	printf("\n函数,中序遍历\n"); 
	re_midorder(root); 
 
	/*函数,后序遍历*/ 
	printf("\n函数,后序遍历\n"); 
	re_posorder(root); 
 
	/*函数,中序遍历(非递归,采用链接栈)*/ 
	printf("\n函数,中序遍历(非递归,采用链接栈)\n"); 
	st_midorder(root); 
}