线索二叉树的前序、中序

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

创新互联企业建站,10年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于成都网站制作、网站建设、外贸网站建设中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。

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

结点信息如下

enum PointerTag{ THREAD, LINK };

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

其前序结构如下

其中序结构如下

程序实现：

#include

using namespace std;

enum PointerTag{ THREAD, LINK };

template
struct BinaryTreeNodeThd
{
	T _data;                      //数据
	BinaryTreeNodeThd* _left;  //左孩子
	BinaryTreeNodeThd* _right; //右孩子
	PointerTag _leftTag;          //左孩子线索标志
	PointerTag _rightTag;         //右孩子线索标志
	
	BinaryTreeNodeThd(const T& x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
		, _leftTag(LINK)
		, _rightTag(LINK)
	{}
};

template
class BinaryTreeThd
{
	typedef BinaryTreeNodeThd 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 t1(a1, 10, '#');
	cout << endl << "中序遍历：";
	t1.InOrderThreading();
	t1.InOrderThd();
	cout << "前序遍历" << endl;
	BinaryTreeThdt2(a1, 10, '#');
	t2.PrevOderThreading();
	t2.PrevOrderThd();
	getchar();
	return 0;
}