线索二叉树

我们都知道二叉树有前序、中序、后序三种不同的遍历方式，不同的遍历方式会得到不同的线性序列。
该序列中的每个结点（第一个和最后一个除外）都有一个直接前驱、直接后继。
那么如果给我们指定结点，该如何找到它的前驱和后继呢？
我们通常定义的二叉树结点只能表现父子关系，不能得到结点在某种遍历序列中的前驱和后继。
由于每个结点都有左孩子和右孩子2个指针，在n个结点的二叉树中就有2n个指针，除根结点外每个结点头上都只有一个指针，即 n-1个指针；所以就有 n+1个空指针。
通过改变这些空指针的指向就可以使前驱和后继（在某种遍历序列中）的查找容易许多，即所谓二叉树的线索化

一、线索二叉树的构造 1. 前序线索二叉树

//线索化基本思路：left==NULL,则令left指向前驱结点；right==NULL,则令right指向后继节点
//为了区分结点的left、right指向的到底是孩子结点还是前驱后继结点，引入了ltag、rtag；
//当ltag==0,rtag==0时，指向的是孩子结点；当ltag==1,rtag==1时，指向的是前驱后继结点。

typedef char ElemType;
typedef struct ThreadNode
{
	ElemType val;
	struct ThreadNode* left;
	struct ThreadNode* right;
	int ltag; //线索标志
	int rtag;
}ThreadNode;

//这里的pre指针指向的是cur的前驱结点。
//因为right的线索化要指向的是当前结点的后继，无法通过cur找到后继（如果该结点需要线索化的话）
//因此需要pre指针指向cur前驱结点，当cur指向下一个结点后，再来判断pre的right是否需要线索化，如果需要的话，将pre->right指向cur即可。
void PreThread(ThreadNode*& root, ThreadNode*& pre) 
{
	ThreadNode* cur = root;
	if(cur)
	{
		if(cur->left == NULL)
		{
			cur->left = pre;
			cur->ltag = 1;
		}
		if(pre != NULL && pre->right == NULL)
		{
			pre->right = cur;
			pre->rtag = 1;
		}
		pre = cur; //pre跟上cur,cur去下一个结点
		
		//这里是有坑的，因为如果cur->left==NULL，在这之前cur->left就会被指向其前驱结点pre
		//而接下来再递归左子树，就会形成死循环
		if(cur->ltag == 0) 
		{
			PreThread(cur->left, pre);
		}
		PreThread(cur->right, pre);
	}
}
void CreatePreThread(ThreadNode*& root)
{
	assert(root);
	ThreadNode* pre = NULL;
	if(root)
	{
		PreThread(root, pre);
		//注意当cur为最后一个结点时进行的 *** 作是：cur->left指向pre，pre=cur。而pre->right还并未判断，因此pre->rtag仍未0；
		//所以需要再对最后一个结点进行处理
		if(pre->right == NULL)
		{
			pre->rtag == 1; 
		}
	}
}

需要注意的是，

1. 由于前序遍历“根左右”的特性，左右指针的线索化是在递归之前的，因此一定要注意 ltag==0 的时候才需要递归左子树，而ltag == 1时说明其左指针为空且已经指向前驱结点，这时再对左子树递归会进入死循环。
2. 对某个结点 left 和 right 的线索化不是同时进行的。因为无法通过cur找到当前结点的后继（对cur->right的判空是可以的，但是即便cur->right==NULL在当前递归栈中也无法进行指向后继的 *** 作），即需要在下一层递归中判断pre->right==NULL?。
   这样就会存在一个问题，在处理最后一个结点(final)时，final的 left 处理完了，而 right 还未处理就结束了（final肯定没有左右孩子，有的话就会继续递归）；因此需要将final的 rtag 置成1（表示线索化完成）。

2. 中序线索二叉树

void InThread(ThreadNode*& root, ThreadNode*& pre)
{
	ThreadNode* cur = root;
	if(cur)
	{
		InThread(cur->left, pre);
		
		if(cur->left == NULL)
		{
			cur->left = pre;
			cur->ltag = 1;
		}
		if(pre != NULL && pre->right == NULL)
		{
			pre->right = cur;
			pre->rtag = 1;
		} 
		pre = cur;
		
		InThread(cur->right, pre);
	}
}
void CreateInThread(ThreadNode*& root)
{
	ThreadNode* pre = NULL;
	if(root)
	{
		InThread(root, pre);
		if(pre->right == NULL)
		{
			pre->rtag = 1;
		}
	}
}

