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

🤡博客主页：醉竺

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

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

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

目录

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的节点，才会递归调用ReleaseNodeif (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; //标志先给0tnode->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，说明该节点没有前趋节点}//这个前趋节点的后继节点肯定是当前这个节点tnodeif (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. 参考前面的代码，对“前序遍历序列线索化的二叉树”进行前序遍历，对“后序遍历序列线索化的二叉树”进行后序遍历，看是否能做到。

这里给予一些提示：

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/420369.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

哈希表，算法

哈希表，算法

哈希存储(散列存储) 为了快速定位数据 哈希表 哈希冲突 / 哈希矛盾 关键字不一样&#xff0c;但是映射之后结果一样 如何避免 哈希矛盾&#xff1f; 1、重新设计哈希函数&#xff0c;尽可能均匀散列分布在哈希表 2、开放定址法&#xff1a;向下寻找未存储的位置进行存放数…
阅读更多...
.net 调用海康SDK实现NVR录像视频的下载

.net 调用海康SDK实现NVR录像视频的下载

📢欢迎点赞 ：👍 收藏 ⭐留言 📝 如有错误敬请指正，赐人玫瑰，手留余香！📢本文作者：由webmote 原创📢作者格言：新的征程，最近一直被测试拿捏，痛苦的挣扎中… 我们面对的不仅仅是技术还有人心，人心不可测，海水不可量，唯有技术，才是深沉黑夜中的一座闪烁的灯…
阅读更多...
记录一下linux安装nginx，也是很简单了啦

记录一下linux安装nginx，也是很简单了啦

1、下载nginx 官网下载nginx&#xff1a;http://nginx.org/&#xff0c;这里很简单&#xff0c;下载自己想要的版本就行&#xff0c;这里不罗嗦 1、进入home目录&#xff0c;建一个文件夹nginx rootroot ~]# cd /home rootroot home]# mkdir nginx rootroot home]# cd /nginx2…
阅读更多...
使用LLaMA-Factory快速训练自己的专用大模型

使用LLaMA-Factory快速训练自己的专用大模型

本文聊聊 LLama-Factory&#xff0c;它是一个开源框架&#xff0c;这里头可以找到一系列预制的组件和模板&#xff0c;让你不用从零开始&#xff0c;就能训练出自己的语言模型&#xff08;微调&#xff09;。不管是聊天机器人&#xff0c;还是文章生成器&#xff0c;甚至是问答…
阅读更多...
【大模型专栏—入门篇】机器学习与深度学习基础测试

【大模型专栏—入门篇】机器学习与深度学习基础测试

大模型专栏介绍 &#x1f60a;你好&#xff0c;我是小航&#xff0c;一个正在变秃、变强的文艺倾年。 &#x1f514;本文为大模型专栏子篇&#xff0c;大模型专栏将持续更新&#xff0c;主要讲解大模型从入门到实战打怪升级。如有兴趣&#xff0c;欢迎您的阅读。 &#x1f4…
阅读更多...
（Charles）如何抓取手机http的报文

（Charles）如何抓取手机http的报文

抓包的目的&#xff1a; 发现bug需要定位要抓包 检查数据传输的安全性 接口测试遇到需求文档不全要抓包 抓包主要抓取的是http协议&#xff08;https协议&#xff09;的报文 http协议规范客户端和服务端的数据传输格式&#xff0c;是一个标准和规范 每个http连接包括请求消息和…
阅读更多...
Oracle OCP认证值得考吗? 需要门槛吗?

Oracle OCP认证值得考吗? 需要门槛吗?

随着数据量的爆炸性增长和企业对数据依赖性的提升&#xff0c;对数据库专业人士的需求也在不断上升。OCP认证&#xff0c;作为Oracle公司提供的权威认证之一&#xff0c;长期以来被视为数据库专业人士技能和知识水平的重要标志。 但随着技术的发展和认证种类的增多&#xff0c;…
阅读更多...
数据结构基础讲解（七）——数组和广义表专项练习

数据结构基础讲解（七）——数组和广义表专项练习

本文数据结构讲解参考书目&#xff1a; 通过网盘分享的文件&#xff1a;数据结构 C语言版.pdf 链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwdze8e 提取码: ze8e 数据结构基础讲解&#xff08;六&#xff09;——串的专项练习-CSDN博客 个人主页&#xff1a;樱娆…
阅读更多...
教你用 Python 自制简单版《我的世界》

教你用 Python 自制简单版《我的世界》

《我的世界 Minecraft》大家应该都听说过&#xff0c;但你有没有想过自己写一个这样的游戏呢&#xff1f;太难、太复杂了&#xff1f;也许吧&#xff0c;但是不试一试你怎么知道能不能成呢&#xff1f; 国外有位叫fogleman的开发者就用Python做了这样的一件事——自制《我的世…
阅读更多...
【Qt网络】—— Qt网络编程

【Qt网络】—— Qt网络编程

目录 &#xff08;一&#xff09;UDP Socket 1.1 核心API概览 1.2 代码示例 1.2.1 回显服务器 1.2.2 回显客户端 &#xff08;二&#xff09;TCP Socket 2.1 核心API概览 2.2 代码示例 2.2.1 回显服务器 2.2.2 回显客户端 &#xff08;三&#xff09;HTTP Client 3…
阅读更多...
虚拟现实智能家居实训系统实训解决方案

虚拟现实智能家居实训系统实训解决方案

随着科技的飞速发展&#xff0c;智能家居已成为现代生活的重要组成部分&#xff0c;它不仅极大地提升了居住的便捷性与舒适度&#xff0c;还推动了物联网、大数据、人工智能等前沿技术的融合应用。为了满足市场对智能家居专业人才日益增长的需求&#xff0c;虚拟现实智能家居实…
阅读更多...
Mongodb 4.2.25 安装教程

Mongodb 4.2.25 安装教程

一、上传部署包 1.1上传mongodb包进入/usr/local目录&#xff0c;将mongodb-linux-x86_64-rhel70-4.2.25.tgz包传到该目录下。 cd /usr/local 二、安装 2.1解压 tar zxvf mongodb-linux-x86_64-rhel70-4.2.25.tgz 2.2修改名称 mv mongodb-linux-x86_64-rhel70-4.2.25/ mong…
阅读更多...
突破最强算法模型，Transformer ！！

突破最强算法模型，Transformer ！！

这几天&#xff0c;大家对于Transformer的问题&#xff0c;还是不少。 今儿再和大家聊聊~ 简单来说&#xff0c;Transformer 是一种神经网络模型&#xff0c;在机器翻译、语言理解等任务中表现特别好。它的核心思想是自注意力机制&#xff08;Self-Attention&#xff09;&…
阅读更多...
反序列化漏洞练习2

反序列化漏洞练习2

拿到题目&#xff0c;发现目标是获得flag.php的内容,且sis中admin和passwd等于sis2407时会输出fag的内容 根据源码编写序列化代码 <?php error_reporting(0); class sis{public $admin;public $passwd;public function __construct(){$this->admin "sis2407"…
阅读更多...
【redis】认识redis和分布式系统

【redis】认识redis和分布式系统

文章目录 认识 redisredis 的主要功能实现数据库实现缓存实现消息中间件 基础概念评价指标 分布式系统单机架构为什么数据多了主机就难以应对 &#xff1f;分布式系统 认识 redis redis 的主要功能 用来在内存中存储数据 定义变量不就是在内存中存储数据吗&#xff1f;为什么…
阅读更多...
Python计算机视觉 第7章-图像搜索

Python计算机视觉 第7章-图像搜索

Python计算机视觉 第7章-图像搜索 7.1　基于内容的图像检索 在大型图像数据库上&#xff0c;CBIR&#xff08;Content-Based Image Retrieval&#xff0c;基于内容的图像检索&#xff09;技术用于检索在视觉上具相似性的图像。这样返回的图像可以是颜色相似、纹理相似、图像中…
阅读更多...
halcon try_catch无try不项目

halcon try_catch无try不项目

#1&#xff0c;没有用过try的人&#xff0c;肯定是没有真正实战做过项目的。 #2&#xff0c;try_catch又被称为抓异常语句&#xff0c;出现异常的代码会在 exception里进行显示&#xff0c;这个exception就是一个字符串的数组。 #3&#xff0c;为什么要用&#xff0c;halcon的一…
阅读更多...
OpenCV结构分析与形状描述符（13）拟合椭圆函数fitEllipseDirect()的使用

OpenCV结构分析与形状描述符（13）拟合椭圆函数fitEllipseDirect()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆&#xff0c;该椭圆拟合一组2D点。它返回一个内切于该椭圆的旋转矩形。使用了由[91]提出的直接…
阅读更多...
将字符串序列中的每个字符串，用字符“0“扩充到x位 Series.str.zfill(x)

将字符串序列中的每个字符串，用字符“0“扩充到x位 Series.str.zfill(x)

【小白从小学Python、C、Java】 【考研初试复试毕业设计】 【Python基础AI数据分析】 将字符串序列中的每个字符串sn 如果sn的位数不足x位 则在sn左侧补充0凑齐x位 即在sn左侧补充x-sn个0 Series.str.zfill(x) 选择题 关于以下代码输出结果的说法中正确的是? import pandas …
阅读更多...
在国产芯片上实现YOLOv5/v8图像AI识别-【4.4】RK3588网络摄像头推理后推流到RTSP更多内容见视频

在国产芯片上实现YOLOv5/v8图像AI识别-【4.4】RK3588网络摄像头推理后推流到RTSP更多内容见视频

本专栏主要是提供一种国产化图像识别的解决方案&#xff0c;专栏中实现了YOLOv5/v8在国产化芯片上的使用部署&#xff0c;并可以实现网页端实时查看。根据自己的具体需求可以直接产品化部署使用。 B站配套视频&#xff1a;https://www.bilibili.com/video/BV1or421T74f 前言…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发