#define _CRT_SECURE_NO_WARNINGS 1;
#include <stdio.h>
#include <stdlib.h>
//为啥需要线索二叉树? 因为浪费空间,遍历时需要叶子节点左右都为NULL, 中序遍历可以节约节点空间
typedef char ElemType;
//线索存储标志位
//Link(0)表示指向左右孩子的指针
//Thread(1)表示指向前驱后继的线索
typedef enum{Link,Thread}PointerTag;
typedef struct BiThrNode
{
char data;
struct BiThrNode* lchild, * rchild;
PointerTag ltag, 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);
}
}
//中序遍历线索化
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;
}
InThreading(T->rchild);
}
}
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;
}
}
int main()
{
BiThrTree T,p=NULL ;
CreateBiThrTree(T);
InOrderThreading(p, T);
}
已经定义T,还是报错很不理解。
新手在为期末 数据结构发愁呜呜呜
|