Question

线索二叉树的应用 编写一个程序！

线索二叉树的应用
基本要求：
（1）实现中序线索二叉树建立
（2）在中序线索二叉树上实现自前向后和自后向前的递推遍历
急！要是过期就不行了！
数据

Answer 1

//二叉树的二叉线索存储表示
#include<stdio.h>
#include<stdlib.h>

typedef enum PointerTag{Link,Thread}pointerType;//Link==0,指针,Thread==1,线索
typedef char TElemType;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild; //左右孩子指针
pointerType LTag,RTag; //左右标志
}BiThrNode,*BiThrTree;

BiThrTree pre; //前驱指针

void CreateBiThrTree(BiThrTree *T)//建树
{
char ch;

scanf("%c",&ch);
fflush(stdin);
if(ch==' '){printf("this is blank\n"); *T = NULL;}
else
{
if(!(*T=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(EXIT_FAILURE);
(*T)->data = ch;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->LTag = (*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;
}
pre = T;
InThreading(T->rchild);
}
}
void InOrderThreading(BiThrTree *Thrt,BiThrTree T)//建立线索头结点
{
//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(1);
(*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;
}
}
void InOrderTraverse_Thr(BiThrTree T)//线索化中序遍历
{
//T指向头结点，头结点左链lchild指向根结点。
BiThrTree p;

p = T->lchild; //p指向根结点

while(p!=T) //空树或遍历结束时，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;
}
}
int main(void)
{
BiThrTree tree,treeHead;

CreateBiThrTree(&tree);

InOrderThreading(&treeHead,tree);

printf("\nInOrderTraverse:\n");
InOrderTraverse_Thr(treeHead);
return 0;
}
-
+
a

this is blank

this is blank
*
b

this is blank

this is blank
-
c
< ----这代表打空格
this is blank

this is blank
d

this is blank

this is blank
/
e

this is blank

this is blank
f

this is blank

this is blank
a + b * c - d - e / f

线索二叉树的遍历比较麻烦，没有把他都搞出来。上面是参考老严的代码。

追问

那···大侠你的代码有没有符合要求呢？

Answer 2

哪位大哥有这个程序的给我传个 谢谢了 如果可能的话加上中文注释拜托各位#include