中序线索二叉树

中序线索二叉树
含n个结点的二叉树中，有n+1个空指针，线索二叉树将结点间前驱后继的关系存放在n+1个空指针中；使用递归的方式中序访问各个结点，使用全局变量pre标记当前结点的前驱结点，用visit函数将他们联系起来，用结构体中的tag标记左右孩子是结点还是线索。

#include 
using namespace std;

typedef struct ThreadNode{
	char data;
	ThreadNode *lchild=NULL,*rchild=NULL;
	int ltag,rtag;
}ThreadNode,*ThreadTree;

void InitBitNode(ThreadTree &head){
	ThreadNode *a=new ThreadNode;
	head=a;
	a->data='A';
	ThreadNode *b=new ThreadNode;
	b->data='B';
	a->lchild=b;
	ThreadNode *c=new ThreadNode;
	c->data='C';
	a->rchild=c;
	ThreadNode *g=new ThreadNode;
	g->data='G';
	c->rchild=g;
	ThreadNode *d=new ThreadNode;
	d->data='D';
	b->lchild=d;
	ThreadNode *e=new ThreadNode;
	e->data='E';
	b->rchild=e;
}//创建一个二叉树

void visit(ThreadTree &head,ThreadTree &pre){
	if(head->lchild==NULL){
		head->lchild=pre;
		head->ltag=1;
	}
	if(pre!=NULL&&pre->rchild==NULL){
		pre->rchild=head;
		pre->rtag=1;
	}
	pre=head;
}//访问每个具体的结点 

void InThread(ThreadTree &head,ThreadTree &pre){
	if(head!=NULL){
		InThread(head->lchild,pre);
		visit(head,pre);
		InThread(head->rchild,pre);
	}
}//递归遍历二叉树 

void CreateInthread(ThreadTree &head){
	ThreadTree pre=NULL;
	if(head!=NULL){
		InThread(head,pre);
		pre->rchild=NULL;
		pre->rtag=1;
	}
}//中序线索二叉树 

void PrintTree(ThreadTree &head){
	if(head!=NULL){
		PrintTree(head->lchild);
		cout<data<<" ";
		PrintTree(head->rchild);
	}
}//递归中序打印二叉树 

int main(void){
	ThreadTree head;
	InitBitNode(head); 
	PrintTree(head); 
	CreateInthread(head);
	cout<lchild->rchild->rtag==1) 
		cout<lchild->rchild->rchild->data<