【数据结构】二叉树的线索化

	void  _CreateTree(Node*& root,T a[],size_t size,size_t& index,const T& invalid)
	{
		assert(a);
		if(index< size&& a[index]!=invalid)
		{
			root=new Node(a[index]);
			_CreateTree(root->leftchild,a,size,++index,invalid);
			_CreateTree(root->rightchild,invalid);

		}
	}

void _InOrderThead(Node* root,Node* &pre)
	{
     if(root==NULL)
	 return ;
	 _InOrderThead(root->leftchild,pre);
	 if(root->leftchild==NULL)
	 {
		 root->LeftTag=Thread;
		 root->leftchild=pre;
	 }
	 if(pre&&pre->rightchild==NULL)
	 {
		 pre->RightTag=Thread;
		 pre->rightchild=root;
	 }
	 pre=root;
	 _InOrderThead(root->rightchild,pre);
	}

void _PrevOrderThead(Node* root,Node* &pre)
	{
		if(root==NULL)
			return ;
		if(root->leftchild==NULL)
		{
			root->LeftTag=Thread;
			root->leftchild=pre;
		}
		if(pre&&pre->rightchild==NULL)
		{
			pre->RightTag=Thread;
			pre->rightchild=root;
		}
		pre=root;
		if(root->LeftTag==Link)
			_PrevOrderThead(root->leftchild,pre);
		if(root->RightTag==Link)
			_PrevOrderThead(root->rightchild,pre);
	}

void _PostOrderThead(Node* root,Node* &pre)
	{
		if(root==NULL)
			return;
		_PostOrderThead(root->leftchild,pre);
		_PostOrderThead(root->rightchild,pre);
		if(root->leftchild==NULL)
		{
			root->LeftTag=Thread;
			root->leftchild=pre;
		}
		if(pre&&pre->rightchild==NULL)
		{
			pre->RightTag=Thread;
			pre->rightchild=root;
		}
		pre=root;
	}

#include<iostream>
#include<stack>
#include<queue>
#include <assert.h>
using namespace std;
enum PointTag
{
	Link,//指针
	Thread//线索
};
template <class T>
struct  BinTreeNode
{
	T _date;
    BinTreeNode<T>* leftchild;//左孩子
	BinTreeNode<T>* rightchild;//右孩子
	PointTag LeftTag;//左孩子线索化标志
	PointTag RightTag;//右孩子线索化标志
	BinTreeNode(const T& x)
		:_date(x),leftchild(NULL),rightchild(NULL),LeftTag(Link),RightTag(Link)

	{}
};
template <class T>
class BinTree
{
	typedef BinTreeNode<T> Node;
public:
	BinTree()
		:_root(NULL)
	{}
	BinTree(T* a,const T& invalid)
		:_root(NULL)
	{
		size_t index=0;
		_CreateTree( _root,index,invalid);
	}
	void PrevOrderThead()
	{
		Node* pre=NULL;
		_PrevOrderThead(_root,pre);
	}
	void PrevOrder_NonR()
	{
		Node* root=_root;
		if(root==NULL)
			return;
		while(root)
		{
			while(root->LeftTag==Link)
			{

				cout<<root->_date<<" ";
				root=root->leftchild;
			}
			cout<<root->_date<<" ";
			root=root->rightchild;
		}
		cout<<endl;
	}
	void InOrderThead()
	{
		Node* pre=NULL;
		_InOrderThead(_root,pre);
	}
	void InOrder_NonR()
	{
		Node* root=_root;
		if(root==NULL)
			return;
		while(root)
		{
			while(root->LeftTag==Link)
			{
				root=root->leftchild;
			}
			cout<<root->_date<<" ";
			while (root->RightTag==Thread)
			{
				root=root->rightchild;
				cout<<root->_date<<" ";
			}
            root=root->rightchild;
		}
		cout<<endl;
	}
	void PostOrderThead()
	{
		Node* pre=NULL;
		_PostOrderThead(_root,pre);
	}
	void PostOrder_NonR()
	{
	}
protected:
	void  _CreateTree(Node*& root,invalid);

		}
	}
	void _InOrderThead(Node* root,pre);
	}
	void _PrevOrderThead(Node* root,pre);
	}
	void _PostOrderThead(Node* root,pre);
		if(root->leftchild==NULL)
		{
			root->LeftTag=Thread;
			root->leftchild=pre;
		}
		if(pre&&pre->rightchild==NULL)
		{
			pre->RightTag=Thread;
			pre->rightchild=root;
		}
		pre=root;
	}
private:
	Node* _root;
};