ACM模版
线索二叉树
typedef char ElemType;
typedef enum
{
Link, Thread
} PointerTag;
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild, *rchild;
PointerTag ltag;
PointerTag rtag;
} BiThrNode, *BiThrTree;
BiThrTree pre;
void CreateBiThrTree(BiThrTree *T)
{
char c;
scanf("%c", &c);
if (' ' == c)
{
*T = NULL;
}
else
{
*T = (BiThrNode *)malloc(sizeof(BiThrNode));
(*T)->data = c;
(*T)->ltag = Link;
(*T)->rtag = Link;
CreateBiThrTree(&(*T)->lchild);
CreateBiThrTree(&(*T)->rchild);
}
return ;
}
void InThreading(BiThrTree T)
{
if (T)
{
InThreading(T->lchild);
if (!T->lchild)
{
T->ltag = Thread;
T->lchild = pre;
}
if (!pre->rchild)
{
pre->rtag = Thread;
pre->rchild = T;
}
pre = T;
InThreading(T->rchild);
}
return ;
}
void InOrderThreading(BiThrTree *p, BiThrTree T)
{
*p = (BiThrTree)malloc(sizeof(BiThrNode));
(*p)->ltag = Link;
(*p)->rtag = Thread;
(*p)->rchild = *p;
if (!T)
{
(*p)->lchild = *p;
}
else
{
(*p)->lchild = T;
pre = *p;
InThreading(T);
pre->rchild = *p;
pre->rtag = Thread;
(*p)->rchild = pre;
}
return ;
}
void visit(char c)
{
std::cout << c;
return ;
}
void InOrderTraverse(BiThrTree T)
{
BiThrTree p;
p = T->lchild;
while (p != T)
{
while (p->ltag == Link)
{
p = p->lchild;
}
visit(p->data);
while (p->rtag == Thread && p->rchild != T)
{
p = p->rchild;
visit(p->data);
}
p = p->rchild;
}
std::cout << '\n';
return ;
}
int main()
{
BiThrTree P, T = NULL;
CreateBiThrTree(&T);
InOrderThreading(&P, T);
std::cout << "中序遍历输出结果为: ";
InOrderTraverse(P);
return 0;
}