数据结构-二叉树的线索化

#PRagma once#include <iostream>using namespace std;enum Type{	LINK,  //指针指向的是一颗子树	THREAD //指针指向的是线索化};template<typename T>struct BinaryTreeThdNode{	T _data;	BinaryTreeThdNode* _left;	BinaryTreeThdNode* _right;	Type _left_type;	Type _right_type;	BinaryTreeThdNode(const T& data)		:_data(data)		, _left(NULL)		, _right(NULL)		, _left_type(LINK)		, _right_type(LINK)	{}};template <typename T>class BinaryTreeThd{	typedef BinaryTreeThdNode<T> Node;public:	BinaryTreeThd(T* a, size_t size, const T& invalid=T())	{		size_t index = 0;		_root = _CreatTree(a, size, index, invalid);	}	void PrevOrderThreading() //先序线索化	{		Node* prev = NULL;		_PrevOrderThreading(_root, prev);	}	void InOrderThreading() //中序线索化	{		Node* prev = NULL;		_InOrderThreading(_root, prev);		if (prev && prev->_right == NULL)			prev->_right_type = THREAD;	}	void PrevOrderThd() //先序线索化遍历	{		Node* cur = _root;		while (cur)		{			while (cur->_left_type == LINK)			{				cout << cur->_data << " ";				cur = cur->_left;			}			cout << cur->_data << " ";			cur = cur->_right;		}		cout << endl;	}	void InOrderThd() //中序线索化遍历	{		Node* cur = _root;		while (cur)		{			//寻找最左节点并访问			while (cur->_left_type == LINK)			{				cur = cur->_left;			}			cout << cur->_data << " ";			while (cur && cur->_right_type == THREAD)			{				cur = cur->_right;				if (cur)					cout << cur->_data << " ";			}			if (cur)				cur = cur->_right;		}		cout << endl;	}protected:	Node* _CreatTree(T* a, size_t size, size_t& index, const T& invalid = T())	{		if (a[index] == invalid || index >= size)			return NULL;		Node* root = new Node(a[index]);		root->_left = _CreatTree(a, size, ++index, invalid);		root->_right = _CreatTree(a, size, ++index, invalid);		return root;	}	void _InOrderThreading(Node* root, Node*& prev)	{		Node* cur = root;		if (cur == NULL)			return;		_InOrderThreading(cur->_left, prev);		if (cur->_left == NULL)		{			cur->_left = prev;			cur->_left_type = THREAD;		}		if (prev && prev->_right == NULL)		{			prev->_right = cur;			prev->_right_type = THREAD;		}		prev = cur;		_InOrderThreading(cur->_right, prev);	}	void _PrevOrderThreading(Node* root, Node*& prev)	{		Node* cur = root;		if (cur == NULL)			return;			if (cur->_left == NULL)		{			cur->_left = prev;			cur->_left_type = THREAD;		}		if (prev && prev->_right == NULL)		{			prev->_right = cur;			prev->_right_type = THREAD;		}		prev = cur;		if (cur->_left_type != THREAD)			_PrevOrderThreading(cur->_left, prev);		if (cur->_right_type != THREAD)			_PrevOrderThreading(cur->_right, prev);	}protected:	Node* _root;};