C语言--线索二叉树创建与遍历

线索二叉树就是把左或者右孩子为空的位置，设置为前驱或者后继

因为中序遍历第一个元素是C，没有前驱，最后一个元素F也没有后继，所以我们设置一个头结点，C的前驱和F的后继都指向投节点，头节点的前驱为根节点，后继为最后一个元素F。

#include"stdio.h"
#include"stdlib.h"
//线索标志位
//link表示指向左右孩子
//thread表示指向前驱后继
enum{link, thread};
//二叉树结构体
struct btree
{
	char data;
	struct btree *lchild, *rchild;
	int ltag, rtag;
};
//全局变量，指向刚访问过的结点
struct btree *pre;
//用户按照前序遍历方式创建二叉树
void create_btree(struct btree **T)
{
	char c;
	*T = (struct btree *)malloc(sizeof(struct btree));
	scanf("%c", &c);
	if(' ' == c)
	{
		*T = NULL;
	}
	else
	{
		(*T)->data = c;
//线索标志位全部初始化为link
		(*T)->ltag = link;
		(*T)->rtag = link;
		create_btree(&(*T)->lchild);
		create_btree(&(*T)->rchild);
	}
}
//中序遍历二叉树，更改线索标志位以及前驱后继
void inthread(struct btree *T)
{
	if(T)
	{
		inthread(T->lchild);
//如果左孩子为空，线索标志位改为thread，lchild指向前驱
//中序遍历二叉树的第一个结点的前驱为头结点
		if(!(T->lchild))
		{
			T->ltag = thread;
			T->lchild = pre;
		}
//如果右孩子为空，线索标志位改为thread，rchild指向后继
//中序遍历二叉树的最后一个结点的后继为头结点
		if(!(pre->rchild))
		{
			pre->rtag = thread;
			pre->rchild = T;
		}
//pre为刚访问过的结点
		pre = T;
		inthread(T->rchild);
	}
}
//创建头节点，并让pre初始化为头结点
void inordthread(struct btree **P, struct btree *T)
{
//初始化头结点
	(*P) = (struct btree *)malloc(sizeof(struct btree));
//头结点左标志位为link，左孩子为二叉树根结点
//头结点右标志位为thread，后继初始化为自己，后面会设置为二叉树最后一个结点
	(*P)->ltag = link;
	(*P)->rtag = thread;
	(*P)->lchild = T;
	(*P)->rchild = *P;
	if(!T)
	{
		(*P)->lchild = *P;
	}
	else
	{
//pre初始化为头结点
		pre = *P;

		inthread(T);
//中序遍历二叉树的最后一个结点的标志位为thread
//后继为头结点
		pre->rtag = thread;
		pre->rchild = *P;
//头结点的后继为最后一个结点
		(*P)->rchild = pre;
	}
}
//打印中序遍历二叉树
void visit(char c)
{
	printf("%c", c);
}
//使用线索中序遍历二叉树
void inordtraversal(struct btree *P)
{
//临时结点p2，初始化为根结点
	struct btree *p2;
	p2 = P->lchild;
//若p2不等于头结点，说明遍历没有完成
	while(p2 != P)
	{
//p2有左孩子，一直往下遍历
		while(p2->ltag == link)
		{
			p2 = p2->lchild;
		}
		visit(p2->data);
//若没有右孩子且后继不为头结点，p2等于p2的后继(一直往后走)
		while(p2->rtag == thread  && p2->rchild != P)
		{
			p2 = p2->rchild;
			visit(p2->data);
		}
//若没有后继，p2等于p2的右孩子
		p2 = p2->rchild;
	}	
}
int main()
{
	struct btree *P, *T;
	create_btree(&T);
	inordthread(&P, T);
	inordtraversal(P);
	printf("\n");
	return 0;
}

第一行是输入，第二行是中序遍历输出。