线索化二叉树：

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

LChild（左孩子） Ltag（左线索标志） Data Rtag（右线索标志） RChild（右孩子）

中序（左根右）：

前序（根左右）：

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

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

#pragma onceenum{	THREAD,	LINK,};typedef int PointerTag;template
     
      struct BinaryTreeNodeThd{	T _data;                      //数据	BinaryTreeNodeThd
      
       * _left;  //左孩子  	BinaryTreeNodeThd
       
        * _right; //右孩子	PointerTag _leftTag;          //左孩子线索化标志  	PointerTag _rightTag;          //右孩子线索化标志	BinaryTreeNodeThd(const T& x)		:_data(x)		, _left(NULL)		, _right(NULL)		, _leftTag(LINK)		, _rightTag(LINK)	{}};template
        
         class BinaryTreeThd{	typedef BinaryTreeNodeThd
         
           Node;public:	//构造	BinaryTreeThd()		:_root(NULL)	{}	// a--树的节点前序遍历的数组  size--数组中元素个数  invaild--无效值即节点为空	BinaryTreeThd(const T* a, size_t size, const T& invalid)	{		size_t index = 0;		_root = _CreateTree(a, size, invalid, index);	}	//析构	~BinaryTreeThd()	{		_Destory(_root);		_root = NULL;	}	//拷贝  	BinaryTreeThd(const BinaryTreeThd
          
           & t) { _root = _Copy(t._root); } //赋值重载(传统) //BinaryTreeThd
           
            & operator=(const BinaryTreeThd
            
             & t) //{ // if (this != &t) // { // Node* tmp = _Copy(t._root); // _Destory(_root); // _root = tmp; // } // return *this; //} //赋值重载(现代) BinaryTreeThd
             
              & operator=(BinaryTreeThd
              
                t) { swap(_root, t._root); return *this; } T& operator->() { return _root; }public: //线索化 void PrevOrderThread()  //前序 { Node* prev = NULL; return _PrevOrderThread(_root, prev); } void InOrderThread()   //中序 { Node* prev = NULL; return _InOrderThread(_root, prev); } void PostOrderThread()  //后序 { Node* prev = NULL; return _PostOrderThread(_root, prev); } //线索化遍历 void PrevOrderThd()  //前序遍历（法一） { 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; } void PrevOrderThd_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; } void InOrderThd() //中序遍历 { 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; } void PostOrderThd();   //后序遍历protected:        //注意 此处index要用引用传参 Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)  { Node* root = NULL; if ((index < size) && (a[index] != invalid)) { root = new Node(a[index]);       //注意下面只能用++index。因为++index返回对象index++返回临时变量 此处传的是引用 root->_left = _CreateTree(a, size, invalid, ++index); root->_right = _CreateTree(a, size, invalid, ++index); } return root; } void _Destory(Node* root) { if (root == NULL) return; _Destroy(root->_left); _Destroy(root->_right); delete root; } Node* _Copy(Node* root) { if (root == NULL) return NULL; NOde* newRoot = new Node(root->_data); newRoot->_left = _Copy(root->_left); newRoot->_right = _Copy(root->_right); return newRoot; }        //前序线索化 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;};

测试代码：

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