線索二叉樹的前序、中序

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

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

結(jié)點信息如下

enum PointerTag{ THREAD, LINK };

template<class T>
struct BinaryTreeNodeThd
{
	T _data;                      //數(shù)據(jù)
	BinaryTreeNodeThd<T>* _left;  //左孩子
	BinaryTreeNodeThd<T>* _right; //右孩子
	PointerTag _leftTag;          //左孩子線索標(biāo)志
	PointerTag _rightTag;         //右孩子線索標(biāo)志
};

其前序結(jié)構(gòu)如下

其中序結(jié)構(gòu)如下

程序?qū)崿F(xiàn)：

#include<iostream>

using namespace std;

enum PointerTag{ THREAD, LINK };

template<class T>
struct BinaryTreeNodeThd
{
	T _data;                      //數(shù)據(jù)
	BinaryTreeNodeThd<T>* _left;  //左孩子
	BinaryTreeNodeThd<T>* _right; //右孩子
	PointerTag _leftTag;          //左孩子線索標(biāo)志
	PointerTag _rightTag;         //右孩子線索標(biāo)志
	
	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)//前驅(qū)的右孩子為空
		{
			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;
}