数据结构-线索二叉树（先序线索二叉树及遍历）

- 日理万妓 2022-05-19 03:48 191阅读 0赞

*  # 先序线索二叉树 #

--------------------

*  ## 线索化的概念及相关图解 ##

在上一篇中详细介绍了中序线索二叉树，**线索化图解**及**相关概念**都放在那篇博客啦，放个传送门

**线索二叉树详细解析（含图解）：[传送门][Link 1]**

*  ## **先序线索二叉树** ##

### **（1）先序线索化** ###

**①思路：**

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

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

**b.保存当前节点，作为下一次的Pre\_Node (记录历史的意思）**

**c.先线索化左孩子节点，再而是右孩子节点，前提是该孩子是链模式（Link）**

**②实现代码：**

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

template<class T>
    void Thread_Binary_tree<T>::PreOrder_Thread_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)
    		return;
    
    	if (Tree->Left_Child == NULL)		//根
    	{
    		Tree->Ltag = Thread;
    		Tree->Left_Child = Pre_Node;
    	}
    
    	if (Pre_Node != NULL && Pre_Node->Right_Child == NULL)
    	{
    		Pre_Node->Rtag = Thread;
    		Pre_Node->Right_Child = Tree;
    	}
    
    	Pre_Node = Tree;
    	if (Tree->Ltag == Link)
    		PreOrder_Thread_Op(Tree->Left_Child);		//左孩子节点
    	if (Tree->Rtag == Link)
    		PreOrder_Thread_Op(Tree->Right_Child);		//右孩子节点
    
    }

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

### （2）中序线索遍历 ###

**①思路：**

**a.靠左（每次都指向左孩子节点）访问：直到该节点的下一左孩子节点是指向它的前驱节点（不为Link模 式了），这个节点也是要访问的。**

**b.找后继节点：若该节点的右孩子指向的是后继节点，则进入该右孩子节点（暂不访问）**

**c.靠右访问：前提是该节点没有处在链（Link）模式的左孩子，有的话进入新一轮的遍历。**

**②实现代码：**

template<class T>
    void Thread_Binary_tree<T>::_PreOrder_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)
    		return;
    	BT_Thread_Node<T>* Cur_Node = Tree;
    	while (Cur_Node != NULL)		//遍历完的标志是节点为空
    	{
    		while (Cur_Node->Left_Child != NULL && Cur_Node->Ltag == Link)		//该节点存在左孩子节点
    		{
    			BT_Node_Stack[++Top] = Cur_Node;		//入栈是为了便于二叉树的析构
    			cout << Cur_Node->Data << " ";
    			Cur_Node = Cur_Node->Left_Child;
    		}
    		BT_Node_Stack[++Top] = Cur_Node;		//该节点的左孩子节点为NULL
    		cout << Cur_Node->Data << " ";
    		
    		if (Cur_Node->Ltag == Thread)		//遇到线索，看右节点
    		{
    			Cur_Node = Cur_Node->Right_Child;
    		}
    
    		while (Cur_Node != NULL)		//右
    		{
    			if (Cur_Node->Left_Child != NULL && Cur_Node->Ltag == Link)//有左孩子节点，直接跳出循环
    				break;
    
    			BT_Node_Stack[++Top] = Cur_Node;		//访问并入栈该节点
    			cout << Cur_Node->Data << " ";
    			Cur_Node = Cur_Node->Right_Child;		//指向右孩子节点
    		}
    	}
    	cout << endl;
    }

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

### （3）析构线索树 ###

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

**①实现代码：**

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

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

*  ## 先序线索二叉树类实现 ##

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

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

### （2）完整代码 ###

