线索化二叉树：

利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。

中序（左根右）：

前序（根左右）：

注意：因为++index返回对象 index++返回临时变量 传引用时只能用++index。

前序、中序的线索化及遍历具体实现如下：

#pragmaonceenum{THREAD,LINK,};typedefintPointerTag;template<classT>structBinaryTreeNodeThd{T_data;//数据BinaryTreeNodeThd<T>*_left;//左孩子BinaryTreeNodeThd<T>*_right;//右孩子PointerTag_leftTag;//左孩子线索化标志PointerTag_rightTag;//右孩子线索化标志BinaryTreeNodeThd(constT&x):_data(x),_left(NULL),_right(NULL),_leftTag(LINK),_rightTag(LINK){}};template<classT>classBinaryTreeThd{typedefBinaryTreeNodeThd<T>Node;public://构造BinaryTreeThd():_root(NULL){}//a--树的节点前序遍历的数组size--数组中元素个数invaild--无效值即节点为空BinaryTreeThd(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreateTree(a,size,invalid,index);}//析构~BinaryTreeThd(){_Destory(_root);_root=NULL;}//拷贝BinaryTreeThd(constBinaryTreeThd<T>&t){_root=_Copy(t._root);}//赋值重载(传统)//BinaryTreeThd<T>&operator=(constBinaryTreeThd<T>&t)//{//if(this!=&t)//{//Node*tmp=_Copy(t._root);//_Destory(_root);//_root=tmp;//}//return*this;//}//赋值重载(现代)BinaryTreeThd<T>&operator=(BinaryTreeThd<T>t){swap(_root,t._root);return*this;}T&operator->(){return_root;}public://线索化voidPrevOrderThread()//前序{Node*prev=NULL;return_PrevOrderThread(_root,prev);}voidInOrderThread()//中序{Node*prev=NULL;return_InOrderThread(_root,prev);}voidPostOrderThread()//后序{Node*prev=NULL;return_PostOrderThread(_root,prev);}//线索化遍历voidPrevOrderThd()//前序遍历（法一）{if(_root==NULL)return;Node*cur=_root;while(cur){//找最左节点while(cur->_leftTag==LINK){cout<<cur->_data<<"";cur=cur->_left;}cout<<cur->_data<<"";//访问右子树cur=cur->_right;}cout<<endl;}voidPrevOrderThd_O()//前序遍历（法二）{if(_root==NULL)return;Node*cur=_root;while(cur){cout<<cur->_data<<"";//找最左节点if(cur->_leftTag==LINK){cur=cur->_left;}else//访问右子树{cur=cur->_right;}}cout<<endl;}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;}voidPostOrderThd();//后序遍历protected://注意此处index要用引用传参Node*_CreateTree(constT*a,size_tsize,constT&invalid,size_t&index){Node*root=NULL;if((index<size)&&(a[index]!=invalid)){root=newNode(a[index]);//注意下面只能用++index。因为++index返回对象index++返回临时变量此处传的是引用root->_left=_CreateTree(a,size,invalid,++index);root->_right=_CreateTree(a,size,invalid,++index);}returnroot;}void_Destory(Node*root){if(root==NULL)return;_Destroy(root->_left);_Destroy(root->_right);deleteroot;}Node*_Copy(Node*root){if(root==NULL)returnNULL;NOde*newRoot=newNode(root->_data);newRoot->_left=_Copy(root->_left);newRoot->_right=_Copy(root->_right);returnnewRoot;}//前序线索化void_PrevOrderThread(Node*cur,Node*&prev){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)//线索化左子树_PrevOrderThread(cur->_left,prev);if(cur->_rightTag==LINK)//线索化右子树_PrevOrderThread(cur->_right,prev);}//中序线索化void_InOrderThread(Node*cur,Node*&prev){if(cur==NULL)return;_InOrderThread(cur->_left,prev);//置前驱线索if(cur->_left==NULL){cur->_leftTag=THREAD;cur->_left=prev;}//置后继线索if(prev&&prev->_right==NULL){prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;_InOrderThread(cur->_right,prev);}//后序线索化void_PostThread(Node*cur,Node*&prev);private:Node*_root;};

测试代码：

voidTestInOrder(){inta1[10]={1,2,3,'#','#',4,'#','#',5,6};size_tsize=sizeof(a1)/sizeof(int);BinaryTreeThd<int>t1=BinaryTreeThd<int>(a1,size,'#');t1.InOrderThread();cout<<"中序后：";t1.InOrderThd();}voidTestPrev(){inta1[10]={1,2,3,'#','#',4,'#','#',5,6};size_tsize=sizeof(a1)/sizeof(int);BinaryTreeThd<int>t1=BinaryTreeThd<int>(a1,size,'#');t1.PrevOrderThread();cout<<"前序后(1)：";t1.PrevOrderThd();cout<<"前序后(2)：";t1.PrevOrderThd_O();}