线索化二叉树-创新互联

二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只

能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。

   为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。

enum PointerTag

{

LINK,  //0

THREAD  //1

};

template

struct BitreeNodeTH

{

T Data;

BitreeNodeTH *left;  //左孩子

BitreeNodeTH *right; //右孩子

PointerTag left_Tag;  //左孩子线索标志

PointerTag right_Tag; //右孩子线索标志

BitreeNodeTH(T data = T())

:Data(data)

,left(NULL)

,right(NULL)

,left_Tag(LINK)

,right_Tag(LINK)

{}

};

一个线索二叉树的节点：

线索化二叉树的主要源代码：

建树：

	BitreeNodeTH* Create_tree(T *arr,int sz,int &i)
	{
		if(*arr==NULL||arr[i]=='#'||i>=sz)
			return NULL;
		else 
		{
			BitreeNodeTH *cur=new BitreeNodeTH;
			cur->Data=arr[i];
			i++;
			cur->left=Create_tree(arr,sz,i);
			i++;
			cur->right=Create_tree(arr,sz,i);
			return cur;
		}
	}

前序线索化：

	void FirstOrderTH(BitreeNodeTH* root, BitreeNodeTH* &prev)// &表示没有开辟临时变量
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
	 	if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev&&prev->right == NULL)
		{
			prev->right_Tag = THREAD;
			prev->right = cur;
		}
		prev = cur;
		if (cur->left_Tag == LINK)   //cur->left
			FirstOrderTH(cur->left,prev);
		if(cur->right_Tag == LINK)   //cur->right
			FirstOrderTH(cur->right, prev);
	}

前序遍历：

	void FirstOrderTHing(BitreeNodeTH* root)
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
		while (cur)
		{
			while(cur->left_Tag == LINK)
			{
				cout<Data<<" ";
				cur = cur->left;
			}
			cout << cur->Data<<" ";
			if (cur->left_Tag == THREAD)
			{
				cur = cur->right;
			}
		}
	}

中序线索化：

void MidOrderTH(BitreeNodeTH* root, BitreeNodeTH* &prev)
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
		MidOrderTH(cur->left,prev);
		if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev && prev->right == NULL)
		{
			prev->right = cur;
			prev->right_Tag = THREAD;
		}
		prev = cur;
		MidOrderTH(cur->right,prev);
	}

中序遍历：

void MidOrderTHing(BitreeNodeTH* root)
	{
		BitreeNodeTH* cur = root;
		while(cur)
		{
			while (cur->left_Tag == LINK)
			{
				cur = cur->left;
			}
			cout<Data<<" ";
			while (cur->right_Tag == THREAD)
			{
				cur = cur->right;
				cout << cur->Data<< " ";
			}
			if (cur->right_Tag == LINK)
			{
				cur = cur->right;
			}
		}
	}

后序线索化：

void LaterOrderTH(BitreeNodeTH* root, BitreeNodeTH* &prev)
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
		LaterOrderTH(cur->left,prev);
		LaterOrderTH(cur->right,prev);
	 

		if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev&&prev->right == NULL)
		{
			prev->right = cur;
			prev->right_Tag = THREAD;
		}
		prev = cur;
	}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。