【数据结构周周练】018 利用递归算法及中序遍历将二叉树线索化并遍历

Bertha 。 2021-06-11 15:13 490阅读 0赞

#  一、线索二叉树 #

从今天起，就给大家分享大家期待已久的线索二叉树的代码啦，首先给大家简单讲解一下线索二叉树的概念。

我们通过链式创建的有N个结点的二叉树会产生N + 1个空指针。怎么出现的这N + 1个空指针呢？

**重点1：为什么有N个结点的二叉树会产生N + 1个空指针？**

我们都知道，每个二叉树的结点都有两个指针，分别指向左孩子和右孩子。在结点初始化过程中设为空，这样就有2 × N个指针，从另一个角度看，除了根节点，每个结点都有唯一的双亲结点，即有N - 1个结点非空，所以剩下N + 1 个空结点。

我们希望能利用这N + 1个空结点，不让其白白浪费，所以通过建立前驱与后继，加快树的访问速度，从而引入线索二叉树。

**重点2：线索二叉树构造原则**

在二叉树线索化过程中，如果没有左子树，lChild 指向前驱结点，如果没有右子树，rChild 指向前驱结点。同时增加两个标志域表明当前所指对象是指左右子结点还是直接前驱与后继。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70][] 标志域含义

typedef struct ThreadNode {
    	int data;               //data field
    	struct ThreadNode *lChild, *rChild; // left child point and right child point
    	int ltag, rtag;         //tag of left thread and rignt thread
    }ThreadNode,*ThreadTree;

给大家举个例子，如下图，我们以中序为例，D结点左右子结点为空，所以左子结点指向其前驱，后子结点指向其后继。对于B（首结点），没有前驱，指向空；对于A，左右子结点都不为空，则指向左右子结点即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 1][] 二叉树线索化图例

# 二、示例 #

利用递归算法及中序遍历将下图的树线索化，先序遍历访问每个结点的编号，数据及所有的孩子结点，并用中序遍历线索化后的二叉树。其中圆角矩形内为结点数据，旁边数字为结点编号，箭头指向的结点为箭尾的孩子结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 2][] 森林转化为二叉树

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct ThreadNode {
    	int data;               //data field
    	int number;
    	struct ThreadNode *lChild, *rChild; // left child point and right child point
    	int ltag, rtag;         //tag of left thread and rignt thread
    }ThreadNode,*ThreadTree;
    
    int number = 0;
    int yon = 0;
    int yesOrNo[] = { 1,1,0,1,1,0,0,0,1,0,0,1,1,0,1,1,0,0,0,1,1,0,0,1,0,0 };
    int numData[] = { 1,2,4,5,6,3,7,8,9,10,11,12,13 };
    
    //Operation the node to creat the binary tree
    int OperationNode(ThreadTree &T) {
    	T = (ThreadTree)malloc(sizeof(ThreadNode));
    	if (!T)
    	{
    		cout << "空间分配失败(Allocate space failure.)" << endl;
    		exit(OVERFLOW);
    	}
    	//T->ltag = 0;
    	//T->rtag = 0;
    	T->data = numData[number];
    	T->number = number;
    	number++;
    	T->lChild = NULL;
    	T->rChild = NULL;
    	return 1;
    
    }
    
    //Eatablish the binary tree  
    void EstablishTree(ThreadTree &T) {
    	OperationNode(T);
    	if (yesOrNo[yon++])
    		EstablishTree(T->lChild);
    	if (yesOrNo[yon++])
    		EstablishTree(T->rChild);
    }
    
    void VisitBiTree(ThreadTree &T) {
    	cout << "【" << T->number + 1 << "】The number of present node is ：" << T->number << "; ";
    	cout << "\tdata is ：" << T->data << "; ";
    	if (T->lChild) {
    		T->ltag = 0;
    		cout << "\n\tlChild's number is :" << T->lChild->number << ",";
    	}
    	else
    		T->ltag = 1;
    
    	if (T->rChild) {
    		T->rtag = 0;
    		cout << "\n\trChild's number is :" << T->rChild->number << ";";
    	}
    	else
    		T->rtag = 1;
    
    	cout << endl;
    }
    
    void PreOrderVisitTree(ThreadTree T) {
    
    	VisitBiTree(T);
    	if (T->lChild)
    		PreOrderVisitTree(T->lChild);
    	if (T->rChild)
    		PreOrderVisitTree(T->rChild);
    }
    
    
    //Threaded binary tree by inorder traversal 
    void InThreadTree(ThreadTree &T, ThreadTree &pre) {
    	if (T)
    	{
    		InThreadTree(T->lChild, pre);
    		if (!T->lChild)
    			T->lChild = pre;
    
    		if (pre && !pre->rChild)
    			pre->rChild = T;
    
    		pre = T;
    		InThreadTree(T->rChild, pre);
    	}
    }
    
    //Creat the thread binary tree
    void CreatInThreadTree(ThreadTree &T) {
    	ThreadTree pre = NULL;
    	if (T)
    	{
    		InThreadTree(T, pre);
    		pre->rChild = NULL;
    	}
    }
    
    ThreadTree FirstNode(ThreadTree T) {
    	while (!T->ltag)
    		T = T->lChild;
    	return T;
    }
    
    ThreadTree NextNode(ThreadTree T) {
    	if (T->rtag == 0)
    		return FirstNode(T->rChild);
    	else
    		return T->rChild;
    }
    
    void VisitThreadTree(ThreadTree T) {
    	cout << "The number of present node is ：" << T->number << "; ";
    	cout << "\tdata is ：" << T->data << "; \n";
    }
    
    void InOrder(ThreadTree T) {
    	for (ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p))
    		VisitThreadTree(p);
    }
    
    void main() {
    	ThreadTree T;
    	EstablishTree(T);
    
    	cout << "\n********【线索化之前遍历二叉树。Traverse binary tree before thread】********" << endl;
    	PreOrderVisitTree(T);
    
    
    	cout << "\n********【线索化之后遍历二叉树。Traverse binary tree after thread】********" << endl;
    	CreatInThreadTree(T);
    	InOrder(T);
    }

# 四、实现效果 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70]: /images/20210516/caa622770aaf4d608969c1354d9e0462.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 1]: /images/20210516/f00b6df1f8de417e89a465f034fdc38d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 2]: /images/20210516/89e2c64577694a81a8aa5291c771789f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_27_color_FFFFFF_t_70 3]: /images/20210516/e9d2a230a43c4ab99867370ef0aea925.png