線索二叉樹的前序、中序

    二叉樹是一種非線性結構，遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實現非遞歸的遍歷。用二叉樹作為存儲結構時，取到一個節點，只能獲取節點的左孩子和右孩子，不能直接得到節點的任一遍歷序列的前驅或者后繼。

    而線索二叉樹利用二叉樹中指向左右子樹的空指針來存放節點的前驅和后繼信息

結點信息如下

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;
}