二叉樹の非再帰的な中間巡回(二叉スレッド記憶構造)
2199 ワード
# include
# include
# include
# include
# define OK 1
# define ERROR 0
# define OVERFLOW -1
typedef char TElemType;
typedef enum PointerTag { Link, Thread };
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre;
void InThreading(BiThrTree p)
{
if (p)
{
InThreading(p->lchild);
if (!p->lchild)
{
p->LTag = Thread;
p->lchild = pre;
}
if (! pre->rchild)
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);
}
}
int InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{
Thrt = (BiThrTree) malloc (sizeof (BiThrNode));
if (!Thrt)
exit (OVERFLOW);
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt;
if (!T)
Thrt->lchild = Thrt;
else
{
Thrt->lchild = T;
pre = Thrt;
InThreading(T);
pre->rchild = Thrt;
pre->RTag = Thread;
Thrt->rchild = pre;
}
return OK;
}
int CreateBiThrTree(BiThrTree &T)
{
TElemType ch;
cin>>ch;
if (ch == '#')
T = NULL;
else
{
T= (BiThrTree) malloc (sizeof (BiThrNode));
T->data = ch;
CreateBiThrTree(T->lchild);
if (T->lchild)
T->LTag = Link;
CreateBiThrTree(T->rchild);
if (T->rchild)
T->RTag = Link;
}
return OK;
}
int InOrderTraverse_Thr(BiThrTree T,int (*Visit)(TElemType e))
{
BiThrTree p;
p = T->lchild ;
while (p != T)
{
while (p->LTag == Link)
p = p->lchild ;
if (! Visit(p->data))
return ERROR;
while (p->RTag == Thread && p->rchild != T)
{
p = p->rchild ;
Visit(p->data);
}
p = p->rchild ;
}
return OK;
}
int Print(TElemType e)
{
cout<
:
・