二叉树的线索化以及 线索化的先序，中序，后序遍历

先简要说下什么线索化

二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。由于有n个结点的二叉链表中必定存在n+1个空指针域，因此充分利用这些空指针域来存放结点的前驱和后继信息。

本篇主要介绍二叉树的前序和中序线索化以及遍历，下篇介绍后序线索化以及遍历

线索化二叉树结点：

enum Info //存放标志{	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;};
  结点默认的左右线索标志符为LINK, 当需要线索化时改为THREAD,
首先创建二叉树：采用前序的方式创建
 
	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函数中的pRoot参数以及index 必须为引用，因为递归调用时需要用到上一次的值
  由于线索化二叉树构造的实质是将二叉链表的中空指针域改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历的时候才能得到，因此线索化的过程即为在遍历的过程中修改空指针域的过程，可用递归算法。
先序线索化以及遍历 ：
   假设当前节点没有右孩子，需要线索化，但是此时还没有遍历到下一个访问的结点，怎么解决这个情况呢？
   用一个结点prev来保存前一次遍历结点的信息，把需要线索化的后继放到访问下一个结点时来线索化，
  即线索化prev的后继
 思路：（1）线索化当前节点的左孩子和右孩子
    （2）线索化左子树
   （3）线索化右子树
 上代码：
  
	void PreThread()	{		BinaryTreeNodeThd<T>* prev = NULL;		_preThread(_pRoot, prev);	}	void _preThread(BinaryTreeNodeThd<T>* pRoot, BinaryTreeNodeThd<T>*& prev)	{		if (pRoot)		{			//线索化当前节点的左指针域			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->_LeftThread)				_preThread(pRoot->_pLeft, prev);			if (LINK == pRoot->_RightThread)				_preThread(pRoot->_pRight, prev);		}	}
  前序线索化遍历：
  （1）找到最左边的结点，顺便访问过程中的结点
  （2）访问当前结点的后继或者右孩子
	void _PreOrder(BinaryTreeNodeThd<T>* pRoot) //前序遍历 0136425	{		BinaryTreeNodeThd<T>* pCur = pRoot;		while (pCur) //外层循环		{			// 找到最左边的节点			while (LINK == pCur->_LeftThread)			{				cout << pCur->_data << " ";				pCur = pCur->_pLeft;			}			//此时pCur为最左边的节点还没有访问			cout << pCur->_data << " ";			//处理右孩子			pCur = pCur->_pRight;					}		cout << endl;	}
中序线索化以及遍历：
  中序 线索化：（1）线索化左子树
（2）线索化结点的左右孩子
（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) //因为结点已经被线索化过了，				_InThread(pRoot->_pRight, prev);		}	}
中序遍历：
 贴代码：
	void _InOrder(BinaryTreeNodeThd<T>* pRoot) //3614052	{		BinaryTreeNodeThd<T>* pCur = pRoot;		while (pCur)		{			//找到最左边的节点			while (LINK == pCur->_LeftThread)			{				pCur = pCur->_pLeft;			}			//访问当前节点			cout << pCur->_data << " ";			//访问当前节点的后继			while (pCur && pCur->_RightThread == THREAD) //注意左单支 pCur为空			{				pCur = pCur->_pRight;				cout << pCur->_data << " ";			}			//没有后继，有右子树			if (pCur)			{				pCur = pCur->_pRight;			}		}	}