C/C++实现中序线索二叉树的构造

上一篇博客我介绍了广度优先遍历的基本实现原理，现在我来聊一聊二叉树的线索化。

众说周知当一个结点的左孩子或右孩子指针是空着的时候，为了不让结点的左孩子或右孩子指针空着，线索二叉树便随之产生了。引入线索二叉树的目的便是为了加快查找前驱和后继的速度。

线索二叉树的数据结构如图所示：

规定：若无左子树，令lchild指向其前驱节点；若无右子树，则令rchild指向其后继节点，还需加两个标志域标识指针是指向左右孩子还是指向前驱或后继的。

代码如下：

typedef char BiElem;

typedef struct ThreadNode {
	BiElem data;
	struct ThreadNode* lchild, * rchild;
	int ltag, rtag;
}ThreadNode, * ThreadTree;

中序线索二叉树的结构较为简单，下面给出一张图片帮助读者理解代码含义：

代码实现如下：

//定义全局变量
ThreadNode* pre = NULL;

//中序线索化
void visit(ThreadTree q)
{
	if (NULL == q->lchild)
	{
		q->lchild = pre;
		q->ltag = 1;
	}
	if (NULL != pre && NULL == pre->rchild)
	{
		pre->rchild = q;
		pre->rtag = 1;
	}
	pre = q;
}
//和中序遍历一样
void InThread(ThreadTree T)
{
	if (NULL != T)
	{
		InThread(T->lchild);
		visit(T);
		InThread(T->rchild);
	}
}
//创建线索二叉树
void CreatInThread(ThreadTree T)
{
	pre = NULL;
	if (NULL != T)
	{
		InThread(T);
		if (pre->rchild == NULL)
		{
			pre->rtag = 1;
		}
	}
}

//中序序列下的第一个结点
ThreadNode* Firstnode(ThreadNode* p)
{
	while (p->ltag == 0)
		p = p->lchild;
	return p;
}
//求节点p在中序序列下的后继
ThreadNode* Nextnode(ThreadTree p)
{
	if (p->rtag == 0)
		return Firstnode(p->rchild);
	else
		return p->rchild;
}
//中序遍历
void Inorder(ThreadNode* T)
{
	for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p))
		putchar(p->data);
}
int main()
{
	char c;
	ThreadTree pnew = NULL;
	ThreadTree tree = NULL;
	p_tag Listhead = NULL;
	p_tag Listtrail = NULL;
	p_tag Listpnew = NULL;
	p_tag pcur = NULL;
	while (scanf("%c", &c) != EOF)
	{
		if ('n' == c)
		{
			break;
		}
		pnew = (ThreadTree)calloc(1, sizeof(ThreadNode));
		pnew->data = c;
		Listpnew = (p_tag)calloc(1, sizeof(tag));
		Listpnew->p = pnew;
		if (NULL == tree)//入队
		{
			tree = pnew;
			Listhead = Listpnew;
			Listtrail = Listpnew;
			pcur = Listpnew;
			continue;
		}
		else
		{
			Listtrail->pnext = Listpnew;
			Listtrail = Listpnew;
		}
		if (NULL == pcur->p->lchild)//入树
		{
			pcur->p->lchild = pnew;
		}
		else if (NULL == pcur->p->rchild)
		{
			pcur->p->rchild = pnew;
			pcur = pcur->pnext;
		}
	}

	CreatInThread(tree);
	pnew = Firstnode(tree);
	printf("%c 为中序遍历下的第一个节点n", pnew->data);
	pnew = Nextnode(tree);
	printf("%c 根节点在中序序列下的后继n", pnew->data);
	Inorder(tree);
	return 0;
}