#define _CRT_SECURE_NO_WARNINGS 1#include
     
      using namespace std;enum PointerTag { THREAD, LINK };     //枚举前言：为了遍历的方便，我们在二叉树中引入前驱和后序，这样就储存了相关信息。其结构如下：
     

template 
     
      struct BinaryTreeThdNode{	T _data;                         // 数据	BinaryTreeThdNode
      
       * _left;   // 左孩子	BinaryTreeThdNode
       
        * _right;  // 右孩子	PointerTag   _leftTag;          // 左孩子线索标志	PointerTag   _rightTag;         // 右孩子线索标志	BinaryTreeThdNode(const T& x)		:_left(NULL)		, _right(NULL)		, _leftTag(LINK)		, _rightTag(LINK)		, _data(x)	{}};template
        
         class BinaryTreeThd{	typedef BinaryTreeThdNode
         
           Node;public:	BinaryTreeThd(int* a, size_t size, const T& invalid)	{		size_t index = 0;		_root = _CreateTreeThd(a, size, invalid, index);	}	Node* _CreateTreeThd(int* a, size_t size, const T& invalid, size_t& index)	{		Node* root = NULL;		if (index < size && a[index] != invalid)		{			root = new Node(a[index]);			root->_left = _CreateTreeThd(a, size, invalid, ++index);			root->_right = _CreateTreeThd(a, size, invalid, ++index);		}		return root;	}	//void PrevOrderThreading();   //前序	//	void PostOrderThreading();   //后序	void InOrderThreading()  //用递归实现中序线索化二叉树	{		Node* prev = NULL;		_InOrderThreading(_root, prev);	}	void InOrder()    //递归打印	{		_InOrder(_root);		cout << endl;	}protected:	void _InOrderThreading(Node* root, Node* prev)  //递归实现线索化二叉树	{		if (root == NULL)			return;		if (root->_leftTag == LINK)			_InOrderThreading(root->_left, prev);		if (root->_left == NULL)		{			root->_left = prev;			root->_leftTag = THREAD;		}		if (root->_right == NULL)		{			root->_rightTag = THREAD;		}		if (prev != NULL && prev->_rightTag == THREAD)		{			prev->_right = root;		}		prev = root;		if (root->_rightTag == LINK)			_InOrderThreading(root->_right, prev);	}	void InOrderThreading()      /*用栈线索化二叉树*/	{		stack
          
            s; Node* prev = NULL; Node* cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } cur = s.top(); s.pop(); if (cur->_left == NULL) { cur->_left = prev; cur->_leftTag = THREAD; } prev = cur; if (cur->_right == NULL && !s.empty()) { cur->_right = s.top(); cur->_rightTag = THREAD; cur = NULL; } else { cur = cur->_right; } } } void _InOrder(Node* root)   //递归打印线索化二叉树 { if (root == NULL) return; if (root->_leftTag == LINK) _InOrder(root->_left); cout << root->_data << " "; if (root->_rightTag == LINK) { _InOrder(root->_right); } } void InOrder()      //用栈打印 { if (_root == NULL) return; Node* cur = _root; while (cur) { while (cur->_left) { cur = cur->_left; } cut << cur->_data << " "; if (cur->_rightTag == THREAD) { cout << cur->_right->_data << " "; cur = cur->_right; } else if (cur->_right == LINK) { } } } void InOrderM()      //循环打印 { Node* cur = _root; while (cur) { while (cur->_leftTag == LINK) cur = cur->_left; cout << cur->_data << " "; while (cur->_rightTag == THREAD) { cur = cur->_right; if (cur == NULL) { cout << endl; return; } cout << cur->_data << " "; }  cur = cur->_right; } } Node* _root;};void test(){ int a[] = { 1, 2, '#', 3, 4, 5, '#', 6 }; BinaryTreeThd
           
             b(a, 8, '#'); b.InOrderThreading(); b.InOrder();}int main(){ test(); system("pause"); return 0;}