数据结构-线索二叉树（后序线索二叉树及遍历）- 校招VIP

转载声明：文章来源 https://blog.csdn.net/SZU_Crayon/article/details/81125122

后序线索二叉树

（1）后序线索二叉树的构造

①思路：在这里说下构造的原因，与先序中序线索二叉树不同，在遍历时后序时先把孩子全部遍历了再回到父母节点，而回寻父母节点的方法只能在定义的节点结构中添加一指针，指向该节点的父母节点。

template
struct BT_Thread_Node
{
	T Data;
	BT_Thread_Node* Left_Child;
	BT_Thread_Node* Right_Child;
	BT_Thread_Node* Parent;	       //指向该节点的父母节点
	int Ltag;
	int Rtag;
};

②先序递归构造二叉树

就一点不同：传参多了一个父母节点，构建完当前节点后，该节点得指向父母节点，并且该节点作为其左右孩子的父母节点作为参数传至下一构造函数。

template
int Thread_Binary_tree::Create_Thread_BTree(BT_Thread_Node* &Tree,BT_Thread_Node* Parent_Node)
{
	int Data;
	cin >> Data;
	if (Data == -1)
		Tree = NULL;
	else
	{
		Tree = new BT_Thread_Node;
		Tree->Parent = Parent_Node;        //指向父母节点
		Tree->Data = Data;
		Tree->Ltag = Link;
		Tree->Rtag = Link;
		Create_Thread_BTree(Tree->Left_Child,Tree);  //Tree是孩子的父母节点
		Create_Thread_BTree(Tree->Right_Child,Tree);
	}
	return 1;
}

（2）后序线索化

①思路：

a.先线索化左右孩子节点

b.根节点：若左孩子节点空，左孩子节点指向前驱节点（前一次访问的节点Pre_Node），标记该孩子为线索模式（Thread）

若前一次访问的节点不为空并且它的右孩子为空，则该右孩子指向当前节点（后继节点），标记该孩子为线索模式（Thread）

c.保存当前节点，作为下一次的Pre_Node (记录历史的意思）

②实现代码：

#define Link	0	//表示该节点有非空孩子节点
#define Thread	1	//表示该节点有后续节点（对于右子树来说）

template
void Thread_Binary_tree::PostOrder_Thread_Op(BT_Thread_Node* &Tree)
{
	if (Tree == NULL)
		return;
	
	PostOrder_Thread_Op(Tree->Left_Child);		//左
	PostOrder_Thread_Op(Tree->Right_Child);		//右
 
	if (Tree->Left_Child == NULL)		//根
	{
		Tree->Left_Child = Pre_Node;
		Tree->Ltag = Thread;
	}
	if (Pre_Node != NULL && Pre_Node->Right_Child == NULL)
	{
		Pre_Node->Right_Child = Tree;
		Pre_Node->Rtag = Thread;
	}
 
	Pre_Node = Tree;
}

注意！！！！！Pre_Node 是作为类内私有数据，相当于全局变量，对每个节点的线索都会使它改变！

（3）中序线索遍历

①思路：

a.靠左访问：找到最左边的节点，也就是后序遍历顺序中最先访问的那个节点

b.按后继线索访问：当前节点的右孩子节点指向的是后继，则访问该节点并指向下一右孩子直到该孩子不为后继节点。记得保存每次访问的节点哦，便于后面判断袖珍树（子树）是否访问完成。

c.回到根部：后面会放出一个例子，在ab两部分操作后，

会出现两种情况

1：该节点为根节点，访问最后这一节点后，整个后序遍历完成啦，跳出。

2：是节点是子树的根节点，访问这一节点后完成的是子树的后序遍历，这时肯定是回到该子树根节点的父母节点，然后指向该父母节点的右孩子进行下一次的遍历。

②实现代码：

template
void Thread_Binary_tree::_PostOrder_Op(BT_Thread_Node* &Tree)
{
	if (Tree == NULL)
		return;
	
	BT_Thread_Node *Cur_Node = Tree;
	Pre_Node = NULL;
	while (Cur_Node != NULL)
	{
		//个人觉得，Cur_Node->Ltag == Link会影响找到最左节点，但就测试数据来看，两个都ok
		//while (Cur_Node->Left_Child != Pre_Node && Cur_Node->Ltag == Link)
		while (Cur_Node->Left_Child != Pre_Node)//change,找到起始节点（在左树的最左边）
		{
			Cur_Node = Cur_Node->Left_Child;
		}
 
		while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点
		{
			BT_Node_Stack[++Top] = Cur_Node;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新
			Cur_Node = Cur_Node->Right_Child;
		}
 
		if (Cur_Node == Tree)		//如果当前节点为根节点，说明遍历完成
		{
			BT_Node_Stack[++Top] = Cur_Node;
			cout << Cur_Node->Data << " ";
			return;
		}
 
		while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该袖珍树只差根就遍历完成
		{
			BT_Node_Stack[++Top] = Cur_Node;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;
			Cur_Node = Cur_Node->Parent;		//访问袖珍树后回到上一层
		}
 
		if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子
		{
			Cur_Node = Cur_Node->Right_Child;
		}
	}
}

把要访问的节点全部入栈？？？
答：为了方便析构。

③图解举栗

a.靠左访问：最左边的节点是D（先找，不访问）

b.按后继访问：看箭头！ D -> G -> E-> B（B的右子树不是线索啦，跳出，此时B还没有访问）

c.回到根部：显然回到的根部是B，并且是上面说的第二种情况！子树的根节点

怎么判断？还记得我说的要保存上一访问节点吗？上一访问节点是E，B的右子树指向E

判定的语句对于程序中的：while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node)

