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

不念不忘少年蓝@ 2022-05-20 07:44 269阅读 0赞

## 1.二叉树线索化 ##

二叉树的遍历是按照一定的规则把二叉树中的节点**按照一定的次序排列成线性序列**进行访问的，实质上就是**对一个非线性结构进行线索化操作**，使得每个节点（除第一个和最后一个外）都有前驱和后继节点，有时为了运算方便需要记录这些前驱和后继节点，称为二叉树线索化，而对于不同的遍历规则，又分为**先序线索二叉树**，**中序线索二叉树**，**后序线索二叉树**。

## 2.线索二叉树的定义 ##

### （1）思路： ###

一颗具有**n**个节点的二叉树，有n-1条指向左孩子或右孩子的分支，对于二叉链表来说，2n个指针只用了n-1个，所以可以利用另外n+1个指针作为指向前驱节点和后继节点的指针。

### （2）前驱节点和后继节点 ###

有些书籍对这两个概念并没有简单明了的解释~，其实就是对于特定遍历方式来说，一个节点的前后节点

#### ①前驱节点： ####

指定遍历方式得出的节点访问顺序中，某一节点的**前一个**节点。

#### ②后继节点 ####

指定遍历方式得出的节点访问顺序中，某一节点的**后一个**节点。

### （3）线索二叉树的节点表示（结构体）-线索链表（Thread Linked List） ###

#define Link	0	//表示该节点有非空孩子节点
    #define Thread	1	//表示该节点有后续节点（对于右子树来说）
    
    template<class T>
    struct BT_Thread_Node
    {
    	T Data;
    	BT_Thread_Node* Left_Child;
    	BT_Thread_Node* Right_Child;
    	int Ltag;
    	int Rtag;
    };

**Ltag=0（Link）-表示Left\_Child的指针指向左孩子节点；Ltag=1（Thread）-表示Left\_Child的指针指向前驱节点**

**Rtag=0（Link）-表示Right\_Child的指针指向右孩子节点；Rtag=1（Thread）-表示Right\_Child的指针指向后继节点**

### （4)线索化规则（重点） ###

书上也是奇奇怪怪的，其实很简单，就按照某一遍历规则，记录当前节点（Cur)，上一次访问的节点（Pre）

①如果当前节点Cur->Left\_Child=NULL（左孩子节点空），则**Cur->Left\_Child=Pre；Cur->Ltag=1（**左指针域指向前驱节点（前一个节点Pre），修改Ltag为线索模式）

②如果前一节点Pre->Right\_Child=NULL（前节点的右孩子节点空），则**Pre->Right\_Child=Cur;Pre->Rtag=1**（前节点的右指针域指向后继节点（也就是当前节点），修改Rtag为线索模式）

## 3.中序线索二叉树 ##

### （1）线索化中序二叉树 ###

![70][]

### （2）中序线索化实现 ###

template<class T>
    void Thread_Binary_tree<T>::InOrder_Thread_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)		//空返回上一节点
    		return;
    	
    	InOrder_Thread_Op(Tree->Left_Child);		//左
    
    	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;
    	InOrder_Thread_Op(Tree->Right_Child);		//右
    }

注：Pre\_Node是类内数据成员，初始化为NULL

### （3）线索化遍历 ###

#### ①思路： ####

对于中序遍历来说，先查找线索链表的第一个节点，也就是最左方向上的最后一个节点，然后如果有右线索先寻找后继节点，查找到断线索（有右节点啦）就往下找一个右节点，继续这样摸下去，其实说到底就是有线索先按线索找（注意线索上的节点是需要访问的），等到线索断了就往下找右孩子节点。

#### ②实现代码 ####

template<class T>
    void Thread_Binary_tree<T>::_InOrder_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)
    		return;
    	
    	BT_Thread_Node<T>* Cur_Node = Tree;
    
    	while (Cur_Node)			//当前节点不能为空
    	{
    		while (Cur_Node->Ltag == Link)		//节点有左树时，寻找最左端的树
    		{
    			Cur_Node = Cur_Node->Left_Child;
    		}
    		cout << Cur_Node->Data << " ";
    
    		while (Cur_Node&&Cur_Node->Rtag == Thread)	//节点非空并且右树是线索树时查找最前的一个线索树节点
    		{
    			Cur_Node = Cur_Node->Right_Child;
    			cout << Cur_Node->Data << " ";
    		}
    
    
    		Cur_Node = Cur_Node->Right_Child;		//右树不是线索树，查找该节点的右孩子节点
    	}
    	cout << endl;
    }

### （4）二叉树的析构（利用线索） ###

#### ①思路： ####

当把树线索化了，其实就是链表，而删除呢，我觉得按链表删就ok，但是后来发现脑子不好用，就想着按遍历的顺序，栈存节点，然后把栈清了就ok，所以再写了一个程序，写了才发现其实！可以直接在遍历的时候顺便入栈了节点，好吧这次先这样，等后面出先序和后序我再改吧~

#### ②代码 ####

