思路来源：数据结构（十七） – C语言版 – 树 - 二叉树的线索化及遍历 – 先序线索化、中序线索化、后序线索化

文章目录

• 1. 中序线索化二叉树
• 2. 前序线索二叉树
• 3. 后序线索二叉树

1. 中序线索化二叉树

这里给出上述博客的中序线索化二叉树的大致内容，有什么不懂，可以移步上述博客：

二叉树的遍历有四种方式：先序遍历、中序遍历、后序遍历、层序遍历。

那么根据遍历来进行线索化的方式也就有四种方式：先序线索化、中序线索化、后序线索化、层序线索化，其实严格意义上来说，除了遍历的顺序不同，其他的没什么太大的区别。对于线索化来将也是一样的。

原来的二叉链表的节点中包含了两个指针域（左右指针）、一个数据域，很难确定节点的两个指针域保存的是子树还是线索了。那么为了解决这样的问题，我们需要在结构定义的基础上加入两个标志位（ ltag、rtag ）分别用来表示当前指针的指向的含义。

ltag=0：节点左子树指向这个节点的左孩子
ltag=1：节点左子树指向这个节点的前驱

rtag=0：节点的右子树指向这个节点的右孩子
rtag=1：节点的右子树指向这个节点的后继

中序线索化二叉树步骤

在中序遍历的基础上，将原本遍历函数中输出的语句修改成线索化的代码即可。

1. 如果当前节点 current 左指针域为空，则需要将其做指针域加上前驱线索
2. 如果当前节点的上一次访问的节点（ prev 指针）右子树为空，则需要为 prev 指针指向后继节点
3. 使 prev 指针跟上当前节点指针

测试中序线索二叉树构造类

这里为了方便，选择了二叉搜索树的构造方式来创建树

#include 
#include struct TreeNode
{int data;TreeNode *left = nullptr;TreeNode *right = nullptr;int ltag = 0;int rtag = 0;TreeNode(int _data) : data(_data) {}
};class Tree
{
private:void InsertNode(int data){if (root == nullptr){root = new TreeNode(data);}else{TreeNode *prev = nullptr;TreeNode *node = root;while (node != nullptr){prev = node;if (node->data >= data){node = node->left;}else{node = node->right;}}TreeNode *next = new TreeNode(data);if (prev->data >= data){prev->left = next;}else{prev->right = next;}}}void _InodesDisplay(TreeNode *root){if (root == nullptr)return;_InodesDisplay(root->left);std::cout << root->data << " ";_InodesDisplay(root->right);}void Destroy(TreeNode *root){if (root == nullptr){return;}Destroy(root->left);Destroy(root->right);delete root;}public:TreeNode *root;Tree(const std::vector &vet){this->root = nullptr;for (int i = 0; i < vet.size(); i++){InsertNode(vet[i]);}}~Tree(){Destroy(root);}//中序遍历void InodesDisplay(){_InodesDisplay(root);std::cout << "\n";}
};

中序线索二叉树实现与测试：

//思路:https://blog.csdn.net/songshuai0223/article/details/106551499?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166795700016782425681940%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166795700016782425681940&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-106551499-null-null.142^v63^control,201^v3^control_2,213^v2^t3_esquery_v1&utm_term=%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1018.2226.3001.4187#include "CreatTree.h"using namespace std;//中序线索化二叉树
void InorderSpan(TreeNode *root, TreeNode *&prev)
{if (root == nullptr)return;InorderSpan(root->left, prev);//当前节点左指针为空，左指针指向前驱if (root->left == nullptr){root->left = prev;root->ltag = 1;}// prev节点右指针为空，右指针指向当前节点(后继节点)if (prev != nullptr && prev->right == nullptr){prev->right = root;prev->rtag = 1;}prev = root;InorderSpan(root->right, prev);
}TreeNode *InorderSpan(TreeNode *&root)
{TreeNode *ret = root;root = nullptr; //摘头，Tree类防止析构函数崩溃TreeNode *prev = nullptr;InorderSpan(ret, prev);return ret;
}//中序线索化二叉树的遍历TreeNode *GetNextNode(TreeNode *root)
{if (root == nullptr){return nullptr;}// 右标志位 1，可以直接得到后继节点if (root->rtag == 1){return root->right;}// 右标志位0，则要找到右子树最左下角的节点else{TreeNode *ret = root->right;while (ret != nullptr && ret->ltag == 0){ret = ret->left;}return ret;}
}
void DisplayTree(TreeNode *root)
{if (root == nullptr)return;//找最左下的节点while (root->ltag == 0){root = root->left;}cout << root->data << " ";//根据后继节点打印这颗树while (root->right != nullptr){root = GetNextNode(root);cout << root->data << " ";}
}//释放线索化二叉树的节点
void Destroy(TreeNode *root)
{if (root == nullptr)return;while (root->ltag == 0){root = root->left;}TreeNode *next = root->right;delete root;root = nullptr;while (next != nullptr){TreeNode *node = next;next = GetNextNode(next);delete node;node = nullptr;}
}int main(int argc, char const *argv[])
{Tree tree({3, 2, 4, 6, 7, 1, 2, 7, 1, 0, 7, 9});tree.InodesDisplay();TreeNode *ret = InorderSpan(tree.root);DisplayTree(ret);//销毁线索化二叉树Destroy(ret);return 0;
}

