先簡要說下什么線索化

二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實(shí)現(xiàn)非遞歸的遍歷。用二叉樹作為存儲結(jié)構(gòu)時(shí)，取到一個(gè)節(jié)點(diǎn)，只能獲取節(jié)點(diǎn)的左孩子和右孩子，不能直接得到節(jié)點(diǎn)的任一遍歷序列的前驅(qū)或者后繼。由于有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定存在n+1個(gè)空指針域，因此充分利用這些空指針域來存放結(jié)點(diǎn)的前驅(qū)和后繼信息。

本篇主要介紹二叉樹的前序和中序線索化以及遍歷，下篇介紹后序線索化以及遍歷

線索化二叉樹結(jié)點(diǎn)：

enum Info //存放標(biāo)志{	LINK,	THREAD};template<class T>struct BinaryTreeNodeThd{	BinaryTreeNodeThd(const T& data)	: _data(data)	, _pLeft(NULL)	, _PRight(NULL)	, _pParent(NULL)	, _LeftThread(LINK)	, _RightThread(LINK)	{}	T _data;	BinaryTreeNodeThd<T>* _pLeft;	BinaryTreeNodeThd<T>* _pRight;	BinaryTreeNodeThd<T>* _pParent;	Info _LeftThread;	Info _RightThread;};
  結(jié)點(diǎn)默認(rèn)的左右線索標(biāo)志符為LINK, 當(dāng)需要線索化時(shí)改為THREAD,
首先創(chuàng)建二叉樹：采用前序的方式創(chuàng)建
 
	BinaryTreeThd()		:_pRoot(NULL)	{	}	BinaryTreeThd(T array[], size_t size)		:_pRoot(NULL)	{		size_t index = 0;		_CreatBinaryTree(_pRoot, array, size, index);	}
private:	void _CreatBinaryTree(BinaryTreeNodeThd<T>*& pRoot, T array[], size_t size, size_t& index)	{		if (index < size && '#' != array[index])		{			pRoot = new BinaryTreeNodeThd<T>(array[index]);			_CreatBinaryTree(pRoot->_pLeft, array, size, ++index);			if (pRoot->_pLeft)				pRoot->_pLeft->_pParent = pRoot;			_CreatBinaryTree(pRoot->_pRight, array, size, ++index);			if (pRoot->_pRight)				pRoot->_pRight->_pParent = pRoot;		}	}
 
注意：_CreatBinaryTree函數(shù)中的pRoot參數(shù)以及index 必須為引用，因?yàn)檫f歸調(diào)用時(shí)需要用到上一次的值
  由于線索化二叉樹構(gòu)造的實(shí)質(zhì)是將二叉鏈表的中空指針域改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷的時(shí)候才能得到，因此線索化的過程即為在遍歷的過程中修改空指針域的過程，可用遞歸算法。
先序線索化以及遍歷 ：
   假設(shè)當(dāng)前節(jié)點(diǎn)沒有右孩子，需要線索化，但是此時(shí)還沒有遍歷到下一個(gè)訪問的結(jié)點(diǎn)，怎么解決這個(gè)情況呢？
   用一個(gè)結(jié)點(diǎn)prev來保存前一次遍歷結(jié)點(diǎn)的信息，把需要線索化的后繼放到訪問下一個(gè)結(jié)點(diǎn)時(shí)來線索化，
  即線索化prev的后繼
 思路：（1）線索化當(dāng)前節(jié)點(diǎn)的左孩子和右孩子
    （2）線索化左子樹
   （3）線索化右子樹
 上代碼：
  
	void PreThread()	{		BinaryTreeNodeThd<T>* prev = NULL;		_preThread(_pRoot, prev);	}	void _preThread(BinaryTreeNodeThd<T>* pRoot, BinaryTreeNodeThd<T>*& prev)	{		if (pRoot)		{			//線索化當(dāng)前節(jié)點(diǎn)的左指針域			if (NULL == pRoot->_pLeft)			{				pRoot->_pLeft = prev;				pRoot->_LeftThread = THREAD;			}			//線索化當(dāng)前節(jié)點(diǎn)的前繼節(jié)點(diǎn)的右指針域			if (prev && NULL == prev->_pRight)			{				prev->_pRight = pRoot;				prev->_RightThread = THREAD;			}			prev = pRoot;			if (LINK == pRoot->_LeftThread)				_preThread(pRoot->_pLeft, prev);			if (LINK == pRoot->_RightThread)				_preThread(pRoot->_pRight, prev);		}	}
  前序線索化遍歷：
  （1）找到最左邊的結(jié)點(diǎn)，順便訪問過程中的結(jié)點(diǎn)
  （2）訪問當(dāng)前結(jié)點(diǎn)的后繼或者右孩子
	void _PreOrder(BinaryTreeNodeThd<T>* pRoot) //前序遍歷 0136425	{		BinaryTreeNodeThd<T>* pCur = pRoot;		while (pCur) //外層循環(huán)		{			// 找到最左邊的節(jié)點(diǎn)			while (LINK == pCur->_LeftThread)			{				cout << pCur->_data << " ";				pCur = pCur->_pLeft;			}			//此時(shí)pCur為最左邊的節(jié)點(diǎn)還沒有訪問			cout << pCur->_data << " ";			//處理右孩子			pCur = pCur->_pRight;					}		cout << endl;	}
中序線索化以及遍歷：
  中序 線索化：（1）線索化左子樹
（2）線索化結(jié)點(diǎn)的左右孩子
（3）線索化右子樹
 
	void InThread()	{		BinaryTreeNodeThd<T>* prev = NULL;		_InThread(_pRoot, prev);	}	void _InThread(BinaryTreeNodeThd<T>* pRoot, BinaryTreeNodeThd<T>*& prev)	{		if (pRoot)		{			_InThread(pRoot->_pLeft, prev);			if (NULL == pRoot->_pLeft)			{				pRoot->_pLeft = prev;				pRoot->_LeftThread = THREAD;			}			if (prev && NULL == prev->_pRight)			{				prev->_pRight = pRoot;				prev->_RightThread = THREAD;			}			prev = pRoot;			if (LINK == pRoot->_RightThread) //因?yàn)榻Y(jié)點(diǎn)已經(jīng)被線索化過了，				_InThread(pRoot->_pRight, prev);		}	}
中序遍歷：
 貼代碼：
	void _InOrder(BinaryTreeNodeThd<T>* pRoot) //3614052	{		BinaryTreeNodeThd<T>* pCur = pRoot;		while (pCur)		{			//找到最左邊的節(jié)點(diǎn)			while (LINK == pCur->_LeftThread)			{				pCur = pCur->_pLeft;			}			//訪問當(dāng)前節(jié)點(diǎn)			cout << pCur->_data << " ";			//訪問當(dāng)前節(jié)點(diǎn)的后繼			while (pCur && pCur->_RightThread == THREAD) //注意左單支 pCur為空			{				pCur = pCur->_pRight;				cout << pCur->_data << " ";			}			//沒有后繼，有右子樹			if (pCur)			{				pCur = pCur->_pRight;			}		}	}