1. 首页
  2. 文章资讯

【高阶数据结构】线索二叉树的实现和一系列相关操作（精美图解+完整代码）

36 阅读 0 评论

博客主页：醉竺

本文专栏：《高阶数据结构》

欢迎关注：感谢大家的点赞评论+关注，祝您学有所成！

想要学习更多《高阶数据结构》点击专栏链接查看 

目录

1.为什么要构建线索二叉树

2.什么是线索二叉树 

3.如何对二叉树进行线索化

4.线索化二叉树 

4.1用中序遍历序列线索化二叉树

4.2用前序遍历序列线索化二叉树

5.在线索二叉树上进行的操作

操作1：找线索二叉树的第一个和最后一个节点

操作2：找线索二叉树中某个节点的前趋和后继节点

操作3：对线索二叉树进行遍历

操作4：对线索二叉树的节点进行查找

小结

归纳思考

本篇文章主题是“线索二叉树”。

和传统二叉树相比，线索二叉树可以进一步提高访问二叉树节点的速度，从而提高访问二叉树的效率，当然，“线索”这个概念的引入也意味着要对原来的二叉树实现代码做出相应的修改。如果小伙伴对二叉树还不是很了解的话，记得要学习以下几篇文章~

《树与二叉树的概念、性质及详细证明》icon-default.png?t=O83Ahttps://blog.csdn.net/weixin_43382136/article/details/136593735

《二叉树的深度优先遍历和广度优先遍历（超多配图！）》icon-default.png?t=O83Ahttps://blog.csdn.net/weixin_43382136/article/details/136658468

那么，什么是线索？要怎么把传统二叉树转变为线索二叉树？带着这些问题，我们先从线索二叉树的概念开始说起，进而探讨如何对二叉树进行线索化，以及在线索二叉树上的操作问题。

1.为什么要构建线索二叉树

我们先来看一个简单的二叉树链式存储。  

在图 1 所示二叉树的链式存储中，每个二叉树节点（BinaryTreeNode）都包含两个指针域，分别是左子节点指针（leftChild）和右子节点指针（rightChild）。但一个二叉树中往往某些节点并没有左孩子或者右孩子，尤其是叶子节点，根本就不存在左孩子和右孩子。

这张图里一共有8个节点，除了根节点外， 都会有一根来自其他节点的指针指向该节点自身。仔细数下来，对于8个节点的2叉树，虽然一共有16个指针域，但实际使用了的只有7个。

总结：二叉树采用二叉链表存储时，每个节点有两个指针域。如果二叉链表有n个节点，则一共有2n个指针域，而只有n-1个是实指针，其余n+1个都是空指针。

为什么呢？

因为二叉树有n-1个分支，每个分支对应一个实指针，如下图所示。从下向上看，每一个节点对应一个分支，只有树根没有对应分支，所以 分支数 等于 总节点数 减 1，分支数(实指针) = n - 1 , 总的指针数减去实指针数，即为空指针数，即 2n - (n - 1) = n + 1。

这n+1个指针域就这样白白浪费了。所以，为了物尽其用，我们可以用这n+1个指针域记录一些有用的信息。

2.什么是线索二叉树 

那要记录什么，又要怎么记录呢？

图 2 所示的这棵二叉树中序遍历（前序、后序遍历也同样道理）的顺序为 DGBHEACF。

在这个序列中 " DGBHEACF "，除 D 和 F 节点外，其他节点都有且只有一个直接前趋和一个直接后继。比如 B 的前趋是 G，B 的后继是 H，而 D 节点没有前趋，F 节点没有后继。

问题来了，在存储起一棵二叉树后，我们可以 通过节点E的左孩子指针迅速找到节点H，但并没有办法通过节点E迅速找到其在中序遍历序列中的后继节点A。

也就是说，只能通过节点的左右孩子指针找到该节点的左右孩子，但没有办法直接得到某个节点在某个遍历序列中的前趋或者后继节点，这种前趋或者后继节点的信息只能在遍历的过程中 动态得到。

不过，既然节点E没有右孩子，那么节点E的右孩子指针可以用来记录后继节点A，也就是指向A。这样就可以通过节点E迅速找到节点A了。