BT_Thread_Node<T>* BT_Node_Stack[MAXSIZE];//类私有，MAXISIZE=100

template<class T>
    int Thread_Binary_tree<T>::Distory_Thread_BTree(BT_Thread_Node<T>* &Tree)
    {
    	if(Tree==NULL)
    		return 0;
    
    	int Top = -1;
    	BT_Thread_Node<T>* Cur_Node = Tree;
    	while (Cur_Node)
    	{
    		while (Cur_Node->Ltag == Link)
    		{
    			Cur_Node = Cur_Node->Left_Child;
    		}
    		
    		BT_Node_Stack[++Top] = Cur_Node;
    		
    		while (Cur_Node&&Cur_Node->Rtag == Thread)
    		{
    			Cur_Node = Cur_Node->Right_Child;
    			BT_Node_Stack[++Top] = Cur_Node;
    		}
    
    		Cur_Node = Cur_Node->Right_Child;
    	}
    
    	for (Top; Top != -1; Top--)
    	{
    		cout << BT_Node_Stack[Top]->Data;
    		delete BT_Node_Stack[Top];
    	}
    
    	return 1;
    }

### （5）中序线索树类实现 ###

#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 Create_Thread_BTree(BT_Thread_Node<T>* &Tree);
    	int Distory_Thread_BTree(BT_Thread_Node<T>* &Tree);
    	void InOrder_Thread_Op(BT_Thread_Node<T>* &Tree);
    	void _InOrder_Op(BT_Thread_Node<T>* &Tree);
    public:
    	Thread_Binary_tree();
    	~Thread_Binary_tree();
    	void InOrder_Thread();
    	void _InOrder();
    };
    
    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;
    		Tree->Ltag = Link;
    		Tree->Rtag = Link;
    		Create_Thread_BTree(Tree->Left_Child);
    		Create_Thread_BTree(Tree->Right_Child);
    	}
    	return 1;
    }
    
    template<class T>
    int Thread_Binary_tree<T>::Distory_Thread_BTree(BT_Thread_Node<T>* &Tree)
    {
    	if(Tree==NULL)
    		return 0;
    
    	int Top = -1;
    	BT_Thread_Node<T>* Cur_Node = Tree;
    	while (Cur_Node)
    	{
    		while (Cur_Node->Ltag == Link)
    		{
    			Cur_Node = Cur_Node->Left_Child;
    		}
    		
    		BT_Node_Stack[++Top] = Cur_Node;
    		
    		while (Cur_Node&&Cur_Node->Rtag == Thread)
    		{
    			Cur_Node = Cur_Node->Right_Child;
    			BT_Node_Stack[++Top] = Cur_Node;
    		}
    
    		Cur_Node = Cur_Node->Right_Child;
    	}
    
    	for (Top; Top != -1; Top--)
    	{
    		cout << BT_Node_Stack[Top]->Data;
    		delete BT_Node_Stack[Top];
    	}
    
    	return 1;
    }
    
    template<class T>
    void Thread_Binary_tree<T>::InOrder_Thread_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)		//空返回上一节点
    		return;
    	
    	InOrder_Thread_Op(Tree->Left_Child);		//左
    
    	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;
    	InOrder_Thread_Op(Tree->Right_Child);		//右
    }
    
    template<class T>
    void Thread_Binary_tree<T>::_InOrder_Op(BT_Thread_Node<T>* &Tree)
    {
    	if (Tree == NULL)
    		return;
    	
    	BT_Thread_Node<T>* Cur_Node = Tree;
    
    	while (Cur_Node)			//当前节点不能为空
    	{
    		while (Cur_Node->Ltag == Link)		//节点有左树时，寻找最左端的树
    		{
    			Cur_Node = Cur_Node->Left_Child;
    		}
    		cout << Cur_Node->Data << " ";
    
    		while (Cur_Node&&Cur_Node->Rtag == Thread)	//节点非空并且右树是线索树时查找最前的一个线索树节点
    		{
    			Cur_Node = Cur_Node->Right_Child;
    			cout << Cur_Node->Data << " ";
    		}
    
    
    		Cur_Node = Cur_Node->Right_Child;		//右树不是线索树，查找该节点的右孩子节点
    	}
    	cout << endl;
    }
    
    template<class T>
    Thread_Binary_tree<T>::Thread_Binary_tree():Pre_Node(NULL)
    {
    	Create_Thread_BTree(Tree);
    }
    
    template<class T>
    Thread_Binary_tree<T>::~Thread_Binary_tree()
    {
    	Distory_Thread_BTree(Tree);
    }
    
    template<class T>
    void Thread_Binary_tree<T>::InOrder_Thread()
    {
    	InOrder_Thread_Op(Tree);
    	Pre_Node = NULL;		//恢复值为空，便于下次线索化
    }
    
    template<class T>
    void Thread_Binary_tree<T>::_InOrder()
    {
    	_InOrder_Op(Tree);
    }

[70]: /images/20220520/361bfc59b8fb48f3a46152b5c7d48ed2.png