3. 后序线索二叉树

void PostThread(ThreadNode*& root, ThreadNode*& pre)
{
	ThreadNode* cur = root;
	if(cur)
	{
		PostThread(cur->left, pre);
		PostThread(cur->right, pre);

		if(cur->left == NULL)
		{
			cur->left = pre;
			cur->ltag = 1;
		}
		if(pre != NULL && pre->right == NULL)
		{
			pre->right = cur;
			cur->rtag = 1;
		}
		pre = cur;
	}
}
void CreatePostThread(ThreadNode*& root)
{
	ThreadNode* pre = NULL;
	if(root)
	{
		PostThread(root, pre);
		if(pre->right == NULL)
		{
			pre->rtag = 1;
		}
	}
}

中序和后序线索化相较于前序来说就很简单，它们不存在进入死循环的情况，因为在对结点left指针进行处理之前已经对左子树进行了遍历；只是仍需要将最后一个结点的rtag置成1。

二、线索二叉树的遍历 找中序后继 – 中序遍历

在中序线索二叉树中找指定结点 p 的后继 next：

1. 若p->rtag == 1，则next = p->right；
2. 若p->rtag == 0，说明 p 有右孩子，由"左-根-右"可知，p 的右子树中第一个被访问的结点就是后继。
   若 p 的右孩子为叶子结点，则 p 的右孩子即为后继；若 p 的右孩子为分支节点，则需要找到 p 右子树中最左下的结点（注意是最左下而不是最底层的结点）。

//找到以root为根的子树中，第一个被中序遍历的结点
ThreadNode* FirstNode(ThreadNode* root)
{
	//循环找到最左下结点（不一定是叶子结点）
	while(root->ltag == 0)
		root = root->left;
	return root;
}
//找p结点的后继
ThreadNode* NextNode(ThreadNode* p)
{
	if(p->rtag == 0) 	//有右孩子，找到以右孩子为根的右子树中第一个被访问的结点
		return FirstNode(p->right);
	else			 	//rtag==1，右指针已被线索化，直接返回后继
		return p->right;
}
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法，空间复杂度O(1)）
void InOrder_Thread(ThreadNode* root)
{
	for(ThreadNode* p = FirstNode(root); p != NULL; p = NextNode(p))
		visit(p); //访问函数
}

找中序前驱 – 逆向中序遍历

在中序线索二叉树中找指定结点 p 的前驱 pre：

1. 若p->ltag == 1，则pre= p->left；
2. 若p->ltag == 0，说明 p 有左孩子，则 p 的左子树中最后被访问的结点即为前驱。由"左-根-右"可知，我们需要找到左子树中最右下的结点。

//找到以root为根的子树中，最后一个被中序遍历的结点
ThreadNode* LastNode(ThreadNode* root)
{
	//找到最右下结点（不一定为叶子节点）
	//若是叶子结点，不用说肯定是最后被访问；若是分支结点，它只有可能有左孩子，那么先访问左（左孩子），最后访问自己
	while(root->rtag == 0)
		root = root->right;
	return root;
}
//找p结点的前驱
ThreadNode* PreNode(ThreadNode* p)
{
	if(p->ltag == 0)
		return LastNode(p->left);
	else
		return p->left;
}
//对中序线索二叉树进行逆向中序遍历
void Reverse_InOrder_Thread(ThreadNode* root)
{
	for(ThreadNode* p = LastNode(root); p != NULL; p = PreNode(p))
		visit(p);
}

找前序后继

在前序线索二叉树中找 p 结点的后继 next：

1. 若p->rtag == 1，则next = p->right；
2. 若p->rtag == 0，说明 p 有右孩子，由“根-左-右”顺序：
   假设 p 也有左孩子，那么 p 的后继就是左子树中第一个被访问的结点，即 p 的左孩子。
   假设 p 只有右孩子没有左孩子，那么 p 的后继就是右子树中第一个被访问的结点，即 p 的右孩子。

