线索二叉树

线性化：对一个非线性结构进行线性化操作，使得每个结点在这个线性序列中有且仅有一个直接前驱和直接后继。
方法：在每个结点上增加两个指针域fwd和bkwd，分别指示结点在任一次遍历序列时得到的前驱和后继信息。

LTag：0： lchild域指示结点的左孩子 1 ：lchild域指示结点的前驱；
RTag：0： rchild域指示结点的右孩子 1： rchild域指示结点的后继。

以这种结构构成的二叉链表作为二叉树的的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。
加上线索的二叉树称之为线索二叉树。
线索话：对二叉树以某种次序遍历使其变为线索二叉树的过程。
在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找到结点的后继直至其后继为空为止。

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

//输入是：abc##de#f##g###

typedef enum { Link, Thread } PointerTag; //Link==0 指针 Thread==1线索

typedef struct BinThrNode
{
	char data;
	struct BinThrNode *lchild, *rchild;
	PointerTag LTag, RTag;
}BinThrNode, *BinThrTree;
BinThrTree pre;

//'#'表示根节点
void createBinTree(BinThrTree &T){
	char ch;
	scanf_s("%c", &ch);
	if (ch == '#'){
		T = NULL;
	}
	else{
		if (!(T = (BinThrNode*)malloc(sizeof(BinThrNode)))){
			exit(0);
		}
		T->data = ch;
		printf("数据%c\n", T->data);
		createBinTree(T->lchild);
		createBinTree(T->rchild);
	}
}

void inThreading(BinThrTree p){
	if (p){
		inThreading(p->lchild);// 左子树线索化
		if (!p->lchild){       //前驱线索化
			p->LTag = Thread;
			p->lchild = pre;
		}
		else{
			p->LTag = Link;
		}
		if (!pre->rchild){      //后继线索化
			pre->RTag = Thread;
			pre->rchild = p;
		}
		else{
			pre->RTag = Link;
		}
		pre = p;
		inThreading(p->rchild); //右子树线索化
	}
}
int InOrderThreading(BinThrTree &Thrt, BinThrTree T){
	if (!(Thrt = (BinThrTree)malloc(sizeof(BinThrNode))))
		exit(-1);
	Thrt->LTag = Link;   //建立结点
	Thrt->RTag = Thread;
	Thrt->rchild = Thrt;   //右指针回退

	if (!T)
		Thrt->lchild = Thrt;  //若二叉树空，则左指针回退
	else{
		Thrt->lchild = T;
		pre = Thrt;
		inThreading(T);         //中序遍历进行中序线索化
		pre->rchild = Thrt;     //最后一个结点线索化
		pre->RTag = Thread;
		Thrt->rchild = pre; 
	}
	return 1;
}
int output_data(BinThrTree T){
	printf("\n%s\t%c\t%s", T->LTag == Link ? "Link" : "Thread", T->data, T->RTag == 0 ? "Link" : "Thread");
	return 1;
}
int InOrderTravese_Thr(BinThrTree T,int (*visit)(BinThrTree h)){
	BinThrTree p;
	p = T->lchild;
	while (p != T){
		while (p->LTag == Link)
			p = p->lchild;
		visit(p);
		while (p->RTag == Thread && p->rchild != T){
			p = p->rchild;
			visit(p);
		}
		p = p->rchild;
	}
	return 1;
}


int main(){
	BinThrTree T, Thrt;
	createBinTree(T);
	if (!InOrderThreading(Thrt, T)){
		return -1;
	}
	if (!InOrderTravese_Thr(Thrt,output_data)){
		return -1;
	}
	return 0;
}