举个例子。在图 3 中：

  • G 节点的左右子节点指针都没有被使用，因此可以用左节点指针指向 G 节点在中序遍历序列中的前趋节点 D，右节点指针指向 G 节点在中序遍历中的后继节点 B。

  • D 节点的左子节点指针没有被使用，因此可以用于指向 D 节点在中序遍历序列中的前趋节点，但因为在中序遍历序列中 D 没有前趋节点，因此该指针只能指向 nullptr。

  • H 节点的左节点指针指向前趋节点 B，右节点指针指向后继节点 E。

  • E 节点的右指针指向后继节点 A。

  • F 节点的左节点指针指向前趋节点 C，右节点指针指向后继节点，但因为 F 节点没有后继节点，所以该指针只能指向 nullptr。

  • C 节点的左节点指针指向前趋节点 A。

总结一下，这些 指向前趋节点和后继节点的指针就叫做线索。由节点的左孩子指针充当指向前趋节点的线索，由节点的右孩子指针充当指向后继节点的线索。

我们把加上了线索的二叉树称为 线索二叉树。对二叉树进行某种序列的遍历使其成为一棵线索二叉树的过程称为二叉树的 线索化。线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

线索二叉树对于节点的插入、删除、查找前趋后继等都会变得更加方便， 解决了存储空间的浪费问题，也解决了前趋和后继节点的记录问题 ， 这就是建立这些线索的意义。

当然，线索二叉树也分为 前序、中序、后序 线索二叉树，而且，因为二叉树还可以层序遍历，因此也存在层序线索二叉树。话说回来，前序线索二叉树是以前序遍历序列为依据对二叉树进行线索化，而中序、后序线索二叉树当然是分别以中序、后序遍历序列为依据对二叉树进行线索化。

3.如何对二叉树进行线索化

要编写线索二叉树的实现代码，得先看一看线索二叉树中每个节点的结构是什么样的。我们先回顾一下以往二叉树链式存储时树中的每个节点的定义。

//树中每个节点的定义
template <typename T> //T 代表数据元素的类型
struct BinaryTreeNode
{
    T               data;        //数据域，存放数据元素
    BinaryTreeNode* lchild,   //左子节点指针
        * rchild;  //右子节点指针
};

而在线索二叉树中，左子节点指针和右子节点指针指向的可能是前趋和后继节点，也有可能是左孩子和右孩子，那么到底指向什么呢？

如果节点有左孩子，则 lchild 指向左孩子，否则 lchild 指向其前驱；如果节点有右孩子，则 rchild 指向右孩子，否则 rchild 指向其后继。

思考：那么怎么区分到底存储的是左孩子和右孩子，还是前驱和后继信息呢？

引入标志域 

为了避免混淆，这就需要为 BinaryTreeNode 结构增加两个标志变量 ltag 和 rtag，用于标记指针保存的是左、右子节点还是前趋、后继节点。节点的结构体如下图所示。

下面是修改后的 BinaryTreeNode 结构代码。

//树中每个节点的定义
template <typename T> //T 代表数据元素的类型
struct BinaryTreeNode
{
	T               data;        //数据域，存放数据元素
	BinaryTreeNode* lchild,   //左子节点指针
		* rchild;  //右子节点指针
	int8_t        ltag,       //左标志 = 0 表示 lchild 指向的是左子节点，=1 表示 lchild 指向的是前趋节点（线索）
		rtag;      //右标志 = 0 表示 rchild 指向的是右子节点，=1 表示 rchild 指向的是后继节点（线索）
};

我们通常将二叉树存储结构称为 二叉链表，而在这里，把这种修改后的、适用于线索二叉树的存储结构称为 线索链表。想一想，对于图 3 所示的线索二叉树对应的链式存储方式结构示意图应该怎么画呢？  

结果如图 4 所示：

图中，0表示指向的是左/右子节点，1表示指向的是前趋/后继节点。

二叉树的线索化过程针对的是二叉树节点的空指针，也就是我们之前说过的“n+1”个没有左孩子或者右孩子的指针。