2. 前序线索二叉树

思路和中序线索二叉树类似：

首先大致递归思路是前序遍历顺序。

1. 如果当前节点 current 左指针域为空，则需要将其做指针域加上前驱线索
2. 如果当前节点的上一次访问的节点（ prev 指针）右子树为空，则需要为 prev 指针指向后继节点
3. 使 prev 指针跟上当前节点指针

#include "CreatTree.h"using namespace std;//前序线索二叉树
void PreorderSpan(TreeNode *root, TreeNode *&prev)
{if (root == nullptr){return;}if (root->left == nullptr){root->left = prev;root->ltag = 1;}if (prev != nullptr && prev->right == nullptr){prev->right = root;prev->rtag = 1;}prev = root;//因为是先修改的Node的tag,所以这里需要判断tag，否则会出现死循环if (root->ltag == 0)PreorderSpan(root->left, prev);if (root->rtag == 0)PreorderSpan(root->right, prev);
}TreeNode *PreorderSpan(TreeNode *&root)
{TreeNode *prev = nullptr;TreeNode *ret = root;root = nullptr;PreorderSpan(ret, prev);return ret;
}void DisplayTree(TreeNode *root)
{if (root == nullptr){return;}while (root != nullptr){while (root->ltag == 0){cout << root->data << " ";root = root->left;}cout << root->data << " ";root = root->right;}
}void Destroy(TreeNode *root)
{if (root == nullptr){return;}while (root != nullptr){while (root->ltag == 0){TreeNode *next = root->left;delete root;root = next;}TreeNode *next = root->right;delete root;root = next;}
}int main(int argc, char const *argv[])
{Tree tree({2, 4, 1, 5, 2, 6, 7, 3, 1, 0, 9});tree.InodesDisplay();TreeNode *node = PreorderSpan(tree.root);DisplayTree(node);Destroy(node);return 0;
}

3. 后序线索二叉树

首先按照后序递归的方式进行递归，在打印的步骤出修改成：

如果当前节点的左子树为空，让左子树指针指向前驱。
当前节点的右子树为空，让右子树指针指向后继。

唯一不同的是：在进行遍历线索二叉树时，后序遍历需要记录父节点，这里采用参考博客的思路
先按照 根节点->右孩子->左孩子 的方式来遍历访问节点，并且将顺序记录一下，最后将刚才记录的顺序翻转即可

这里选择将反向输出的节点放入栈中达到逆向目的。

#include "CreatTree.h"#include using namespace std;//后序线索二叉树
void PostorderSpan(TreeNode *root, TreeNode *&prev)
{if (root == nullptr)return;PostorderSpan(root->left, prev);PostorderSpan(root->right, prev);if (root->left == nullptr){root->left = prev;root->ltag = 1;}if (prev != nullptr && prev->right == nullptr){prev->rtag = 1;prev->right = root;}prev = root;
}TreeNode *PostorderSpan(TreeNode *&root)
{TreeNode *ret = root;root = nullptr;TreeNode *prev = nullptr;PostorderSpan(ret, prev);return ret;
}//遍历线索二叉树
//先按照 根节点->右孩子->左孩子 的方式来遍历访问节点，并且将顺序记录一下，最后将刚才记录的顺序翻转即可(使用栈)
TreeNode *GetNextNode(TreeNode *root)
{if (root == nullptr)return nullptr;//将前驱节点返回，最后逆置相当于找后继节点if (root->ltag == 1){return root->left;}else{// root->ltag = 0;有左子树if (root->rtag == 1){//存在后继节点return root->left;}else if (root->right != nullptr && root->rtag == 0){//左右子树都存在，向右子树走return root->right;}else{return root->left;}}
}void DisplayTree(TreeNode *root)
{stack st;while (root != nullptr){st.push(root);root = GetNextNode(root);}while (!st.empty()){cout << st.top()->data << " ";st.pop();}
}int main(int argc, char const *argv[])
{Tree tree({5, 1, 0, 2});tree.InodesDisplay();TreeNode *node = PostorderSpan(tree.root);DisplayTree(node);return 0;
}