【数据结构】10.线索二叉树

一、线索二叉树的产生

采用先序、中序、后序三种方法遍历二叉树后都可以得到一个线性序列，序列上的每一个结点（除了第一个和最后一个）都有一个前驱和一个后继，但是，这个线性序列只是逻辑的概念，不是物理结构。

二、二叉树线索化

二叉树线索化是将二叉链表中的空指针改为指向前驱或后继结点。而前驱结点和后继结点只要在遍历时才能拿到，所有二叉树线索化分为先序线索二叉树、中序线索二叉树和后序线索二叉树。

2.1 线索二叉树的定义

typedef int ThreadedBinaryTreeDataType;

typedef struct ThreadedBinaryTree
{
	ThreadedBinaryTreeDataType _data;	
	struct ThreadedBinaryTree* _left;	
	struct ThreadedBinaryTree* _right;
	int _LeftFlag, _RightFlag;	//左右指针类型：0表示非线索指针，1表示线索指针
}TBT,*pTBT;

2.2 先序线索二叉树

如果当前结点的右指针存放的是线索，右指针指向的结点即为后续节点。
如果当前结点的右指针存放的是结点，取左子结点，如果左子结点为空，取右子结点。

void _ThreadedPrevOrder(TBT* root)
{
	if (root == NULL)
		return;

	if (root->left == NULL)
	{
		root->left = prev;
		root->LeftFlag = 1;
	}
	if (prev && prev->right == NULL)
	{
		prev->right = root;
		prev->RightFlag = 1;
	}
	prev = root;

	if(root->LeftFlag==0)
		_ThreadedPrevOrder(root->left);
	if(root->RightFlag==0)
		_ThreadedPrevOrder(root->right);
}

void ThreadedPrevOrder(TBT* root)
{
	if (root == NULL)
		return;
	_ThreadedPrevOrder(root);

	prev->right = NULL;
	prev->RightFlag = 1;
}

2.3 后序线索二叉树

如果当前结点的左指针存放的是线索，左指针指向的结点即为前驱节点。
如果当前结点的左指针存放的是结点，取右子结点，如果右子结点为空，取左子结点。

void _ThreadedPostOrder(TBT* root)
{
	if (root == NULL)
		return;

	_ThreadedPostOrder(root->left);
	_ThreadedPostOrder(root->right);
	if (root->left == NULL)
	{
		root->left = prev;
		root->LeftFlag = 1;
	}
	if (prev && prev->right == NULL)
	{
		prev->right = root;
		prev->RightFlag = 1;
	}
	prev = root;
}

void ThreadedPostOrder(TBT* root)
{
	if (root == NULL)
		return;
	_ThreadedPostOrder(root);
}

2.4 中序线索二叉树

如果当前结点的右指针存放的是线索，右指针指向的结点即为后续节点。
如果当前结点的右指针存放的是结点，右子树中序遍历序列的第一个结点（最左）就是后续节点。
如果当前结点的左指针存放的是线索，左指针指向的结点即为前驱节点。
如果当前结点的左指针存放的是结点，左子树中序遍历序列的最后一个结点（最右）就是后续节点。

void _ThreadedInOrder(TBT* root)
{
	if (root == NULL)
		return;

	_ThreadedInOrder(root->left);

	if (root->left == NULL)
	{
		root->left = prev;
		root->LeftFlag = 1;
	}
	if (prev && prev->right == NULL)
	{
		prev->right = root;
		prev->RightFlag = 1;
	}
	prev = root;
	_ThreadedInOrder(root->right);
}

void ThreadedInOrder(TBT* root)
{
	if (root == NULL)
		return;
	_ThreadedInOrder(root);

	prev->right = NULL;
	prev->RightFlag = 1;
}

三、遍历线索二叉树

3.1 遍历中序线索二叉树

void inOrderTraverseThTree(TBT* root)
{
	//找到初始节点
	TBT* head = root;
	while (head->left)
		head = head->left;

	while (head)
	{
		printf("%d ", head->data);

		//找下一个访问的结点
		if (head->right && head->RightFlag == 1)
			head = head->right;
		else if (head->right)
		{
			head = head->right;
			while (head->left && head->LeftFlag == 0)
				head = head->left;
		}
		else if (head->right == NULL)
			break;
	}
}

3.2 遍历先序线索二叉树

void PrevOrderTraverseThTree(TBT* root)
{
	TBT* head = root;
	while (head)
	{
		printf("%d ", head->data);
		if (head->LeftFlag == 0)
			head = head->left;
		else
			head = head->right;
	}
}

3.3 遍历后序线索二叉树

对于后序线索二叉树的遍历是要复杂一点的，对于根节点的后继结点是不好定位的，最好使用到三叉链，当然也可以迭代找到，这里就不演示了