二叉樹的前序、中序和后序線索化

    二叉樹是一種非線性結構，遍歷二叉樹需要通過遞歸或者用棧輔助實現非遞歸的遍歷。

    用二叉樹作為壓縮存儲結構時，取到一個結點，只能獲取節點的左孩子和右孩子，不能直接得到結點的任一遍歷序列的前驅或者后繼。為了實現這種遍歷，偶們利用二叉樹中指向左右子樹的空指針來存放結點的前驅和后繼。

線索化二叉樹思路：

    當某一結點的左結點或結右點存在NULL時，則該結點的為空的子結點需要線索化。

    在進行線索化時，結點的前驅指向前一個訪問過的結點，故定義一個指針prev來保存前一個結點；結點的后繼偶們并不知道，則對于未來的事情并不知道，偶們可以在未來對該結點的后繼進行線索化，使prev的后繼指向cur。

前序遍歷二叉樹------根->左->右（1,2,3,4,5,6）

template<class T>
void BinaryTreeThd<T>::PrevOrderThreading()//前序線索化二叉樹
{
	Node* prev = NULL;
	_PrevOrderThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_PrevOrderThreading(Node* cur, Node*& prev)//前序線索化二叉樹
{
	if (cur == NULL)
	{
		return;
	}
	if (cur->_left == NULL)
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;
	}
	if (prev && prev->_right == NULL)//到未來的結點進行先前結點后繼的線索化
	{
		prev->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
	if (cur->_leftTag == LINK)//線索化左結點
	{
		_PrevOrderThreading(cur->_left, prev);
	}
	if (cur->_rightTag == LINK)//線索化右結點
	{
		_PrevOrderThreading(cur->_right, prev);
	}
}

中序遍歷二叉樹------左->根->右（3,2,4,1,6,5）

遞歸實現：

template<class T>
void BinaryTreeThd<T>::InOrderThreading()//中序線索化二叉樹
{
	//遞歸實現中序線索化
	Node* prev = NULL;//線索化的前一個結點
	_InOrederThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_InOrederThreading(Node* cur,Node*& prev)//中序線索化二叉樹
{
	if (cur == NULL)
	{
		return;
	}
	_InOrederThreading(cur->_left, prev);//遞歸出cur->_left為空
	if (cur->_left == NULL)
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;//當前結點的前驅指向前一個結點
	}
	//對先前的結點后繼進行線索化，在cur指向下一個結點即后繼時，將先前節點的后繼指向cur
	//到未來的結點進行先前結點后繼的線索化
	if (prev && prev->_right == NULL)
	{
		cur->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
	_InOrederThreading(cur->_right, prev);//遞歸出cur->_right為空
}

非遞歸實現（利用棧）：

template<class T>
void BinaryTreeThd<T>::InOrderThreading_NonR()//中序線索化二叉樹--非遞歸
{
	//棧實現中序線索化
	stack<Node*> s;
	Node* prev = NULL;
	Node* cur = _root;
	if (cur == NULL)
	{
		return;
	}
	while (cur || !s.empty())
	{
		while(cur)//找到最左結點,入棧
		{
			s.push(cur);
			cur = cur->_left;
		}//cur不為空進棧，cur為空說明cur已經線索化了
		cur = s.top();//循環進入使cur為棧頂元素并判斷是否需要線索化
		if (cur->_left == NULL)
		{
			cur->_leftTag = THREAD;
			cur->_left = prev;
		}
		s.pop();//彈出棧頂元素，使棧頂保存需要線索化的cur的后繼
		prev = cur;
		if (cur->_right == NULL && !s.empty())
		{
			cur->_rightTag = THREAD;
			cur->_right = s.top();
			cur = NULL;//設置cur為空，防止死循環（2）
		}
		else
		{
			cur = cur->_right;//線索化跳到右子樹進行
		}
	}
}

后序遍歷二叉樹------左->右->根（3,4,2,6,5,1）

template<class T>
void BinaryTreeThd<T>::PastOrderThreading()//后序線索化二叉樹
{
	Node* prev = NULL;
	_PastOrderThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_PastOrderThreading(Node* cur, Node*& prev)//后序線索化二叉樹
{
	if (cur == NULL)
	{
		return;
	}
	_PastOrderThreading(cur->_left, prev);//最左結點
	_PastOrderThreading(cur->_right, prev);//最右結點
	if (cur->_left == NULL)//線索化前驅
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;
	}
	if (prev && prev->_right == NULL)//線索化后繼
	{
		prev->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
}