【二叉树】线索化二叉树

线索化二叉树：

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

中序（左根右）：

前序（根左右）：

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

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

#pragma once

enum
{
	THREAD,
	LINK,
};

typedef int PointerTag;

template<class T>
struct BinaryTreeNodeThd
{
	T _data;                      //数据
	BinaryTreeNodeThd<T>* _left;  //左孩子  
	BinaryTreeNodeThd<T>* _right; //右孩子
	PointerTag _leftTag;          //左孩子线索化标志  
	PointerTag _rightTag;          //右孩子线索化标志

	BinaryTreeNodeThd(const T& x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
		, _leftTag(LINK)
		, _rightTag(LINK)
	{}
};

template<class T>
class BinaryTreeThd
{
	typedef BinaryTreeNodeThd<T> 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>& t)
	{
		_root = _Copy(t._root);
	}
	//赋值重载(传统)
	//BinaryTreeThd<T>& operator=(const BinaryTreeThd<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:
	//线索化
	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<int> t1 = BinaryTreeThd<int>(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<int> t1 = BinaryTreeThd<int>(a1, size, '#');

        t1.PrevOrderThread();
	cout << "前序后(1)：";     
	t1.PrevOrderThd();
	cout << "前序后(2)：";      
	t1.PrevOrderThd_O();
}