实验6：二叉树的线索化
一、实验目的
1．掌握线索二叉树的存储结构。

2．掌握将一棵二叉树线索化算法。

3．掌握线索二叉树的遍历算法，理解算法在效率上的改进。

4.将算法用C语言编写完整程序并上机运行，记录实验过程与数据。

二、实验仪器：
1.硬件：Lenovo通用PC机，
2.软件：WINDOWS7，WORD，GCC编译器
三、实验原理：
1.线索化算法
四、实验步骤：
1.设计一个实验样本，取二叉树为：
2.定义一个线索二叉树的结点；
此处填写具体代码
3.按先序的方式建立一棵普通的二叉树；此处填写具体代码
4.将普通二叉树线索化
此处填写具体代码
5.按线性方式遍历线索二叉树
此处填写具体代码
五、数据处理及结论
1.输入：
A↙B↙D↙#↙#↙E↙#↙#↙C↙F↙#↙#↙G↙#↙#
注:每个↙符号代表输入确定，即回车
2.输出：
C B E A F C G
C B E A F C G
七、思考题：
1.为什么要将一棵二叉树线索化？
2.为什么在线索化的过程中preNode要使用全局变量？附：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define NULLFLAG '#'
typedef char elemType;
typedef enum{
FALSE,TRUE
}status;
typedef enum{
link,thread
}pointerTag;
typedef struct NODE{
elemType data;
struct NODE *lchild,*rchild;
int lTag,rTag;
}biThreadTreeNode;
//定义一个全局变量指针preNode,在线索化时记录每个结点的直接前驱结点biThreadTreeNode *preNode;
status biThreadTreeNodeInit(biThreadTreeNode *t,elemType e){ if(t){
t->data=e;
t->lchild=NULL;
t->rchild=NULL;
t->lTag=link;
t->rTag=link;
return TRUE;
}
else
return FALSE;
}
//按先序遍历的方法建立一棵二叉树，空位用空格号代替
status biThreadTreeCreate(biThreadTreeNode **t){
elemType ch;
//fflush(stdin);//如果使用清空缓存的这句，则每输入一个字符要回车一次ch=getchar();
if(ch==NULLFLAG){
*t=NULL;
return FALSE;
}
else{
*t=(biThreadTreeNode*)malloc(sizeof(biThreadTreeNode));
if(*t){
biThreadTreeNodeInit(*t,ch);
biThreadTreeCreate(&((*t)->lchild));
biThreadTreeCreate(&((*t)->rchild));
}
}
return TRUE;
}
//按中序遍历的方式输出一棵二叉树
void biThreadTreePrint(biThreadTreeNode *t){
if(t){
biThreadTreePrint(t->lchild);
printf("%4c",t->data);
biThreadTreePrint(t->rchild);
}
}
//按中序遍历的方式将二叉树线索化
status biTreeThreading(biThreadTreeNode *t){
if(!t)
return FALSE;
else{
biTreeThreading(t->lchild);
if(t->lchild==NULL){
t->lchild=preNode;
t->lTag=thread;
}
if(preNode->rchild==NULL){
preNode->rchild=t;
preNode->rTag=thread;
}
preNode=t;
biTreeThreading(t->rchild);
}
return TRUE;
}
//完整的线索化过程
status inOrderThreading(biThreadTreeNode *head,biThreadTreeNode *t){ head->rchild=head;
head->rTag=thread;
if(t==NULL){
head->lchild=head;
head->lTag=thread;
return FALSE;
}
else{
head->lTag=link;
head->lchild=t;
preNode=head;
biTreeThreading(t);
head->rchild=preNode;
preNode->rchild=head;
preNode->rTag=thread;
}
return TRUE;
}
status threadTraversal(biThreadTreeNode *head){
biThreadTreeNode *p;
if(head==NULL)
return FALSE;
p=head->lchild;
while(p!=head){
while(p->lTag==link)
p=p->lchild;
printf("%4c",p->data);
while(p->rTag==thread && p->rchild!=head){
p=p->rchild;
printf("%4c",p->data);
}
p=p->rchild;
}
return TRUE;
}
void main(){
biThreadTreeNode *head,*root;
head=(biThreadTreeNode*)malloc(sizeof(biThreadTreeNode));
biThreadTreeCreate(&root);
biThreadTreePrint(root);
inOrderThreading(head,root);
printf("\n");
threadTraversal(head);
}
（注：可编辑下载，若有不当之处，请指正，谢谢!）。