换句话说，在线索化一棵二叉树的过程中，我们并没有把所有节点的前趋和后继节点都记录下来，只是利用了 n+1 个空指针域进行前趋和后继节点的记录。

那么，对于没有记录其前趋和后继的节点，就要通过一些其他方法寻找其前趋和后继了。

4.线索化二叉树 

线索化的实质是利用二叉链表中的空指针记录节点的前驱或后继线索。而每种遍历顺序不同，节点的前驱和后继也不同，因此二叉树线索化必须指明是什么遍历顺序的线索化。线索二叉树分为前序线索二叉树、中序线索二叉树和后序线索二叉树。 

4.1用中序遍历序列线索化二叉树

我们先耐下心来理解一下线索二叉树的定义和实现代码。  

//线索二叉树的定义
template <typename T>
class ThreadBinaryTree
{
public:
	ThreadBinaryTree();  //构造函数
	~ThreadBinaryTree(); //析构函数
public:
	//利用扩展二叉树的前序遍历序列来创建一棵二叉树
	void CreateBTreeAccordPT(char* pstr);
private:
	//利用扩展二叉树的前序遍历序列创建二叉树的递归函数
	void CreateBTreeAccordPTRecu(BinaryTreeNode<T>*& tnode, char*& pstr);//参数为引用类型，确保递归调用中对参数的改变会影响到调用者
public:
	//在二叉树中根据中序遍历序列创建线索
	void CreateThreadInBTreeAccordIO();
private:
	void CreateThreadInBTreeAccordIO(BinaryTreeNode<T>*& tnode, BinaryTreeNode<T>*& pre);//参数为引用类型
private:
	void ReleaseNode(BinaryTreeNode<T>* pnode);
private:
	BinaryTreeNode<T>* root; //树根指针
};

//构造函数
template<class T>
ThreadBinaryTree<T>::ThreadBinaryTree()
{
	root = nullptr;
}

//析构函数
template<class T>
ThreadBinaryTree<T>::~ThreadBinaryTree()
{
	ReleaseNode(root);
};

//释放二叉树节点
template<class T>
void ThreadBinaryTree<T>::ReleaseNode(BinaryTreeNode<T>* pnode)
{
	if (pnode != nullptr)
	{
		if (pnode->ltag == 0)
			ReleaseNode(pnode->lchild); //只有真的需要delete的节点，才会递归调用ReleaseNode
		if (pnode->rtag == 0)
			ReleaseNode(pnode->rchild); //只有真的需要delete的节点，才会递归调用ReleaseNode
	}
	delete pnode;
}

//利用扩展二叉树的前序遍历序列来创建一棵二叉树
template<class T>
void ThreadBinaryTree<T>::CreateBTreeAccordPT(char* pstr)
{
	CreateBTreeAccordPTRecu(root, pstr);
}

//利用扩展二叉树的前序遍历序列创建二叉树的递归函数
template<class T>
void ThreadBinaryTree<T>::CreateBTreeAccordPTRecu(BinaryTreeNode<T>*& tnode, char*& pstr)
{
	if (*pstr == '#')
	{
		tnode = nullptr;
	}
	else
	{
		tnode = new BinaryTreeNode<T>; //创建根节点
		tnode->ltag = tnode->rtag = 0; //标志先给0
		tnode->data = *pstr;
		CreateBTreeAccordPTRecu(tnode->lchild, ++pstr); //创建左子树
		CreateBTreeAccordPTRecu(tnode->rchild, ++pstr);//创建右子树
	}
}

//在二叉树中根据中序遍历序列创建线索
template<class T>
void ThreadBinaryTree<T>::CreateThreadInBTreeAccordIO()
{
	BinaryTreeNode<T>* pre = nullptr;  //记录当前所指向的节点的前趋节点（刚开始的节点没有前趋，所以设置为nullptr）

	CreateThreadInBTreeAccordIO(root, pre);

	//注意处理最后一个节点的右孩子，因为这个右孩子还没处理
	pre->rchild = nullptr; //这里之所以直接给nullptr，是因为中序遍历访问顺序是左根右，所以最后一个节点不可能有右孩子，否则最后一个访问的节点就会是他的右孩子。其实就算不执行这句，pre->rchild也已经是等于nullptr的了。
	pre->rtag = 1; //线索化
}

