[数据结构与算法]数据结构-----------树和二叉树(线索二叉树)

#include<iostream>
using namespace std;
typedef struct BiTreeNode
{
	char data;
	struct BiTreeNode *lchild;
	struct BiTreeNode *rchild;
	int LTag,RTag;
}BiTree;

BiTree *pre;

void CreatNode1(BiTree *&T)  //先序遍历建立二叉链表 
{
	char ch;
	cin>>ch;
	if(ch=='#')
		T=NULL;
	else
	{
		T=new BiTree;
		T->data=ch;
		CreatNode1(T->lchild);
		CreatNode1(T->rchild);
	}
}


void CreatBiTree1(BiTree *&T)   //中序线索化 
{
	if(T)
	{
		CreatBiTree1(T->lchild);
		if(!T->lchild)
		{
			T->LTag=1;
			T->lchild=pre;
		}
		else T->LTag=0;
		if(!pre->rchild)
		{
			pre->RTag=1;
			pre->rchild=T;
		}
		else pre->RTag=0;
		pre=T;
		CreatBiTree1(T->rchild);
	}
}

void Threading(BiTree *&Thrt,BiTree *&T)
{
	Thrt=new BiTree;
	Thrt->LTag=0;
	Thrt->RTag=1;
	Thrt->rchild=Thrt;
	if(!T)
		Thrt->lchild=Thrt;
	else
	{
		Thrt->lchild=T;
		pre=Thrt;
		CreatBiTree1(T);
		pre->rchild=Thrt;
		pre->RTag=1;
		Thrt->rchild=pre; 
	}
}

void Traverse(BiTree *T)   //遍历线索二叉树 
{
	BiTree *p;
	p=T->lchild;
	while(p!=T)
	{
		while(p->LTag==0)
			p=p->lchild;
		cout<<p->data<<" ";
		while(p->RTag==1&&p->rchild!=T)
		{
			p=p->rchild;
			cout<<p->data<<" ";
		}
		p=p->rchild;
	}
} 

int main()
{
	BiTree *T;
	BiTree *Thrt;
	cout<<"先序遍历建立二叉链表"<<endl;
	CreatNode1(T);
	cout<<"将二叉树线索化."<<endl;
	Threading(Thrt,T);
	cout<<"线索二叉树显示如下:"<<endl;
	Traverse(Thrt);
	return 0;
}

改代码为二叉树的线索化，增加Ltag和Rtag来标准线索，来获取左右孩子或父辈。