二叉树后序线索化以及后序遍历

构建节点：多了双亲节点

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;};
  后序线索化：先线索化左子树 再线索化右子树，最后线索化当前根节点
   直接贴代码
	void PostThread()	{		BinaryTreeNodeThd<T>* prev = NULL;		_PostThread(_pRoot, prev);	}	void _PostThread(BinaryTreeNodeThd<T>* pRoot, BinaryTreeNodeThd<T>*& prev)	{		if (pRoot)		{			_PostThread(pRoot->_pLeft,prev);// 线索化左子树			_PostThread(pRoot->_pRight,prev); //线索化右子树			if (pRoot->_pLeft == NULL)			{				pRoot->_LeftThread = THREAD;				pRoot->_pLeft = prev;			}						if (prev && prev->_pRight == NULL)			{				prev->_RightThread = THREAD;				prev->_pRight = pRoot;			}			prev = pRoot;		}	} 
后序遍历线索二叉树：
 思路：（1）找到最左边的节点(分为两种情况 ：存在右子树 ，不存在右子树)
    （2）while循环一直遍历节点的后继（prev保存上一次访问的节点）注意左单支
跳出循环条件：当前节点有右子树或者可能到根节点
    （3）跳出循环：判断是否为根节点：如果根节点没有右子树，直接访问return退出
    （4）当前节点不为根节点，循环访问当前节点的双亲节点  注意右单支
    （5）最后判断是否为有右子树，当前节点指向其右子树
  
代码:
 
	void PostOrder()	{		_PostOrder(_pRoot);	}        void _PostOrder(BinaryTreeNodeThd<T>* pRoot) 	{		BinaryTreeNodeThd<T>* pCur = pRoot; 		BinaryTreeNodeThd<T>* prev = NULL; //保存上一次访问的节点		while (pCur)		{			//找最左边的节点			while (pCur->_LeftThread == LINK && pCur->_pLeft != prev) //防止陷入死循环  			{				pCur = pCur->_pLeft;			} //跳出循环的条件：pCur为最左边的节点						//访问节点的后继			while (pCur && THREAD == pCur->_RightThread) // 			{				cout << pCur->_data << " ";				prev = pCur; //perv记录已经访问过的节点				pCur = pCur->_pRight;			}//跳出循环的条件：pCur为空（即左单支情况） 节点有右子树，节点为根节点			//跳出循环，判断是否为根节点			if (pCur == pRoot && pCur->_pRight == prev)			{				cout << pCur->_data << " ";				return;			}			//不是根节点，访问当前节点的双亲节点			while (pCur && pCur->_pRight == prev) // 注意 右单支情况			{				cout << pCur->_data << " ";				prev = pCur;				pCur = pCur->_pParent;			}			// 判断根节点是否有右子树			if (pCur && pCur->_RightThread == LINK)			{				pCur = pCur->_pRight;			}		}	}
  代码测试分析：
 
  测试代码：
void FunTest2(){	char* pTreeInfo = "1245##6#7###3";	BinaryTreeThd<char> bt(pTreeInfo, strlen(pTreeInfo));	bt.PostThread();	bt.PostOrder(); //结果:5764231}
测试一下特殊的右单支的情况：
        
 分析右单支：注意（3）步
     
测试一下特殊的左单支：所以循环访问后继的时候需要加判断pCur是否为空