threadbinatree.c

根据广义表创建一棵二叉树

/* 
******************************************************************************************
*
*    功  能 ：二叉树的线索遍历 
*    作  者 ：林永表
*    日  期 ：2009-4-5
*
******************************************************************************************
*/


#include <stdio.h>
#include <stdlib.h>
#include "define.h"



/*1
*功   能：初始化二叉树
*参   数：hbt,二叉树结构指针的指针，指向根节点的指针的地址
*/
void initial_thread_btree(hbt)
ptr_thread_btree *hbt;
{
	*hbt=NULL;
	return;
}

/*2
*功   能：创建二叉树（根据数组a所指向的广义表字符串）
*参   数：无
*/
void creat_thread_btree(hbt)  //注意如果这个函数有参数，且是指针，则改变这个指针的内容时并
ptr_thread_btree *hbt;        //没有改变实参指针的值，所以要设参数，要设为指针的指针
{                               
	char ch_Y=0;                 //输入广义表错误时，接收是否要继续的信息

	ptr_thread_btree pbt;           //存树节点


	char_arry a={""};                 //接受客户端输入的广义表字符串
    INTEGER i=0;                 //遍历广义表字符串的下标
	INTEGER k=0;                 //设置标记，若为1，处理左子树；2，处理右子树

	ptr_thread_btree s[STACK_MAX_SIZE]; //栈s存储根节点及子根节点
	INTEGER top=-1;              //栈顶，若为1，栈空

	initial_thread_btree(hbt);      //初始化，注意应传入指针的指针，
	                              //不然初始化改变的只是指针的指向，并没有改变指针自己的内容
	                              //从空二叉树开始建立    
	
	printf("\n请输入要建立的二叉树的广义表:");
	scanf("%s",a);

	while('\0'!=a[i])
	{
		switch(a[i])
		{
		     case ' ':
				 break;          //空字符跳过
			 case '(':
				 if((STACK_MAX_SIZE-1)==top) //表明后面还会有数据，栈不能到顶了
				 {
					 printf("栈空间太小!");
					 exit(1);
				 }
				 top++;
				 s[top]=pbt;     //把最近创建的节点入栈
				 k=1;
				 break;
			 case ',':          //处理右子树
				 k=2;
				 break;
			 case ')':
				 if(-1==top)
				 {
					 printf("\n无法创建，栈为空了!\n");
					 exit(1);
				 }
				top--;          //返回上一层结点，相当于弹出栈顶元素。
				 break;
			 default :
				 pbt=(ptr_thread_btree)malloc(N*sizeof(ptr_thread_btree));
				 if(!pbt)
				 {
					 printf("\n内存分配失败!\n");
					 exit(1);
				 }
				 pbt->data=a[i]; //存入结点数据域，并置左右子树域指针为空
				 pbt->left=pbt->right=NULL;
				 if(NULL==*hbt)
				 {
					 *hbt=pbt;  //hbt保存主根结点
				 }
				 else
				 {
					 if(1==k)
						 s[top]->left=pbt; //让栈顶节点左子树指针指向当前创建结点
					 else 
						 if(2==k)
						 {
						 s[top]->right=pbt;//让栈顶节点右子树指针指向当前创建结点
						 }
						 else
						 {
							 system("cls");
							 printf("\n广义表输入有误，无法创建!\n\n");
							 printf("要继续吗?(y/n)");
							 getchar();
							 ch_Y=getchar();
							 if('y'==ch_Y||'Y'==ch_Y)//这种容错能力只能解决开始输入的两个为字母的
							 {                       //状况，因为输入的数组的开始一定是一个元素
								                     //跟一个‘（’,或者只有一个括号‘（’
								 free(*hbt);
								 *hbt=NULL;
								 free(pbt);
								 pbt=NULL;
								 creat_thread_btree(hbt);
								 k=3;  //设置正确输入后跳出循环的标识
							 }
							 else
							 {
								 exit(1);
							 }
						 }
				 }
				 break;
		}
		if(3==k) break;  //出现过输入广义表错误，则调用直到正确输入
		                 //后跳出循环，即不执行上次遗留的数组节点
		++i; //读广义表下一个字符
	}
	//return hbt;
}