template<class T>
void ThreadBinaryTree<T>::CreateThreadInBTreeAccordIO(BinaryTreeNode<T>*& tnode, BinaryTreeNode<T>*& pre)
{
	if (tnode == nullptr)
		return;

	//中序遍历序列（左根右），递归顺序非常类似于中序遍历
	CreateThreadInBTreeAccordIO(tnode->lchild, pre);

	if (tnode->lchild == nullptr) //找空闲的指针域进行线索化
	{
		tnode->ltag = 1; //线索
		tnode->lchild = pre;  //如果lchild ==nullptr，说明该节点没有前趋节点
	}

	//这个前趋节点的后继节点肯定是当前这个节点tnode
	if (pre != nullptr && pre->rchild == nullptr)
	{
		pre->rtag = 1; //线索
		pre->rchild = tnode;
	}
	pre = tnode; //前趋节点指针指向当前节点

	CreateThreadInBTreeAccordIO(tnode->rchild, pre);
}

依据这些代码，我们就可以创建线索二叉树了。创建线索二叉树可以分成两个步骤。  

  1. 用任何方法创建二叉树。这里将采用前面使用过的利用扩展二叉树的前序遍历序列创建图 3 所示的二叉树。

  1. 将该二叉树按照中序（也可以是前序、后序）遍历序列 创建线索，这会用到 CreateThreadInBTreeAccordIO 成员函数。

在 main 主函数，加入下面的代码来创建并按中序遍历线索化一棵二叉树。  

ThreadBinaryTree<int> mythreadtree;
mythreadtree.CreateBTreeAccordPT((char*)"ABD#G##EH###C#F##");  //利用扩展二叉树的前序遍历序列创建二叉树
//对二叉树进行线索化(根据中序遍历序列创建线索)
mythreadtree.CreateThreadInBTreeAccordIO();

从上面的代码不难看到，根据中序遍历序列线索化二叉树的过程其实与中序遍历的过程非常类似，只不过是在遍历的过程中进行线索化而已。  

4.2用前序遍历序列线索化二叉树

前面的代码演示了在二叉树中根据中序遍历序列线索化二叉树。那么如果根据前序遍历序列线索化二叉树代码应该是什么样的呢？

可以参照上述的 CreateThreadInBTreeAccordIO 成员函数来书写名字叫做 CreateThreadInBTreeAccordPO 的新成员函数来实现，参考下面的代码。

//在二叉树中根据前序遍历序列创建线索
template<class T>
void ThreadBinaryTree<T>::CreateThreadInBTreeAccordPO()
{
	BinaryTreeNode<T>* pre = nullptr;
	CreateThreadInBTreeAccordPO(root, pre);
	pre->rchild = nullptr;
	pre->rtag = 1;
}
template<class T>
void ThreadBinaryTree<T>::CreateThreadInBTreeAccordPO(BinaryTreeNode<T>*& tnode, BinaryTreeNode<T>*& pre)
{
	if (tnode == nullptr)
		return;

	//前遍历序列（根左右），递归顺序非常类似于前序遍历
	if (tnode->lchild == nullptr) //找空闲的指针域进行线索化
	{
		tnode->ltag = 1; //线索
		tnode->lchild = pre;  //如果lchild ==nullptr，说明该节点没有前趋节点
	}

	//这个前趋节点的后继节点肯定是当前这个节点tnode 
	if (pre != nullptr && pre->rchild == nullptr)
	{
		pre->rtag = 1; //线索
		pre->rchild = tnode;
	}
	pre = tnode; //前趋节点指针指向当前节点

	if (tnode->ltag == 0) //当lchild是真正的子节点而不是线索化后的前趋节点时
		CreateThreadInBTreeAccordPO(tnode->lchild, pre);

	if (tnode->rtag == 0) //当rchild是真正的子节点而不是线索化后的后继趋节点时
		CreateThreadInBTreeAccordPO(tnode->rchild, pre);
}

前序遍历序列化线索二叉树代码与中序遍历序列线索化二叉树的代码有一些非常不同的地方。

