#include <stdio.h>
#include <stdlib.h>
typedef enum PointerTag{Link, Thread};
typedef struct BiThrNode
{
int data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;
int createBinaryTree(BiThrTree &T) //线索二叉树建立
{
int ch;
scanf("%d", &ch);
if(ch != 0)
{
T = (BiThrTree)malloc(sizeof(BiThrNode));
T->data = ch;
printf("请输入%d的左结点，无则输入0\n",ch);
createBinaryTree(T->lchild);//循环嵌套，到0为止
printf("请输入%d的右结点，无则输入0\n",ch);
createBinaryTree(T->rchild);//循环嵌套，到0为止
}
else
{
T = NULL;
}
return 0;
}
int InTreading(BiThrTree T, BiThrTree &pre) //中序线索建立 内
{
if(T != NULL)
{
InTreading(T->lchild, pre);
if(T->lchild == NULL){ T->LTag = Thread; T->lchild = pre;}
else{ T->LTag = Link;}
if(pre->rchild == NULL){ pre->RTag = Thread; pre->rchild = T;}
else{ T->RTag = Link;}
pre = T;
InTreading(T->rchild, pre);
}
return 0;
}
int InOrderThreading(BiThrTree & Thrt, BiThrTree T) //中序线索建立 外
{
BiThrTree pre;
Thrt= (BiThrTree)malloc(sizeof(BiThrNode));
Thrt->LTag = Link; Thrt->RTag = Thread;
Thrt->rchild = Thrt;
if(T == NULL) Thrt->lchild = Thrt;
else
{
Thrt->lchild = T; pre = Thrt;
InTreading(T, pre);
pre->rchild = Thrt; pre->RTag = Thread;
Thrt->rchild = pre;
}
return 0;
}
int visit(int data)
{
printf("%d ", data);
return 0;
}
int InOrderTraverse_Thr(BiThrTree T) //中序非递归线索二叉树遍历
{
BiThrTree 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;
}
return 0;
}
int main()
{
BiThrNode TT;
BiThrTree T, Thrt;
createBinaryTree(T);
InOrderThreading(Thrt, T);
InOrderTraverse_Thr(Thrt); //遍历的时候要带上头结点
return 0;
}
网友评论