学步园

//函数功能：创建一棵二叉树，将其线索化，并非递归不设栈中序输出
//注意：ltag、rtag为0指向孩子节点为1指向前驱或后继，此程序未实现指向孩子节点时将标志置0；
#include <stdio.h>
#include<malloc.h>
#include <string.h>

struct bithrnode{
	char data;
	struct bithrnode *lchild,*rchild;
	int ltag,rtag;//设置初值0，假设所有节点无线索;??? 结构体中不能预设初值
};//定义线索二叉树的节点结构

creat_tree(struct bithrnode* *t) //创建二叉树，参数为指向指向节点指针的地址
{
	char c;
	c=getchar();
	if(c==' ') *t=NULL;
	else{
		*t=(struct bithrnode *)malloc(sizeof(struct bithrnode));
		(*t)->data=c;
		creat_tree(&(*t)->lchild);
		creat_tree(&(*t)->rchild);
	}
}
//递归先序打印节点
print_tree(struct bithrnode *t)
{
	if(t){
		putchar(t->data);
		print_tree(t->lchild);
		print_tree(t->rchild);
	}
}
//线索化函数
void inthreading(struct bithrnode * *t,struct bithrnode * *pre)
{
	if(*t)
	{
		inthreading(&(*t)->lchild,&(*pre)); //左子树线索化
		
		//对一个节点访问时线索化当前节点和前驱节点（如果可以线索的话）
		if(!(*t)->lchild){
			(*t)->ltag=1;(*t)->lchild=*pre; //lchild==NULL,前驱线索
		}
		
		if(!(*pre)->rchild){
			(*pre)->rtag=1;(*pre)->rchild=*t;//rchild==NULL,后继线索
		}
		
		*pre=*t;//pre始终指向刚刚访问过的节点
		
		inthreading(&(*t)->rchild,&(*pre));//右子树线索化
	}
}

//中序遍历二叉树，并将其线索化
struct bithrnode *inorderthreading(struct bithrnode *t1)
{
	struct bithrnode *thr,*pre;
	thr=(struct bithrnode*)malloc(sizeof(struct bithrnode));
	
	thr->rchild=thr;/*thr->ltag=0*/;thr->rtag=1;//0指孩子，1为线索
	
	if(!t1) thr->lchild=thr;	//若为空树，头结点的lchild指向自身
	else{
		thr->lchild=t1; //指向首元结点 
		pre=thr;
		
		inthreading(&t1,&pre);//线索化函数
		
		pre->rchild=thr;//最后一个节点线索化
		pre->rtag=1;
		thr->rchild=pre;
	}
	return thr;
}

in_traverse(struct bithrnode *t) //非递归中序遍历，输出节点
{
	struct bithrnode *p;
	p=t->lchild;
	while(p!=t)//空树或是遍历结束时p==t
	{
		while(p->ltag!=1) p=p->lchild;//找到第一个叶子节点
		putchar(p->data);

		while(p->rtag==1&&p->rchild!=t)
		{
			p=p->rchild;//访问后继节点
			putchar(p->data);
		}
		p=p->rchild;
	}
}
main()
{
	struct bithrnode *t;
	creat_tree(&t);
	t=inorderthreading(t);//线索化
	if(!t) printf("the tree is empty!\n");

	in_traverse(t);//中序遍历输出

	//print_tree(t);//先序递归输出
}