因为前序遍历访问节点的顺序是“根、左、右”，所以在处理根的时候，很可能已经线索化了根节点的 leftChild 和 rightChild 指针。

那么我们在对左右子节点进行递归调用CreateThreadInBTreeAccordPO 时，就一定要判断这些子节点指针指向的是否为真正的子节点，而不是线索化后的前趋或者后继节点。否则就可能写出错误的实现代码导致程序执行产生异常。

main 主函数中，可以把下面的代码行：

mythreadtree.CreateThreadInBTreeAccordIO();

修改为：  

mythreadtree.CreateThreadInBTreeAccordPO();

以根据前序遍历序列线索化二叉树，测试完成后记得修改回如下代码行以免对后序测试产生影响。

mythreadtree.CreateThreadInBTreeAccordIO();

5.在线索二叉树上进行的操作

二叉树线索化之后，因为左右子节点指针保存的数据发生了改变，所以，许多针对原有二叉树进行操作的代码也必须做出相应的改变。

我们将通常会进行的操作分为4类：找第一个和最后一个节点，找某个节点的前趋和后继节点，对线索二叉树进行遍历，以及查找线索二叉树的节点。

操作1：找线索二叉树的第一个和最后一个节点

由于线索二叉树也分前序、中序和后序，因此找的第一个和最后一个节点肯定指的是相应顺序的节点。比如，如果线索二叉树是用中序遍历序列来线索化的，那么找的第一个和最后一个节点肯定指的是该二叉树进行中序遍历时的第一个和最后一个节点。

以中序遍历序列线索化的二叉树为例看看代码的书写，在 ThreadBinaryTree 类模板的定义中，增加GetFirst_IO()和GetLast_IO()成员函数即可。

  • 找线索二叉树（中序线索化）的第一个节点 
//找线索二叉树（中序线索化）的第一个节点
BinaryTreeNode<T>* GetFirst_IO()
{
	return GetFirst_IO(root);
}
BinaryTreeNode<T>* GetFirst_IO(BinaryTreeNode<T>* root)
{
	//中序遍历是“左根右顺序”
	//一直找真正的左孩子即可。
	if (root == nullptr)
		return nullptr;
	BinaryTreeNode<T>* tmpnode = root;
	while (tmpnode->ltag == 0) //指向的是真正的左子节点
	{
		tmpnode = tmpnode->lchild;
	}
	return tmpnode;
}
  • 找线索二叉树（中序线索化）的最后一个节点 
//找线索二叉树（中序线索化）的最后一个节点
BinaryTreeNode<T>* GetLast_IO()
{
	return GetLast_IO(root);
}
BinaryTreeNode<T>* GetLast_IO(BinaryTreeNode<T>* root)
{
	//中序遍历是“左根右顺序”
	//一直找真正的右孩子即可。
	if (root == nullptr)
		return nullptr;
	BinaryTreeNode<T>* tmpnode = root;
	while (tmpnode->rtag == 0) //指向的是真正的右子节点
	{
		tmpnode = tmpnode->rchild;
	}
	return tmpnode;
}

操作2：找线索二叉树中某个节点的前趋和后继节点

以 中序遍历 序列线索化的二叉树为例看代码的书写，在 ThreadBinaryTree 类模板的定义中，可以增加GetNextPoint_IO()和GetPriorPoint_IO()成员函数。

  • 找线索二叉树（中序线索化）中当前节点的后继节点 
//找线索二叉树（中序线索化）中当前节点的后继节点
BinaryTreeNode<T>* GetNextPoint_IO(BinaryTreeNode<T>* currnode)
{
	if (currnode == nullptr)
		return nullptr;
	if (currnode->rtag == 1)//rchild指向的是后继节点（线索）
		return currnode->rchild;

	//如果该节点的 rchild指向的是真正的右孩子节点，那么该怎么获得该节点的后继节点呢？
	//考虑到中序遍历的顺序为“左根右”，那么当前节点（看成根）的右子树 的第一个节点就是：
	return GetFirst_IO(currnode->rchild); //在右子树中查找第一个要访问的节点
}
  • 找线索二叉树（中序线索化）中当前节点的前趋节点 
