#include<malloc.h>
#include<stdlib.h>
#include<stdio.h>
#define MaxSize 100
//实现中序线索化二叉树
typedef struct node{
char data; //数据域
int ltag,rtag; //线索标记
struct node *lchild; //左孩子指针
struct node *rchild; //右孩子
}TBTNode;
//ltag、rtag为1：表示线索化
//由str串建立含空线索域的二叉链b
void CreateTBTree(TBTNode *&b,char *str){
TBTNode *St[MaxSize],*p;
int top=-1,k,j=0;
char ch=str[j]; //ch赋值为字符串的第一个字符
b=NULL; //初始化二叉树b
while(ch!='\0'){ //扫描到结束符退出循环
switch(ch){
case'(':
top++;
St[top] = p; //St存储双亲结点 ,也就是上一个结点
k=1; //k用于标记下个元素是不是左右孩子
break; //开始处理左子树
case')':
top--; //删除一个St中的双亲元素
break; //子树处理完毕
case',':
k=2; //k=2,下个元素为右孩子
break; //开始处理右子树
default:
p=(TBTNode *)malloc(sizeof(TBTNode));
p->data = ch; //存储结点值
p->lchild = p->rchild = NULL; //左右指针全指向NULL
if (b==NULL)
b=p; //若b为空，p置为二叉树根结点
//这里修改了头指针，所以函数定义时，需要用&
else{ //若已经创建好根结点
switch(k){ //这里用的k标记是上一轮循环标记好的
case 1:St[top]->lchild = p; //St[top]存储了上一个结点p1
//等价于 p1->lchild = p;
break;
case 2: St[top]->rchild = p;
break;
}
}
}
j++;
ch = str[j];
}
}
//输出含空线索域的二叉树
void DispTBTree(TBTNode *b){
if(b!=NULL){
printf("%c",b->data);
if(b->lchild != NULL || b->rchild != NULL){
printf("("); //有孩子结点时才输出(
DispTBTree(b->lchild); //递归处理左子树
if(b->rchild != NULL)
printf(","); //有右孩子结点时才输出,
DispTBTree(b->rchild); // 递归处理右子树
printf(")"); //有孩子结点时才输出)
}
}
}
TBTNode *pre; //==========全局变量===================
//中序线索化二叉树，被CreateThread调用
void Thread(TBTNode *&p){
if(p!=NULL){
Thread(p->lchild); //-------递归遍历左子树，并将其线索化
if(p->lchild == NULL){ //若左指针为空，将该指针作为线索保存前驱结点
p->lchild = pre; //p的前驱是pre，所以p的左孩子保存pre结点
p->ltag=1; //标记该结点已经线索化
} else //否则标记左指针不能被线索化
p->ltag=0;
if(pre->rchild == NULL) { //pre的后继是p，所以pre的右孩子保存p结点
//注意此处判断的pre的右孩子是否为空
pre->rchild=p;
pre->rtag=1;
}else
pre->rtag=0;
pre = p; //修改前驱结点
Thread(p->rchild); //--------递归遍历右子树，并将其线索化
}
}
//问题一：已经构建好了二叉树，并且在Thread中已经线索化了，那么CreateThread()函数有什么作用？
/*-------
作用一：增加一个头结点root，使得第一个被线索化的结点有前驱root；
作用二： 修改全局变量pre，使它指向根结点root ；
作用三：Thread函数将数b线索化后，最后被遍历的结点的右指针并没有被线索化，
所以Thread调用完后，需将最后结点（线索化后pre指向最后一个结点）的右指针线索化 ，
指向根结点root；
----------*/
//创建中序线索化二叉树
TBTNode *CreateThread(TBTNode *b){
TBTNode *root;
root = (TBTNode *)malloc(sizeof(TBTNode)); //创建头结点
root->ltag=0; //左指针指向根结点
root->rtag=1; //右指针用来线索化
root->rchild=b;//如果数b只有一个结点，那么头结点root的右指针指向最后一个结点
if(b==NULL) //空二叉树
root->lchild = root;
else{
root->lchild = b;
pre = root;
Thread(b);
pre->rchild = root; //此时的pre为中序遍历的最后结点
pre->rtag = 1;
root->rchild = pre; //将的右指针线索指向最后结点pre
}
return root;
}
// 被ThInOrder算法调用
void InOrder(TBTNode *tb){
if(tb->lchild != NULL && tb->ltag == 0) //有左孩子且没有被线索化
InOrder(tb->lchild);
printf("%c",tb->data);
if(tb->rchild!=NULL && tb->rtag == 0)
InOrder(tb->rchild);
}
//中序线索二叉树的中序遍历递归算法
void ThInorder(TBTNode *tb){
InOrder(tb->lchild);
}
//中序线索二叉树的中序遍历非递归算法
void ThInOrder1(TBTNode *tb){
TBTNode *p = tb->lchild; //指向根结点
while(p!=tb){
while(p->ltag == 0) //找中序开始结点
p=p->lchild;
printf("%c",p->data);
while(p->rtag == 1 && p->rchild != tb){
p=p->rchild;
printf("%c",p->data);
}
p=p->rchild;
}
}
//被DestroyTBTree算法调用
void DestroyTBTree1(TBTNode *tb){
if(tb!=NULL){
if(tb->lchild != NULL && tb->ltag == 0) //如果有左孩子，且没被线索化
DestroyTBTree1(tb->lchild);
if(tb->rchild != NULL && tb->rtag == 0)
DestroyTBTree1(tb->rchild);
free(tb);
}
}
//释放中序线索二叉树的所有结点
void DestroyTBTree(TBTNode * tb){
DestroyTBTree1(tb->lchild);
free(tb);
printf("释放完成");
}
int main(){
TBTNode *b,*tb;
CreateTBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))");
printf("二叉树：");DispTBTree(b);printf("\n");
tb=CreateThread(b);
tb=b;
printf("线索中序序列：\n");
printf(" 递归算法：");ThInorder(tb); printf("\n");
printf(" 非递归算法：");ThInOrder1(tb);printf("\n");
DestroyTBTree(tb);
return 1;
}
?