/*3
*功   能：中序遍历线索化
*参   数：hbt，指向当前的根节点
*         pre，当前节点的前驱节点的地址，是一个指针的指针
*              开始递归时为空，
*/
void iner_thread(hbt,pre)
ptr_thread_btree hbt;
ptr_thread_btree *pre;                    //因为在在递归中用到的同一个指针，所以
{                                         //要得到上一次的指针值，应该用指针的地址
	if(NULL!=hbt)                         //传参
	{  
	    iner_thread(hbt->left,pre);       //递归中序遍历线索化左子树

		if(NULL==hbt->left)               //当前节点左子树空，则标志为1，
		{                                 //建立前驱线索
			hbt->ltag=1;
			hbt->left=*pre;
		}
		else
		{
			hbt->ltag=0;
		}

        if((NULL!=*pre)&&(NULL==((*pre)->right)))  //前驱节点不空且右子树不空，建立后继线索，
		{
			(*pre)->rtag=1;
			(*pre)->right=hbt;
		}
		else 
		{
			hbt->rtag=0;           //当前节点右子树不为空!
		}
	  	
		*pre=hbt;   //中序遍历下一个节点
	    
		iner_thread(hbt->right,pre);     //递归中序遍历线索化右子树
	}
}

/*4
*功   能：遍历中序线索化后的二叉树
*参   数：hbt，指向根节点
*/
void iner_thread_btree(hbt)
ptr_thread_btree hbt;
{
	INTEGER k=1; //设置标志，为1，表示当前节点第一次访问，为2，表示第二次访问

	ptr_thread_btree pbt=NULL;

	pbt=hbt;

	while(NULL!=pbt)
	{
		while((0==pbt->ltag)&&(1==k))  //第一次访问且有左子树，访问其左子树
		{
			pbt=pbt->left;
		}

		printf("%c ",pbt->data);  //打印当前节点
	//	printf("\npbt->ltag=%d,pbt->rtag=%d\n",pbt->ltag,pbt->rtag);

		if(1==(pbt->rtag))       //当前节点无右子树，则为第二次访问   
		{
			pbt=pbt->right;
			k=2;
		}
		else                    //当前节点存在右子树，为第一次访问
		{
			pbt=pbt->right;
			k=1;
		}                        
	} 
	printf("\n\n");
}

//这里有点小问题，就是当换成： 
/*       

        if(0==(pbt->rtag))       
		{
			pbt=pbt->right;
			k=1;
		}
		else                  
		{
			pbt=pbt->right;
			k=2;
        }
*/
//任何一个根节点的右子树的左孩子无法输出，比如一子树为a(b,d(e,f))
//那么节点e并没有输出，其他的能正常输出，这个问题的出现，
//说明，子树的根节点a的右指标rtag被置成1了，所以才会跳过
//if这一步而到else,这样一来就肯定不能输出e了。那么换成上面的
//那样就可以正确得到结果了。



/*5
*功   能：前序遍历线索化
*参   数：hbt，指向当前的根节点
*         pre，当前节点的前驱节点的地址，是一个指针的指针
*              开始递归时为空，
*/
void pre_thread(hbt,pre)
ptr_thread_btree hbt;
ptr_thread_btree *pre;   
{
}


/*6
*功   能：遍历前序线索化后的二叉树
*参   数：hbt，指向根节点
*/
void pre_thread_btree(hbt)
ptr_thread_btree hbt;
{
}



/*7
*功   能：后序遍历线索化
*参   数：hbt，指向当前的根节点
*         pre，当前节点的前驱节点的地址，是一个指针的指针
*              开始递归时为空，
*/
void afer_thread(hbt,pre)
ptr_thread_btree hbt;
ptr_thread_btree *pre;   
{
}


/*6
*功   能：遍历后序线索化后的二叉树
*参   数：hbt，指向根节点
*/
void afer_thread_btree(hbt)
ptr_thread_btree hbt;
{
}