数据结构 二叉树的线索存储
【摘要】 #include <stdio.h>#include <stdlib.h>#include <iostream.h> #define OK 1#define ERROR 0#define OVERFLOW -2 typedef char TElemType;typedef enum {Link,Thread} PointerTag...
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <iostream.h>
-
-
-
#define OK 1
-
#define ERROR 0
-
#define OVERFLOW -2
-
-
-
typedef char TElemType;
-
typedef enum {Link,Thread} PointerTag;
-
-
typedef struct BiThrNode
-
{
-
TElemType data;
-
struct BiThrNode *lchild,*rchild;
-
PointerTag LTag;
-
PointerTag RTag;
-
}BiThrNode, *BiThrTree;
-
-
-
BiThrTree pre;
-
-
void Create_BiThrTree(BiThrTree &T)
-
{
-
TElemType ch;
-
cin >> ch;
-
if (ch == '#')
-
{
-
T = NULL;
-
}
-
else
-
{
-
T = (BiThrTree)malloc(sizeof(BiThrNode));
-
if (!T)
-
{
-
exit(OVERFLOW);
-
}
-
T->data = ch;
-
Create_BiThrTree(T->lchild);
-
if (T->lchild)
-
{
-
T->LTag = Link;
-
}
-
Create_BiThrTree(T->rchild);
-
if (T->rchild)
-
{
-
T->RTag = Link;
-
}
-
}
-
}
-
-
-
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)
-
{
-
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
-
{
-
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 InOrderTraverse_Thr(BiThrTree T)
-
{
-
BiThrTree p;
-
p = T->lchild;
-
while (p != T)
-
{
-
while (p->LTag == Link)
-
{
-
p = p->lchild;
-
}
-
printf("%c",p->data);
-
while (p->RTag == Thread && p->rchild != T)
-
{
-
p = p->rchild;
-
printf("%c",p->data);
-
}
-
p = p->rchild ;
-
}
-
return OK;
-
}
-
-
-
-
int main()
-
{
-
BiThrTree T,H;
-
Create_BiThrTree(T);
-
InOrderThreading(H,T);
-
InOrderTraverse_Thr(T);
-
printf("\n");
-
return 0;
-
}
文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq523176585/article/details/17249281
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）