线索二叉树的实现

线索二叉树的实现

一、目的：

掌握线索二叉树的定义、性质及存储方式，各种遍历算法。

二、要求：

采用线索二叉树链表作为存储结构，完成二叉树的建立，对二叉树进行中序线索化，并进行中序遍历。

三、实验内容

1、设计、分析、理解程序。

2、调试程序，设计一棵二叉树，按先序遍历方式输入：“ABD##EH##I##CF##G##”，其中“#”表示空指针。完成二叉树进行中序线索化，并进行中序后继线索遍历。

四、实验报告要求

1、画出所设计的二叉树，画出线索化示意图。

2、给出实验结果。

#include
#include

#include

typedef enum{Link,Thread} PointerTag; /*指针标志*/

typedef char DataType;

typedef struct BiThreTree{ /*定义结点元素*/

PointerTag LTag,RTag;

DataType data;

struct BiThreTree *lchild,*rchild;

}BiThreTree;

BiThreTree *pre; /*全局变量，用于二叉树的线索化*/

BiThreTree *CreateTree() /*按前序输入建立二叉树*/

{

BiThreTree *T;

DataType ch;

scanf("%c",&ch);

if(ch=='#')

T=NULL;

else

{T=(BiThreTree *)malloc(sizeof(BiThreTree));

T->data=ch;

T->LTag=Link; /*初始化时指针标志均为Link*/

T->RTag=Link;

T->lchild=CreateTree();

T->rchild=CreateTree();

}

return T;

}

void InThread(BiThreTree *T)

{

BiThreTree *p;

p=T;

if(p)

{

InThread(p->lchild);

if(!p->lchild)

{ p->LTag=Thread;

p->lchild=pre;

}

if(!pre->rchild)

{ pre->RTag=Thread;

pre->rchild=p;

}

pre=p;

InThread(p->rchild);

}

}

BiThreTree *InOrderThrTree(BiThreTree *T) /*中序线索化二叉树*/

{

BiThreTree *Thre; /*Thre为头结点的指针*/

Thre=(BiThreTree *)malloc(sizeof(BiThreTree));

Thre->lchild=T;

Thre->rchild=Thre;

pre=Thre;

InThread(T);

pre->RTag=Thread;

pre->rchild=Thre;

Thre->rchild=pre;

return Thre;

}

void InThrTravel(BiThreTree *Thre) /*中序遍历二叉树*/

{

BiThreTree *p;

p=Thre->lchild;

while(p!=Thre) /*指针回指向头结点时结束*/

{

while(p->LTag==Link)

p=p->lchild;

printf("%4c",p->data);

while(p->RTag==Thread&&p->rchild!=Thre)

{p=p->rchild;

printf("%4c",p->data);

}

p=p->rchild;

}

}

void main()

{

BiThreTree *T,*Thre;

printf("PreOrder Create Binary Tree:\n");

T=CreateTree();

Thre=InOrderThrTree(T);

printf("InOrder Traverse Binary Tree:\n");

InThrTravel(Thre);

system("pause");

}