gc_862.c

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

# include <stdio.h>
# include <stdlib.h>
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);
}