c++ 线索二叉树的问题
/*1、线索二叉树的创建和遍历操作算法的实现
编程实现二叉树的线索链表存储表示的基本操作，这些基本操作包括：
线索二叉树的创建、线索二叉树的中序遍历算法的实现。要求对程序中的一些关键语句要有注释，
并能够进行简单的输入输出验证。
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OVERFLOW 0
#define ERROR 0
#define TURE 1
#define OK 1
typedef char TElemType;
typedef int Status;
typedef enum PointerTag
{
Link,Thread
};
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;//左右孩子指针
PointerTag LTag,RTag;//左右标志
}BiThrNode, *BiThrTree;
//二叉树的创建
Status CreateBiThrTree(BiThrTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiThrNode *)malloc(sizeof(BiThrNode))))
exit (OVERFLOW);
T->data=ch;
T->LTag=Link;//杨梦晨
T->RTag=Link;//
CreateBiThrTree(T->lchild);
CreateBiThrTree(T->rchild);
}
return OK;
}
Status InThreading(BiThrTree p,BiThrTree &pre)
{
if(p)
{
InThreading(p->lchild,pre);
if(!p->lchild)
{
p->LTag=Thread;
p->lchild=pre;
}
if(!pre->rchild)
{
pre->RTag=Thread;
pre->rchild=p;
}
pre=p;
InThreading(p->rchild,pre);
}
return 0;
}
//中序遍历二叉树，并将其中序线索化，Thrt指向头结点
Status InorderThreading(BiThrTree &Thrt,BiThrTree T)
{
BiThrTree pre;
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) //BiThrTree =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);
pre->rchild=Thrt; pre->RTag=Thread;
Thrt->rchild=pre;
}
printf("已经线索化!\n");
return 0;
}
//Visit是对数据元素操作的应用函数
Status Visit(TElemType e)
{
printf("%c",e);
return OK;
}
//线索二叉树的中序遍历
Status InOrderTraverse_Thr(BiThrTree T,Status(*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 main()
{
BiThrTree T;
BiThrTree Thrt;
printf("用先序的方法创建一个二叉树:\n");
CreateBiThrTree(T);
InorderThreading(Thrt,T);
printf("线索二叉树的中序遍历输出:\n");
InOrderTraverse_Thr(T,Visit);
printf("\n");
return 0;
}
不能输出头结点，怎么改啊
