首页 / 算法 / 线索二叉树C++实现
线索二叉树C++实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了线索二叉树C++实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含6283字,纯文字阅读大概需要9分钟。
内容图文
![线索二叉树C++实现](/upload/InfoBanner/zyjiaocheng/642/1b90645d09e6432f86a86b9593ede56d.jpg)
线索二叉树C++实现
什么是线索二叉树
线索二叉树主要体现在二叉树的 DFS 中, 也就是前序, 中序, 与后序遍历, 我们以中序遍历为例, 讲述线索二叉树线索的原理.
线索主要表现在, DFS 的过程中记录遍历的前驱与后继节点, 可以用下面的图来表示节点,
代码表示就是
struct Tree{
Tree *left, *right;
int number;
int lbit, rbit; // 用于记录节点的左右指针是前驱还是后继
};
首先, 我们先来回顾一下二叉树的中序遍历, (本文讲述的以下算法均是基于中序遍历的),
二叉树的中序遍历:
用代码表示就是:
void Midorder(Tree *node)
{
if(node != nullptr)
{
Midorder(node->left);
VISIT(node); // 访问节点
Midorder(node->right);
}
}
对于下图的中序遍历, 我们遍历的顺序就是 D, B, J, E, A, H, F, I, C, G.
接下来, 我们以此图来构造出一个线索二叉树, 构造线索二叉树只有两个原则:
prior 是中序遍历序列中的当前节点的前一个节点, 比如 A的prior 就是 E 节点,
- 若当前访问的结点的左指针域为空,则它指向prior指的结点, 同时置该节点 lbit 的值为 0;
- 若prior所指结点的右指针域为空,则它指向当前访问的结点, 同时置前驱节点的 rbit 为 0。
因为我们每次都要记录 prior 节点, 因此我们不妨将 prior 设置为全局变量, 这样访问起来较为方便
而构建这个索引的代码, 我们可以在中序遍历的基础上完成:
Tree *prior = *head;
void Mid_order(Tree *node)
{
if(node != nullptr)
{
Mid_order(node->left);
if(node->left == nullptr)
{
node->lbit = 0;
node->left = prior;
}
if(prior->right == nullptr)
{
prior->rbit = 0;
prior->right = node;
}
VISIT(node);
prior = node;
Mid_order(node->right);
}
}
假设我们最先访问的是head节点, 及第一个prior 节点是 head 节点. 现在我们构造出了下面这样的线索二叉树,
内容总结
以上是互联网集市为您收集整理的线索二叉树C++实现全部内容,希望文章能够帮你解决线索二叉树C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。