//找线索二叉树（中序线索化）中当前节点的前趋节点
BinaryTreeNode<T>* GetPriorPoint_IO(BinaryTreeNode<T>* currnode)
{
	if (currnode == nullptr)
		return nullptr;

	if (currnode->ltag == 1)//lchild指向的是前趋节点（线索）
		return currnode->lchild;

	//如果该节点的 lchild指向的是真正的左孩子节点，那么该怎么获得该节点的前趋节点呢？
	return GetLast_IO(currnode->lchild); //在左子树中查找最后一个要访问的节点
}

至于 前序遍历 序列线索化的二叉树找前趋和后继节点，我们增加GetNextPoint_PO()和GetPriorPoint_PO()成员函数即可。

  • 找线索二叉树（前序线索化）中当前节点的后继节点 
//找线索二叉树（前序线索化）中当前节点的后继节点
BinaryTreeNode<T>* GetNextPoint_PO(BinaryTreeNode<T>* currnode)
{
	//根左右
	if (currnode == nullptr)
		return nullptr;

	if (currnode->rtag == 1)
		return currnode->rchild;

	//该节点有右孩子才能走到这里，
	//那么：如果该节点有左孩子，则该节点的后继节点必然是左孩子的第一个节点，根据根左右顺序，就是该左孩子节点
	if (currnode->ltag == 0) //有左孩子
		return currnode->lchild;

	//没有左孩子，而且前面已经确定了有右孩子，则根据根左右顺序
	return currnode->rchild;
}
  • 找线索二叉树（前序线索化）中当前节点的前趋节点
// 找线索二叉树（前序线索化）中当前节点的前趋节点
template <typename T>
BinaryTreeNode<T>* ThreadBinaryTree<T>::GetPriorPoint_PO(BinaryTreeNode<T>* currnode)
{
	if (currnode == nullptr)
		return nullptr;

	// 如果当前节点的左标签为1，说明左孩子是指向前趋节点的线索
	if (currnode->ltag == 1)
		return currnode->lchild;

	// 如果当前节点有父节点指针
	if (currnode->parent != nullptr)
	{
		// 如果当前节点是父节点的右孩子，并且当前节点的左兄弟存在
		if (currnode == currnode->parent->rchild && currnode->parent->ltag == 0)
		{
			BinaryTreeNode<T>* leftSibling = currnode->parent->lchild;
			// 找到左兄弟子树中最后一个被访问的节点
			while (leftSibling->rtag == 0 || leftSibling->ltag == 0)
			{
				if (leftSibling->rtag == 0)
					leftSibling = leftSibling->rchild;
				else if (leftSibling->ltag == 0)
					leftSibling = leftSibling->lchild;
			}
			return leftSibling;
		}
		// 如果当前节点是父节点的左孩子，或者当前节点是父节点的右孩子但没有左兄弟
		else
		{
			return currnode->parent;
		}
	}

	// 如果没有父节点指针，无法确定前趋节点
	return nullptr;
}

操作3：对线索二叉树进行遍历

要注意的是，传统二叉树遍历的相关代码（递归遍历）并不适用于线索二叉树，因为递归遍历时只遍历真正的孩子节点。所以，我们要对这些遍历代码做出一定的修改。

先来看一下传统递归遍历的代码。

  • 传统中序递归遍历来遍历线索二叉树 
//传统中序递归遍历来遍历线索二叉树：		
void inOrder_Org()
{
	inOrder_Org(root);
}
void inOrder_Org(BinaryTreeNode<T>* tNode)  //中序遍历二叉树
{
	if (tNode != nullptr) //若二叉树非空
	{
		//左根右顺序
		if (tNode->ltag == 0) //是真正的左孩子
			inOrder_Org(tNode->lchild);  //递归方式中序遍历左子树

		cout << (char)tNode->data << " "; //输出节点的数据域的值

		if (tNode->rtag == 0) //是真正的右孩子
			inOrder_Org(tNode->rchild); //递归方式中序遍历右子树
	}
}

我们以中序遍历序列线索化的二叉树为例，所进行的遍历也要求是中序遍历。线索化后的二叉树的遍历方式与以往二叉树的遍历方式不同，必须要充分利用这些线索来增加遍历的效率。

