#include <iostream>
usingnamespace std;
typedef enum PointerTag {Link,Thread}; //Link==0,Thread==1;线索
typedef struct treenode
{
struct treenode *left;
char
data;
struct treenode *right;
PointerTag
Ltag,Rtag; //左右标志
}Treenode,* Treep;
Treep pre;
/*全局变量，用于二叉树的线索化*/
//初始化二叉树
void init_tree(Treep &root)
{
root=NULL;
cout<<"初始化成功!"<<endl;
}
//创建二叉树
void creat_tree(Treep &rt)
{
char ch;
ch=getchar();
if(\'#\'==ch)
rt=NULL;
else
{
rt=(Treep )malloc(sizeof(Treenode));
rt->data=ch;
rt->Ltag=Link;
rt->Rtag=Link;
creat_tree(rt->left);
//构造左子树
creat_tree(rt->right); //构造右子树
}
}
//前序遍历二叉树
void pre_order(Treep &rt)
{
if(rt!=NULL)
{
cout<<rt->data<<"";
pre_order(rt->left);
pre_order(rt->right);
}
}
//前序线索化二叉树
void preThreading(Treep &p)
{
if(p)
{
if(!p->left)
{
p->Ltag=Thread;
p->left=pre;
//前继线索
}
if(!pre->right)
{
pre->Rtag=Thread;
pre->right=p;
//后继线索
}
pre=p;
if(Link==p->Ltag)
preThreading(p->left);
if(Link==p->Rtag)
preThreading(p->right);
}
}//InThreading
Treep preorderThreading(Treep &rt)
{
Treep thrt;
if( !(thrt = (Treep) malloc (sizeof(Treenode) ) ) )
exit(1);
thrt->Ltag=Link;
thrt->Rtag=Thread; //建头结点
thrt->right=thrt; //右指针回指
if(!rt)
thrt->left=thrt; //若二叉树空，则左指针回指
else
{
thrt->left=rt;
pre=thrt;
preThreading(rt);
//前序遍历进行中序线索化
pre->right=thrt;
//最后一个节点处理
pre->Rtag=Thread;
thrt->right=pre;
}
return thrt;
}
//前序遍历线索二叉树
void preorderTraver(Treep &thrt)
{
Treep p;
p=thrt->left;
while(p!=thrt)
{
cout<<p->data<<"";
if(Link==p->Ltag)
p=p->left;
else
p=p->right;
}
}
int main()
{
Treep root;
init_tree(root);
//初始化树
cout<<"请输入二叉树,空值以#代表，输完要以Ctrl+Z表示结束，否则影响下个树的创建!:"<<endl;
creat_tree(root);
//创建二叉树
//前序遍历二叉树
cout<<"前序遍历序列是:"<<endl;
pre_order(root);
cout<<endl;
Treep thrt;
thrt=preorderThreading(root);
preorderTraver(thrt);
cout<<endl;
return0;
}