访问B后完成以B为根节点的子树（BDEG）的后序遍历，然后回到B的父母节点A

回到A（不访问A），直接指向它的右孩子C

大家注意！！对于a操作，不仅可以在链模式（左孩子存在的情况下）找，也可以寻找该节点的前驱！！

我的锅这个图其实C的左孩子是指向F，为了易懂我还没画出来。

回到遍历：到了C之后，又是重复abc操作啦，靠左孩子访问到了F（C的左孩子节点指向它的前驱节点F），再后继访问到C，最后回到根部A，遍历完成。

（4）析构线索树

在写中序线索树的时候我是比较傻，又写了一遍线索遍历，这次干脆在遍历的时候就把节点入栈，便于删除。

①实现代码：

template
Thread_Binary_tree::~Thread_Binary_tree()
{
	while (Top != -1)
	{
		delete BT_Node_Stack[Top];
		Top--;
	}
}

到这再bb两句，重要的！和先序还有中序线索不同的是

一节点的定义：多了个指向父母节点的指针

二保存上一访问节点：为了判断子树是否遍历完成，需记录

到这基础就讲完啦，看看类实现代码吧~

后序线索二叉树类实现

（1）类定义包括常量定义

老思路，实现与接口分开~实现函数全部私有化

#include
using namespace std;
#define Link	0	//表示该节点有非空孩子节点
#define Thread	1	//表示该节点有后续节点（对于右子树来说）
#define MAXSIZE  100
 
template
struct BT_Thread_Node
{
	T Data;
	BT_Thread_Node* Left_Child;
	BT_Thread_Node* Right_Child;
	BT_Thread_Node* Parent;	       //指向该节点的父母节点
	int Ltag;
	int Rtag;
};
 
template
class Thread_Binary_tree
{
private:
	BT_Thread_Node* Tree;
	BT_Thread_Node* Pre_Node;
	BT_Thread_Node* BT_Node_Stack[MAXSIZE];
	int Top;
	int Create_Thread_BTree(BT_Thread_Node* &Tree,BT_Thread_Node* Parent);
	void PostOrder_Thread_Op(BT_Thread_Node* &Tree);
	void _PostOrder_Op(BT_Thread_Node* &Tree);
public:
	Thread_Binary_tree();
	~Thread_Binary_tree();
	void PostOrder_Thread();
	void _PostOrder();
};

（2）完整代码

#include
using namespace std;
#define Link	0	//表示该节点有非空孩子节点
#define Thread	1	//表示该节点有后续节点（对于右子树来说）
#define MAXSIZE  100
 
template
struct BT_Thread_Node
{
	T Data;
	BT_Thread_Node* Left_Child;
	BT_Thread_Node* Right_Child;
	BT_Thread_Node* Parent;	       //指向该节点的父母节点
	int Ltag;
	int Rtag;
};
 
