二叉树的线索化，这几天以来我很难掌握，今天终于想通了，哈哈，首先我们来看看二叉树线索化之后会变成什么样子，这里我们以图中的二叉树为例，图如下：

画的太糙，各位看官讲究着看吧- -。所谓二叉树的线索化，就是当一个节点的左右指针为空时，就让它的左右指针指向该节点的前驱或者后继（一般来说左指针指向前驱，右指针指向后继）。这里不论指向前驱或者后继，我们都应该线索化时，至少要明确两个节点指针的值，当前节点和当前节点的前驱/后继。这也是线索化的两种思路：

保存前驱：访问当前节点时若当前节点的左指针为空，则令左指针指向前驱，若前驱的右指针为空，则令前驱的右指针指向当前节点，代码描述如下：

voidvisit(NODE*cur,NODE*&prev)//当前指针的前驱在当前指针访问时会改变，故传引用用来改变//prev{if(prev->right==NULL;prev->right=cur;if(cur->left==NULL)cur->left=prev;prev=cur;}

这里我们要注意的是应该先进行访问，最后再改变prev的值。

保存后继：这种方法很难做到，并且个人觉得没有什么意义，因为在遍历整个数的过程中我们始终都会访问到一个节点的后继，若将要访问后继那我们如何保存到未来的东西，即使通过类似栈的数据结构通过压栈来强行访问，效率也是不高的，在此不推荐。

接下来献上c++完整的线索二叉树结构以及中序线索化过程，通过递归与非递归两种方式实现，其他的都大同小异。

节点类定义如下：

typedefcharDatatype;enumNodeType{LINK,THERAD};structTheardBinaryTreeNode{TheardBinaryTreeNode*_left;TheardBinaryTreeNode*_right;NodeType_leftTag;NodeType_rightTag;Datatype_data;TheardBinaryTreeNode(constDatatype&data):_left(NULL),_right(NULL),_leftTag(LINK),_rightTag(LINK),_data(data){}TheardBinaryTreeNode():_left(NULL),_right(NULL),_leftTag(LINK),_rightTag(LINK),_data((Datatype)0){}};

中序线索化如下：

voidInTherad(){NODE*prev=NULL;_InTherad(_root,prev);//stack<NODE*>s;//借助栈来实现非递归的中序线索化//NODE*cur=_root;//NODE*prev=NULL;//while(!s.empty()||cur)//{//while(cur)//{//s.push(cur);//cur=cur->_left;//}//NODE*top=s.top();//s.pop();//if(top->_left==NULL&&top->_leftTag==LINK)//{//top->_left=prev;//top->_leftTag=THERAD;//}//prev=top;//if(top->_right==NULL&&top->_rightTag==LINK)//{//top->_rightTag=THERAD;//if(!s.empty())//top->_right=s.top();//}//else//cur=top->_right;//}}void_InTherad(NODE*root,NODE*&prev)//递归的中序线索化{if(root==NULL)return;_InTherad(root->_left,prev);if(prev&&prev->_rightTag==LINK&&prev->_right==NULL){prev->_right=root;prev->_rightTag=THERAD;}if(root->_leftTag==LINK&&root->_left==NULL){root->_leftTag=THERAD;root->_left=prev;prev=root;}_InTherad(root->_right,prev);}

如有不足或者疑问希望留言提出。3Q -3-。