具体的操作方式可以参考如下代码。

  • 中序遍历按照“中序遍历序列线索化的二叉树”线索二叉树 
//中序遍历按照“中序遍历序列线索化的二叉树”线索二叉树
void inOrder_IO()
{
	inOrder_IO(root);
}
void inOrder_IO(BinaryTreeNode<T>* tNode)
{
	BinaryTreeNode<T>* tmpNode = GetFirst_IO(tNode);
	while (tmpNode != nullptr)  //从第一个节点开始一直找后继即可
	{
		cout << (char)tmpNode->data << " "; //输出节点的数据域的值
		tmpNode = GetNextPoint_IO(tmpNode);
	}
}

思考一下，如果进行中序逆向遍历是不是也可以做到了呢？这就需要用到 GetLast_IO 和 GetPriorPoint_IO。参考如下代码。  

  • 逆向中序遍历按照“中序遍历序列线索化的二叉树”线索二叉树 
//逆向中序遍历按照“中序遍历序列线索化的二叉树”线索二叉树
void revInOrder_IO()
{
	revInOrder_IO(root);
}
void revInOrder_IO(BinaryTreeNode<T>* tNode)
{
	BinaryTreeNode<T>* tmpNode = GetLast_IO(tNode);
	while (tmpNode != nullptr)  //从第一个节点开始一直找后继即可
	{
		cout << (char)tmpNode->data << " "; //输出节点的数据域的值
		tmpNode = GetPriorPoint_IO(tmpNode);
	}
}

通过代码可以看到，只要能成功找到前趋和后继节点，进行遍历是一件很容易的事。你也可以在 main 主函数中加入如下代码进行测试。  

mythreadtree.inOrder_Org(); //传统中序递归遍历
cout << endl;
mythreadtree.inOrder_IO();
cout << endl;
mythreadtree.revInOrder_IO();
cout << endl;

操作4：对线索二叉树的节点进行查找

这里用中序遍历序列线索化的二叉树为例来讲解。参考如下代码。  

  • 中序遍历序列线索化的二叉树查找某个节点(假设二叉树的节点各不相同) 
//中序遍历序列线索化的二叉树查找某个节点(假设二叉树的节点各不相同)
BinaryTreeNode<T>* SearchElem_IO(const T& e)
{
	return SearchElem_IO(root, e);
}
BinaryTreeNode<T>* SearchElem_IO(BinaryTreeNode<T>* tNode, const T& e)
{
	if (tNode == nullptr)
		return nullptr;
	if (tNode->data == e)  //从根开始找
		return tNode;

	//这里的代码取自于  中序遍历按照“中序遍历序列线索化的二叉树”线索二叉树inOrder_IO()的代码
	BinaryTreeNode<T>* tmpNode = GetFirst_IO(tNode);
	while (tmpNode != nullptr)  //从第一个节点开始一直找后继即可
	{
		if (tmpNode->data == e)
			return tmpNode;
		tmpNode = GetNextPoint_IO(tmpNode);
	}
	return nullptr;
}

可以在 main 主函数中加入下面的代码进行测试。

int val = 'B';
BinaryTreeNode<int>* p = mythreadtree.SearchElem_IO(val);
if (p != nullptr)
{
	cout << "找到了值为" << (char)val << "的节点" << endl;

	//顺便找下后继和前趋节点
	BinaryTreeNode<int>* nx = mythreadtree.GetNextPoint_IO(p);
	if (nx != nullptr)
		cout << "后继节点值为" << (char)nx->data << "。" << endl;

	BinaryTreeNode<int>* pr = mythreadtree.GetPriorPoint_IO(p);
	if (pr != nullptr)
		cout << "前趋节点值为" << (char)pr->data << "。" << endl;

}
else
{
	cout << "没找到值为" << (char)val << "的节点" << endl;
}

思考一下，对于“前序遍历序列线索化的二叉树”和“后序遍历序列线索化的二叉树”，能通过上述代码进行一定的改造来查找节点吗？

前序遍历序列线索化的二叉树是可以的。因为前序遍历序列线索化的二叉树的第一个节点就是根节点，而且可以通过 GetNextPoint_PO 成员函数不断找到后继节点。参考如下代码。

  • 前序遍历序列线索化的二叉树查找某个节点(假设二叉树的节点各不相同) 
