线索二叉树的前序、中序

    二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。

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

结点信息如下

enum PointerTag{ THREAD, LINK };

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

其前序结构如下

其中序结构如下

程序实现：

#include<iostream>

using namespace std;

enum PointerTag{ THREAD, LINK };

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)
	{}
	BinaryTreeThd(const T*a, size_t size, const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size, index, invalid);
	}
	void InOrderThreading()//中序线索化
	{
		Node*prev = NULL;
		_InOrderThreading(_root, prev);
	}
	void PrevOderThreading()//前序线索化
	{
		Node*prev = NULL;
		_PrevOderThreading(_root, prev);
	}
		
	void InOrderThd()//中序遍历
	{
		_InOrderThd(_root);
	}
	void PrevOrderThd()//前序遍历
	{
	_PrevOrderThd(_root);
	}
protected:
	Node* _CreateTree(const T*a, size_t size, size_t& index, const T& invalid)
	{
		Node* _root = NULL;
		
		if (index < size&&a[index] != invalid)
		{
			_root = new Node(a[index]);
			_root->_left = _CreateTree(a, size, ++index, invalid);
			_root->_right = _CreateTree(a, size, ++index, invalid);
		}
		return _root;
	}
	
	void _PrevOderThreading(Node* root, Node*& prev)//前序线索化
	{
		if (root == NULL)
			return;
		
		if (root->_left == NULL)
		{
			root->_leftTag = THREAD;
			root->_left	= prev;
		}
		
		if (prev&&prev->_right == NULL)
		{
			prev->_rightTag = THREAD;
			prev->_right = root;
		}
		prev = root;
		if (root->_leftTag == LINK)//递归
		{
			_PrevOderThreading(root->_left,prev);//线索化左子树
		}

		if (root->_rightTag == LINK)
		{
			_PrevOderThreading(root->_right,prev);//线索化右子树
		}
	}
	
	void _PrevOrderThd(Node* root)
	{
		Node*cur = root;
		
		while (cur)
		{
			while (cur->_leftTag == LINK)
			{
				cout << cur->_data << " ";
				cur = cur->_left;
			}
			cout << cur->_data << " ";
			cur = cur->_right;
		}
	}
	/*方法二
	void _PrevOrderThd(Node* root)
	{
		Node*cur = root;
		
		while (cur)
		{
			while (cur->_leftTag==LINK)
			{
				cout << cur->_data << " ";
				cur = cur->_left;
			}
			cout << cur->_data << " ";
			while (cur->_rightTag == THREAD)
			{
				cur = cur->_right;
				cout << cur->_data << " ";
			}
			if (cur->_leftTag == LINK)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
		}
	}*/
	void _InOrderThreading(Node* _root, Node* &prev)//中序线索化
	{
		if (_root == NULL)
		{
			return;
		}
		if (_root->_leftTag==LINK)
			_InOrderThreading(_root->_left,prev);
		//线索化
		if (_root->_left == NULL)//左孩子为空
		{
			_root->_leftTag = THREAD;
			_root->_left = prev;
		}
		if (prev != NULL&&prev->_right == NULL)//前驱的右孩子为空
		{
			prev->_rightTag = THREAD;
			prev->_right = _root;
		}
		prev = _root;

		if (_root->_rightTag==LINK)//线索化右孩子
			_InOrderThreading(_root->_right,prev);
	}

	void _InOrderThd(Node* _root)                  //中序遍历
	{
		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;
	}
protected:
	Node* _root;
};

测试

int main()
{
	int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
	BinaryTreeThd<int> t1(a1, 10, '#');
	cout << endl << "中序遍历：";
	t1.InOrderThreading();
	t1.InOrderThd();
	cout << "前序遍历" << endl;
	BinaryTreeThd<int>t2(a1, 10, '#');
	t2.PrevOderThreading();
	t2.PrevOrderThd();
	getchar();
	return 0;
}