|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
//线索存储标志位
//link(0):表示是指向左右孩子的指针
//thread(1):表示指向前驱后继的线索
typedef enum {Link, Thread} PointerTag;
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild,*rchild;
PointerTag ltag;
PointerTag rtag;//左右线索的标志
}BiThrNode, *BiThrTree;
//全局变量,始终指向刚刚访问的节点
BiThrTree pre;
//创建一颗二叉树(前序遍历)
CreateBiThrTree(BiThrTree *T)//T根节点
{
char c;
scanf("%c\n", &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);
}
}
/*
//访问二叉树结点的具体操作
visit(char c, int level)
{
printf("%c位于第%d层\n", c, level);
}
*/
//遍历二叉树(中序遍历线索化)
InThreading(BiThrTree T)
{
if(T)
{
InThreading(T->lchild);//递归左孩子
if(!T->lchild) //如果没有左孩子,设置ltag为Thread ,并把lchild指向上一个节点
{
T->ltag = Thread;
T->lchild = pre;
}
if (!pre->rchild)//上一个节点右边无孩子,设置其有指针
{
pre->rtag = Thread;
pre->rchild = T;//全局变量保存
}
if(!T->rchild) //如果没有右孩子,设置ltag为Thread ,并把lchild指向上一个节点
{
T->rtag = Thread;
T->rchild = pre;
}
if (!pre->lchild)//上一个节点zuo边无孩子,设置其有指针
{
pre->ltag = Thread;
pre->lchild = T;
}
pre = T;//继续下一个节点访问
InThreading(T->rchild);//递归右孩子线索化
}
}
//pre头指针赋予
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 P,T = NULL;
CreateBiThrTree(&T);
InOrderThreading(&P,T);
return 0;
}
|
-
输入数字,程序不执行下一步
|