//前序遍历序列线索化的二叉树查找某个节点(假设二叉树的节点各不相同)
BinaryTreeNode<T>* SearchElem_PO(const T& e)
{
	return SearchElem_PO(root, e);
}
BinaryTreeNode<T>* SearchElem_PO(BinaryTreeNode<T>* tNode, const T& e)
{
	if (tNode == nullptr)
		return nullptr;

	BinaryTreeNode<T>* tmpNode = root; //根就是第一个节点
	while (tmpNode != nullptr)  //从第一个节点开始一直找后继即可
	{
		if (tmpNode->data == e)
			return tmpNode;
		tmpNode = GetNextPoint_PO(tmpNode);
	}
	return nullptr;
}

后序遍历序列线索化的二叉树也是可以的，虽然这种二叉树找后继节点不行，但是找前趋节点是可以的，通过GetPriorPoint_POSTO成员函数，而且，最后一个节点就是根节点。从最后一个节点向前找即可。参考下面的代码。  

  • 后序遍历序列线索化的二叉树查找某个节点(假设二叉树的节点各不相同) 
//后序遍历序列线索化的二叉树查找某个节点(假设二叉树的节点各不相同)
BinaryTreeNode<T>* SearchElem_POSTO(const T& e)
{
	return SearchElem_POSTO(root, e);
}
BinaryTreeNode<T>* SearchElem_POSTO(BinaryTreeNode<T>* tNode, const T& e)
{
	if (tNode == nullptr)
		return nullptr;

	BinaryTreeNode<T>* tmpNode = root; //根就是最后一个节点
	while (tmpNode != nullptr)  //从最后一个节点开始一直找前趋即可
	{
		if (tmpNode->data == e)
			return tmpNode;
		tmpNode = GetPriorPoint_POSTO(tmpNode);
	}
	return nullptr;
}

小结

这节课，我讲解了线索二叉树的相关内容，包括线索二叉树的基本概念、二叉树的线索化、线索二叉树的操作3个子话题。

线索二叉树存在的意义，就是充分利用线索，尽量简化二叉树的操作，更方便地找一个节点的前趋和后继节点，从而为更快捷地遍历整个二叉树创造条件。

线索二叉树，其实就是加上了线索的二叉树，而线索，也就是指向前趋或后继节点的指针。

我们可以通过给没有被使用到的二叉树节点的指针域，保存这个节点的前趋或后继节点的指针信息，实现二叉树的线索化。

在线索化二叉树的过程中，首先要注意的是必须是空闲的指针域才能被线索化，在线索化的过程中，不但要标记该指针域是被线索化过的，还要确保该指针域正确地指向其前趋或后继节点。

最后提醒一下，这节课我们所有实现的代码都以能够理解为主，无需死记硬背。

归纳思考

  1. 前面通过代码已经实现了用 中序 遍历序列线索化二叉树和用 前序 遍历序列线索化二叉树。你是否可以仿照前面的代码自己试着写一下如何用 后序 遍历序列线索化二叉树呢？

  2. 参考前面的代码，尝试写出代码完成对 后序 遍历序列线索化的二叉树找前趋和后继节点。

  3. 参考前面的代码，对“前序遍历序列线索化的二叉树”进行前序遍历，对“后序遍历序列线索化的二叉树”进行后序遍历，看是否能做到。

这里给予一些提示：

  • 对“前序遍历序列线索化的二叉树”，因为找当前节点的后继节点是没问题的，所以对这种二叉树进行前序遍历是可以的。但因为找当前节点的前趋节点是无法做到的，因此进行前序逆向遍历是不行的。

  • 对“后序遍历序列线索化的二叉树”，因为找当前节点的前趋节点是没问题的，所以对这种二叉树进行逆向后序遍历是可以的。但因为找当前节点的后继节点是无法做到的，因此进行后序遍历是不行的。

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处： 免费源码网-免费的源码资源网站 » 【高阶数据结构】线索二叉树的实现和一系列相关操作（精美图解+完整代码）

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部