学步园

转自：http://blog.csdn.net/flying0033/article/details/6937477

后序线索二叉树的线索化有些麻烦：

1：若节点是二叉树的根，则后继为空；

2：若节点X是双亲的右孩子或者是双亲的左孩子且双亲没有右子树，则后继为双亲节点；

3：若双亲有左孩子而且双亲有右孩子，则后继为双亲右子树上面按后序遍历列出的第一个节点。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef enum{Link,Thread} PointTag;
typedef char Element;
typedef int Status;
typedef struct Node{
	Element data;
	struct Node* left;  //指向左孩子
	struct Node* right; //指向右孩子
	PointTag Ltag;   //左右标志
	PointTag Rtag;
}BitNode,*BitTree;
Status visit(Element e);
Status CreateTree(BitTree *T);
void InThreading(BitTree T);
void InOrderThreading(BitTree *H,BitTree T);
void InOrderTraverse_Thr(BitTree L);


BitTree pre;
Status visit(Element e)
{
	printf("%c ",e);
	return OK;
}
Status CreateTree(BitTree *T) //前序创建二叉树
{
	Element ch;
	scanf("%c",&ch);
	if(ch == '#')
		(*T) = NULL;
	else
	{
		(*T) = (BitTree)malloc(sizeof(BitNode));
		if(!(*T))
			exit(OVERFLOW);
		(*T)->data = ch;
		(*T)->Ltag = Link;
		(*T)->Rtag = Link;
		CreateTree(&(*T)->left);
		CreateTree(&(*T)->right);
	}
	return OK;
}
void InThreading(BitTree p) //后序线索二叉树
{
	if(p)
	{
		InThreading(p->left);
		InThreading(p->right);
		if(!p->left)
		{
			p->left = pre;
			p->Ltag = Thread;
		}
		if(!pre->right)
		{
			pre->right = p;
			pre->Rtag = Thread;
		}
		pre = p;
	}
}
void InOrderThreading(BitTree *H,BitTree T) //创建头节点,后序线索二叉树
{
	(*H) = (BitTree)malloc(sizeof(BitNode));
	if(!(*H))
		exit(OVERFLOW);
	(*H)->right = (*H);
	(*H)->Rtag = Link;
	if(!T)
	{
		(*H)->left = (*H);
		(*H)->Ltag = Link;
	}
	else
	{
		pre = (*H);
		(*H)->left = T;
		(*H)->Ltag = Link;
		InThreading(T);
		(*H)->right = pre;
	}
}
BitTree Parent(BitTree Thr,BitTree p)  //取得节点的父节点
{
	BitTree temp = Thr;
	if(temp->left == p)
		return temp;
	else
	{
		temp = temp->left;
		while(temp->left != p && temp->right != p)
		{
			if(temp->Rtag == Link)
				temp = temp->right;
			else
				temp = temp->left;  //有左孩子去左孩子,没有左孩子,去前驱;
		}
	}
	return temp;
}
void InOrderTraverse_Thr(BitTree Thr)
{
	BitTree temp = Thr->left;
	BitTree par = NULL;
	while(TRUE)
	{
		while(temp->Ltag == Link)
			temp = temp->left;
		if(temp->Rtag == Link)
			temp = temp->right;
		else
			break;
	}
	while(temp != Thr)
	{
		visit(temp->data);
		par = Parent(Thr,temp);  //获得节点temp的父节点
		if(par == Thr) //若父节点是Thr则节点temp为根节点,无后继
			temp = Thr;
		else if(par->Rtag == Thread || temp == par->right) //无右兄弟的左节点或是右儿子
			temp = par;
		else				//节点temp是左孩子,且有右兄弟
		{
			while(par->Rtag == Link)
			{
				par = par->right;
				while(par->Ltag == Link)
				{
					par = par->left;
				}
			}
			temp =par;
		}
	}
}
int main()
{
	BitTree H,T;
    printf("请输入前序二叉树的数据,例('ABDH##I##EJ###CF##G##')\n");
    CreateTree(&T);
    InOrderThreading(&H,T);
    InOrderTraverse_Thr(H);
    return 0;
}