找前序前驱

在前序线索二叉树中找 p 结点的前驱 pre：

1. 若p->ltag == 1，则pre= p->left；
2. 若p->ltag == 0，说明 p 有左孩子，但是由“根-左-右”，我们发现 p 的左右子树中的所有结点都不可能是其前驱。而以当前“结点的结构”是没办法回溯找到 p 的前驱。

那怎么办呢？
方法一：从根结点开始，用递归遍历的方法找到前驱

//方法一：从根结点出发，重新进行一次中序遍历，指针cur记录当前访问结点，pre记录上一个结点；当cur==p时，pre为前驱
ThreadNode* p; //指定结点
ThreadNode* pre = NULL; //当前结点的前驱
ThreadNode* ret = NULL; //最终返回的前驱结点
void FindPre_Of_InOrder(ThreadNode* root)
{
    if(root == NULL)
        return;
    visit(root);
    FindPre_Of_InOrder(root->left);
    FindPre_Of_InOrder(root->right);
}
 ThreadNode* visit(ThreadNode* cur)
 {
     if(cur == p)
         ret = pre;
     else
         pre = cur;
 }

方法二：
首先，我们来分析以下几种情况（前序遍历：根-左-右）：

1. 能找到 p 的父节点，且 p 是左孩子，则 p 的父结点即为前驱；
2. 能找到 p 的父节点，且 p 是右孩子，其左兄弟为空，则 p 的父结点即为前驱；
3. 能找到 p 的父节点，且 p 是右孩子，其左兄弟非空，则 p 的左兄弟子树中最后一个被访问的结点即为前驱；
   接下来分析如何找到某子树中最后一个被前序遍历的结点？
   如果根结点有右孩子，就顺着右孩子一路到底，直到右孩子为空。
   若当前结点（cur）为叶子结点，cur 即为前驱；若为 cur 分支结点，则说明 cur 有左孩子，那么就顺着左孩子一路到底，直到左孩子为空。
   接下来还得判断 cur 是不是叶子结点，如果是 cur 即为前驱，如果不是还得顺着cur的右孩子一路到底… … 就这样不断重复上述步骤，直到遇到一个叶子结点结束。
4. 找不到 p 的父结点，说明 p 为根结点，那么根结点是没有前驱的。

找前序前驱的基本思路就是以上这四种情况，我们的分析都是建立在能够找到父结点的基础上。
**如何找到父结点呢？**我们可以尝试使用三叉链表，即增加一个指向父结点的前向指针来解决这个问题。

找后序前驱

在后序线索二叉树中找 p 结点的前驱 pre：

1. 若p->ltag == 1，则pre= p->left；
2. 若p->ltag == 0，说明 p 有左孩子，若 p 有右孩子，由“左-右-根”可知，则 p 的右孩子即为前驱；若 p 无右孩子，则 p 的左孩子即为前驱。

找后序后继

在后序线索二叉树中找 p 结点的后继 next：

1. 若p->rtag == 1，则pre= p->right；
2. 若p->rtag == 0，说明 p 有右孩子，但是由“左-右-根”，我们发现 p 的左右子树中的所有结点都不可能是其后继。

跟找前序前驱的情况类似，
方法一：从根结点开始，用递归遍历找到后继
方法二：用三叉链表存储，从而找到 p 的父结点

• 能找到 p 的父结点，且 p 是右孩子，则 p 的父结点即为后继；
• 能找到 p 的父结点，且 p 是左孩子，其右兄弟为空，则 p 的父结点即为后继；
• 能找到 p 的父结点，且 p 是左孩子，其右兄弟非空，则 p 的右兄弟子树中第一个被访问的结点即为后继。同样地，从右兄弟结点出发，有左孩子就一路左到底，此时为叶子结点，即为后继；不是的话就一路右到底，此时为叶子结点，即为后继… … 不断重复左右左右这个过程，直到遇见叶子结点。
• 找不到 p 的父结点，p 为根结点，无后继。

这个过程对于我这个自学菜鸟来说好复杂，代码我得酝酿一段时间。