二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。


为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。



代码结构如下：

enumPointerTag{THREAD,LINK};template<classT>structBinaryTreeNode{T_data;BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;PointerTag_leftTag;//左孩子线索标志PointerTag_rightTag;//右孩子线索标志BinaryTreeNode(constT&d):_data(d),_left(NULL),_right(NULL){_leftTag=LINK;_rightTag=LINK;}};

代码实现如下：

voidInOrderThreading()//中序线索化{Node*prev=NULL;_InOrderThreading(_root,prev);}voidPrevOrderThreading()//前序线索化{Node*prev=NULL;_PrevOrderThreading(_root,prev);}//voidPostOrderThreading()//后序线索化//{//Node*prev=NULL;//_PostOrderThreading(_root,prev);//}voidInOrderThd()//中序遍历{Node*cur=_root;while(cur){while(cur->_leftTag==LINK){cur=cur->_left;}cout<<cur->_data<<"";while(cur->_rightTag==THREAD){cur=cur->_right;cout<<cur->_data<<"";}cur=cur->_right;}cout<<endl;}voidPrevOrderThd()//前序遍历{Node*cur=_root;while(cur){cout<<cur->_data<<"";while(cur->_leftTag==LINK){cur=cur->_left;cout<<cur->_data<<"";}cur=cur->_right;}cout<<endl;}void_InOrderThreading(Node*root,Node*&prev)//{if(root==NULL){return;}_InOrderThreading(root->_left,prev);if(root->_left==NULL){root->_leftTag=THREAD;root->_left=prev;}if(prev&&(prev->_right==NULL)){prev->_rightTag=THREAD;prev->_right=root;}prev=root;_InOrderThreading(root->_right,prev);}void_PrevOrderThreading(Node*root,Node*&prev){Node*cur=root;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);}}

因为后序比较复杂，所以露珠不是很有能力写出来。以后露珠会好好提高自己，然后把后序实现了哈哈哈哈