template
class Thread_Binary_tree
{
private:
	BT_Thread_Node* Tree;
	BT_Thread_Node* Pre_Node;
	BT_Thread_Node* BT_Node_Stack[MAXSIZE];
	int Top;
	int Create_Thread_BTree(BT_Thread_Node* &Tree,BT_Thread_Node* Parent);
	void PostOrder_Thread_Op(BT_Thread_Node* &Tree);
	void _PostOrder_Op(BT_Thread_Node* &Tree);
public:
	Thread_Binary_tree();
	~Thread_Binary_tree();
	void PostOrder_Thread();
	void _PostOrder();
};
 
template
int Thread_Binary_tree::Create_Thread_BTree(BT_Thread_Node* &Tree,BT_Thread_Node* Parent_Node)
{
	int Data;
	cin >> Data;
	if (Data == -1)
		Tree = NULL;
	else
	{
		Tree = new BT_Thread_Node;
		Tree->Parent = Parent_Node;        //指向父母节点
		Tree->Data = Data;
		Tree->Ltag = Link;
		Tree->Rtag = Link;
		Create_Thread_BTree(Tree->Left_Child,Tree);  //Tree是孩子的父母节点
		Create_Thread_BTree(Tree->Right_Child,Tree);
	}
	return 1;
}
 
template
void Thread_Binary_tree::PostOrder_Thread_Op(BT_Thread_Node* &Tree)
{
	if (Tree == NULL)
		return;
	
	PostOrder_Thread_Op(Tree->Left_Child);		//左
	PostOrder_Thread_Op(Tree->Right_Child);		//右
 
	if (Tree->Left_Child == NULL)		//根
	{
		Tree->Left_Child = Pre_Node;
		Tree->Ltag = Thread;
	}
	if (Pre_Node != NULL && Pre_Node->Right_Child == NULL)
	{
		Pre_Node->Right_Child = Tree;
		Pre_Node->Rtag = Thread;
	}
 
	Pre_Node = Tree;
}
 
template
void Thread_Binary_tree::_PostOrder_Op(BT_Thread_Node* &Tree)
{
	if (Tree == NULL)
		return;
	
	BT_Thread_Node *Cur_Node = Tree;
	Pre_Node = NULL;
	while (Cur_Node != NULL)
	{
		//个人觉得，Cur_Node->Ltag == Link会影响找到最左节点，但就测试数据来看，两个都ok
		//while (Cur_Node->Left_Child != Pre_Node && Cur_Node->Ltag == Link)
		while (Cur_Node->Left_Child != Pre_Node)//change,找到起始节点（在左树的最左边）
		{
			Cur_Node = Cur_Node->Left_Child;
		}
 
		while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点
		{
			BT_Node_Stack[++Top] = Cur_Node;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新
			Cur_Node = Cur_Node->Right_Child;
		}
 
		if (Cur_Node == Tree)		//如果当前节点为根节点，说明遍历完成
		{
			BT_Node_Stack[++Top] = Cur_Node;
			cout << Cur_Node->Data << " ";
			return;
		}
 
		while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该袖珍树只差根就遍历完成
		{
			BT_Node_Stack[++Top] = Cur_Node;
			cout << Cur_Node->Data << " ";
			Pre_Node = Cur_Node;
			Cur_Node = Cur_Node->Parent;		//访问袖珍树后回到上一层
		}
 
		if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子
		{
			Cur_Node = Cur_Node->Right_Child;
		}
	}
}
 
template
Thread_Binary_tree::Thread_Binary_tree():
	Pre_Node(NULL)
	,Top(-1)
{
	Create_Thread_BTree(Tree, NULL);
}
 
template
Thread_Binary_tree::~Thread_Binary_tree()
{
	while (Top != -1)
	{
		delete BT_Node_Stack[Top];
		Top--;
	}
}
 
template
void Thread_Binary_tree::PostOrder_Thread()
{
	PostOrder_Thread_Op(Tree);
}
 
template
void Thread_Binary_tree::_PostOrder()
{
	_PostOrder_Op(Tree);
}
 
 
int main()
{
	Thread_Binary_tree MyTree;
	MyTree.PostOrder_Thread();
	MyTree._PostOrder();
	return 0;
}