#include<iostream>
    using namespace std;
    #define Link	0	//表示该节点有非空孩子节点
    #define Thread	1	//表示该节点有后续节点（对于右子树来说）
    #define MAXSIZE  100
    
    template<class T>
    struct BT_Thread_Node
    {
    	T Data;
    	BT_Thread_Node* Left_Child;
    	BT_Thread_Node* Right_Child;
    	int Ltag;
    	int Rtag;
    };
    
    template<class T>
    class Thread_Binary_tree
    {
    private:
    	BT_Thread_Node<T>* Tree;
    	BT_Thread_Node<T>* Pre_Node;
    	BT_Thread_Node<T>* BT_Node_Stack[MAXSIZE];
    	int Top;
    	int Create_Thread_BTree(BT_Thread_Node<T>* &Tree);
    	void PreOrder_Thread_Op(BT_Thread_Node<T>* &Tree);
    	void _PreOrder_Op(BT_Thread_Node<T>* &Tree);
    public:
    	Thread_Binary_tree();
    	~Thread_Binary_tree();
    	void PreOrder_Thread();
    	void _PreOrder();
    };
    
    template<class T>
    int Thread_Binary_tree<T>::Create_Thread_BTree(BT_Thread_Node<T>* &Tree)
    {
    	int Data;
    	cin >> Data;
    	if (Data == -1)
    		Tree = NULL;
    	else
    	{
    		Tree = new BT_Thread_Node<T>;
    		Tree->Data = Data;
    
    		//节点都要初始化为链状态Link
    		Tree->Ltag = Link;
    		Tree->Rtag = Link;
    		Create_Thread_BTree(Tree->Left_Child);
    		Create_Thread_BTree(Tree->Right_Child);
    	}
    	return 1;
    }
    
    template<class T>
    void Thread_Binary_tree<T>::PreOrder_Thread_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)
    		return;
    
    	if (Tree->Left_Child == NULL)		//根
    	{
    		Tree->Ltag = Thread;
    		Tree->Left_Child = Pre_Node;
    	}
    
    	if (Pre_Node != NULL && Pre_Node->Right_Child == NULL)
    	{
    		Pre_Node->Rtag = Thread;
    		Pre_Node->Right_Child = Tree;
    	}
    
    	Pre_Node = Tree;
    	if (Tree->Ltag == Link)
    		PreOrder_Thread_Op(Tree->Left_Child);		//左孩子节点
    	if (Tree->Rtag == Link)
    		PreOrder_Thread_Op(Tree->Right_Child);		//右孩子节点
    
    }
    
    template<class T>
    void Thread_Binary_tree<T>::_PreOrder_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)
    		return;
    	BT_Thread_Node<T>* Cur_Node = Tree;
    	while (Cur_Node != NULL)		//遍历完的标志是节点为空
    	{
    		while (Cur_Node->Left_Child != NULL && Cur_Node->Ltag == Link)		//该节点存在左孩子节点
    		{
    			BT_Node_Stack[++Top] = Cur_Node;		//入栈是为了便于二叉树的析构
    			cout << Cur_Node->Data << " ";
    			Cur_Node = Cur_Node->Left_Child;
    		}
    		BT_Node_Stack[++Top] = Cur_Node;		//该节点的左孩子节点为NULL
    		cout << Cur_Node->Data << " ";
    		
    		if (Cur_Node->Ltag == Thread)		//遇到线索，看右节点
    		{
    			Cur_Node = Cur_Node->Right_Child;
    		}
    
    		while (Cur_Node != NULL)		//右
    		{
    			if (Cur_Node->Left_Child != NULL && Cur_Node->Ltag == Link)//有左孩子节点，直接跳出循环
    				break;
    
    			BT_Node_Stack[++Top] = Cur_Node;		//访问并入栈该节点
    			cout << Cur_Node->Data << " ";
    			Cur_Node = Cur_Node->Right_Child;		//指向右孩子节点
    		}
    	}
    	cout << endl;
    }
    
    
    template<class T>
    Thread_Binary_tree<T>::Thread_Binary_tree()
    {
    	Create_Thread_BTree(Tree);
    }
    
    template<class T>
    Thread_Binary_tree<T>::~Thread_Binary_tree()
    {
    	while (Top != -1)
    	{
    		delete BT_Node_Stack[Top];
    		Top--;
    	}
    }
    
    template<class T>
    void Thread_Binary_tree<T>::PreOrder_Thread()
    {
    	PreOrder_Thread_Op(Tree);
    }
    
    template<class T>
    void Thread_Binary_tree<T>::_PreOrder()
    {
    	_PreOrder_Op(Tree);
    }
    
    //测试
    int main()
    {
    	Thread_Binary_tree<int> MyTree;
    	MyTree.PreOrder_Thread();
    	MyTree._PreOrder();
    	return 0;
    }

[Link 1]: https://blog.csdn.net/szu_crayon/article/details/81050911