《数据结构、算法与应用C++语言描述》-线索二叉树的定义与C++实现

_23Threaded BinaryTree

可编译运行代码见：GIithub::Data-Structures-Algorithms-and-Applications/_24Threaded_BinaryTree

线索二叉树定义

在普通二叉树中，有很多nullptr指针被浪费了，可以将其利用起来。

在这里插入图片描述

首先我们要来看看这空指针有多少个呢？对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-（n-1）=n+1个空指针域。

对上图**(参考：《大话数据结构 溢彩加强版 程杰》160页图)**做中序遍历，得到了HDIBJEAFCG这样的字符序列，遍历过后，我们可以知道，结点I的前驱是D，后继是B，结点F的前驱是A，后继是C。也就是说，我们可以很清楚地知道任意一个结点，它的前驱和后继是哪一个结点。

可是这是建立在已经遍历过的基础之上的。在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都必须先遍历一次。这样比较浪费时间。

我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

我们把二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。将所有空指针域中的lchild，改为指向当前结点的前驱。由此得出，经过线索化的二叉树变成了一个双向链表。双向链表相比于二叉树更容易找到某节点的前驱和后继节点。因此，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

但是还有一个问题，如果将这些空指针作为线索后无法区分该指针是线索还是指向孩子节点，因此需要标志位LTag为True表示该节点的左指针是索引，RLag为true表示该节点的右指针是索引，反之不是索引。

代码

main.cpp

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17点06分
Last Version:			V1.0
Descriptions:			线索二叉树
*/
#include "inThreadedBinaryTreeChains.h"
int main() {
    inThreadedBinaryTreeChainsTest();
    return 0;
}

inThreadedBinaryTreeChains.h

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17点06分
Last Version:			V1.0
Descriptions:			线索二叉树链表表示
*/

#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H
#include <iostream>
#include "binaryTree.h"
#include "inThreadedBinaryTreeNode.h"
using namespace std;
/*二叉树基础测试函数*/
void inThreadedBinaryTreeChainsTest();
template<class E>
class inThreadedBinaryTreeChains : public binaryTree<inThreadedBinaryTreeNode<E>>
{
public:
    /*二叉树的基础成员函数*/
    /*构造函数函数*/
    inThreadedBinaryTreeChains() {
        root = nullptr; treeSize = 0;
    }
    /*析构函数*/
    ~inThreadedBinaryTreeChains() { erase(); }
    /*当树为空时，返回true；否则，返回false*/
    bool empty() const { return treeSize == 0; }
    /*返回元素个数*/
    int size() const { return treeSize; }

    void inOrderThreaded()  // 中序遍历索引，就是中序遍历的时候添加索引
    {
        pre = nullptr;
        inOrderThreaded(root);
    }

    /*中序遍历二叉树，使用函数指针的目的是是的本函数可以实现多种目的*/
    void inOrder(void(*theVisit)(inThreadedBinaryTreeNode<E>*))
    {
        visit = theVisit;
        /*是因为递归，所以才要这样的*/
        inOrder(root);/*这里调用的是静态成员函数inOrder()*/
    }
    /*中序遍历---输出endl*/
    void inOrderOutput() { inOrder(output); cout << endl; }

    /*后续遍历二叉树，使用函数指针的目的是是的本函数可以实现多种目的*/
    void postOrder(void(*theVisit)(inThreadedBinaryTreeNode<E>*))
    {
        visit = theVisit;
        /*是因为递归，所以才要这样的*/
        postOrder(root);/*这里调用的是静态成员函数inOrder()*/
    }
    /*后序遍历---输出endl*/
    void postOrderOutput() { postOrder(output); cout << endl; }

    /*清空二叉树 这里必须使用后序遍历 不然会出错*/
    void erase()
    {
        postOrder(dispose);
        root = nullptr;
        treeSize = 0;
    }
    /*输入时为了将root根节点传递给createBiTree()函数*/
    void input(void)
    {
        createBiTree(root);
    }
private:
/*二叉树基础私有成员*/
    inThreadedBinaryTreeNode<E>* root;//指向根的指针
    int treeSize;//树的结点个数
    static inThreadedBinaryTreeNode<E>* pre;// 在线索化时使用的前驱temp
    static void (*visit)(inThreadedBinaryTreeNode<E>*);//是一个函数指针,返回值为void 函数参数为binaryTreeNode<E>*
    static void inOrder(inThreadedBinaryTreeNode<E>* t);
    static void inOrderThreaded(inThreadedBinaryTreeNode<E>* t);// 中序遍历索引，就是中序遍历的时候添加索引
    static void postOrder(inThreadedBinaryTreeNode<E>* t);
    static void dispose(inThreadedBinaryTreeNode<E>* t) { delete t; }
    static void output(inThreadedBinaryTreeNode<E>* t) { cout << t->element << " "; }
    /*创建二叉树---递归---作为私有成员只能被成员函数调用*/
    void createBiTree(inThreadedBinaryTreeNode<E>*& tree);
};
/*私有静态成员初始化*/
/*这里是静态函数指针成员的初始化，不初始化会引发LINK错误*/
template<class E>
void (*inThreadedBinaryTreeChains<E>::visit)(inThreadedBinaryTreeNode<E>*) = 0;      // visit function
// 这个地方需要做一个初始化，不做的话就会bug
template<class E>
inThreadedBinaryTreeNode<E>* inThreadedBinaryTreeChains<E>:: pre = nullptr;
/*中序遍历 递归*/
/*不受索引影响的中序遍历*/
template<class E>
void inThreadedBinaryTreeChains<E>::inOrder(inThreadedBinaryTreeNode<E>* t)
{
    if (t != nullptr)
    {
        // 在其左孩子不是索引时遍历
        if(!t->LTag)
            inOrder(t->leftChild);/*中序遍历左子树*/
        visit(t);/*访问树根*/
        // 在其右孩子不是索引时遍历
        if(!t->RTag)
            inOrder(t->rightChild);/*中序遍历右子树*/
    }
}
/*中序遍历索引 递归*/
/*本文写法可以保证在多次调用此函数下依然能正常执行，当插入新元素后再执行本函数可更新节点的索引*/
template<class E>
void inThreadedBinaryTreeChains<E>::inOrderThreaded(inThreadedBinaryTreeNode<E>* t)
{
    if (t != nullptr)
    {
        if(!t->LTag)
            inOrderThreaded(t->leftChild);/*中序遍历左子树*/
        if(!t->leftChild || t->LTag) // 没有左孩子，或者是第二次遍历即左孩子指向了他的前驱
        {
            t->LTag = true;
            t->leftChild = pre;
        }
        if(pre){
            if(!pre->rightChild || t->RTag)  // 如果前驱没有右孩子，或者是第二次遍历即右孩子指向了它的后继
            {
                pre->RTag = true;
                pre->rightChild = t;
            }
        }
        pre = t;
        if(!t->RTag)
            inOrderThreaded(t->rightChild);/*中序遍历右子树*/
    }
}
/*后序遍历 递归*/
/*不受索引影响的后序遍历*/
template<class E>
void inThreadedBinaryTreeChains<E>::postOrder(inThreadedBinaryTreeNode<E>* t)
{
    if (t != nullptr)
    {
        // 在其左孩子不是索引时遍历
        if(!t->LTag)
            postOrder(t->leftChild);/*后序遍历左子树*/
        // 在其右孩子不是索引时遍历
        if(!t->LTag)
            postOrder(t->rightChild);/*后序遍历右子树*/
        visit(t);/*访问树根*/
    }
}

/*创建二叉树---递归---模板的实现*/
template<class E>
void inThreadedBinaryTreeChains<E>::createBiTree(inThreadedBinaryTreeNode<E>*& tree)
{
    E data;
    cout << "Please enter the tree element:";
    while (!(cin >> data))
    {
        cin.clear();//清空标志位
        while (cin.get() != '\n')//删除无效的输入
            continue;
        cout << "Please enter the tree element:";
    }
    cin.get();
    /*针对char类型的特例*/
    if (typeid(data) == typeid(char)) {
        if (data == '#')
            tree = nullptr;
        else {
            treeSize++;
            tree = new inThreadedBinaryTreeNode<E>(data);
            createBiTree(tree->leftChild);
            createBiTree(tree->rightChild);
        }
    }
    else/*针对其他类型*/{
        if (data == 999)
            tree = nullptr;//当遇到999时，令树的根节点为nullptr,从而结束该分支的递归
        else
        {
            treeSize++;
            tree = new inThreadedBinaryTreeNode<E>(data);
            createBiTree(tree->leftChild);
            createBiTree(tree->rightChild);
        }
    }
}
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREE_H

inThreadedBinaryTreeChains.cpp

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17点06分
Last Version:			V1.0
Descriptions:			线索二叉树测试函数
*/
#include "inThreadedBinaryTreeChains.h"
void inThreadedBinaryTreeChainsTest(){
    cout << endl << "******************************inThreadedBinaryTreeChains()函数开始**********************************" << endl;
    cout << endl << "测试成员函数*******************************************" << endl;
    cout << "输入****************************" << endl;
    cout << "默认构造函数********************" << endl;
    inThreadedBinaryTreeChains<int> a;
    a.input();
    cout << "输出****************************" << endl;
    cout << "中序输出************************" << endl;
    //递归遍历
    a.inOrderThreaded();
    cout << "a.inOrderOutput() = ";
    a.inOrderOutput();
    cout << "后序输出************************" << endl;
    a.inOrderThreaded();
    cout << "a.postOrderOutput() = ";
    a.postOrderOutput();
    cout << "empty()*************************" << endl;
    cout << "a.empty() = " << a.empty() << endl;
    cout << "size()**************************" << endl;
    cout << "a.size() = " << a.size() << endl;
    cout << "erase()**************************" << endl;
    a.erase();
    cout << "a.inOrderOutput() = ";
    a.inOrderOutput();
    cout << "******************************inThreadedBinaryTreeChains()函数结束**********************************" << endl;
}

binaryTree.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月27日09点43分
Last Version:			V1.0
Descriptions:			二叉树的抽象类
*/

#ifndef _24THREADED_BINARYTREE_BINARYTREE_H
#define _24THREADED_BINARYTREE_BINARYTREE_H
template<class T>
class binaryTree
{
public:
    virtual ~binaryTree() {}
    virtual bool empty() const = 0;
    virtual int size() const = 0;
//    virtual void preOrder(void (*)(T*)) = 0;
    virtual void inOrder(void (*)(T*)) = 0;
    virtual void postOrder(void (*)(T*)) = 0;
//    virtual void levelOrder(void (*)(T*)) = 0;
};
#endif //_24THREADED_BINARYTREE_BINARYTREE_H

inThreadedBinaryTreeNode.h

/*
Project name :			_24Threaded_BinaryTree
Last modified Date:		2023年11月28日17点06分
Last Version:			V1.0
Descriptions:			线索二叉树节点结构体
*/

#ifndef _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
#define _24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H
template<class T>
struct inThreadedBinaryTreeNode
{
    T element;
    inThreadedBinaryTreeNode<T>* leftChild,//左子树
    *rightChild;//右子树
    bool LTag, RTag;// 左右子树指针是否为索引，为True则是索引，否则不是索引
    /*默认构造函数*/
    inThreadedBinaryTreeNode() { leftChild = rightChild = nullptr; LTag = RTag = false;}
    /*只初始化element*/
    inThreadedBinaryTreeNode(T melement)
    {
        element = melement;
        leftChild = rightChild = nullptr;
        LTag = RTag = false;
    }
    /*三个元素都初始化*/
    inThreadedBinaryTreeNode(T melement, inThreadedBinaryTreeNode<T>* mleftChild, inThreadedBinaryTreeNode<T>* mrightChild)
    {
        element = melement;
        leftChild = mleftChild;
        rightChild = mrightChild;
        LTag = RTag = false;
    }
};
#endif //_24THREADED_BINARYTREE_INTHREADEDBINARYTREENODE_H

测试

"C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C++\_24Threaded BinaryTree\cmake-build-debug\_24Threaded_BinaryTree.exe"

******************************inThreadedBinaryTreeChains()函数开始**********************************

测试成员函数*******************************************
输入****************************
默认构造函数********************
Please enter the tree element:1
Please enter the tree element:2
Please enter the tree element:999
Please enter the tree element:999
Please enter the tree element:3
Please enter the tree element:999
Please enter the tree element:999
输出****************************
中序输出************************
a.inOrderOutput() = 2 1 3
后序输出************************
a.postOrderOutput() = 2 3 1
empty()*************************
a.empty() = 0
size()**************************
a.size() = 3
erase()**************************
a.inOrderOutput() =
******************************inThreadedBinaryTreeChains()函数结束**********************************

Process finished with exit code 0

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

分享一套MES源码，可以直接拿来搞钱的好项目

分享一套MES源码，可以直接拿来搞钱的好项目

目前国内智能制造如火如荼&#xff0c;工厂信息化、数字化是大趋势。如果找到一个工厂&#xff0c;搞定一个老板&#xff0c;搞软件的朋友就能吃几年。 中国制造业发达&#xff0c;工厂林立&#xff0c;但是普遍效率不高&#xff0c;需要信息化提高效率。但是矛盾的地方在于&a…
阅读更多...
pdf文件能扫码查看吗？一键做文本二维码

pdf文件能扫码查看吗？一键做文本二维码

pdf格式是常用的一种文件格式&#xff0c;很多资料、展示性的内容都会选择这种格式&#xff0c;现在很多人都需要将文件生成二维码图片后分享给他人&#xff0c;那么文件存入二维码展示的方法有哪些呢&#xff1f;下面给大家分享一招使用二维码生成器来生成二维码图片的操作方法…
阅读更多...
skywalking告警UI界面有告警信息，webhook接口没有回调，400错误

skywalking告警UI界面有告警信息，webhook接口没有回调，400错误

400错误就是回调接口返回数据的属性对应不上 PostMapping(“/webhook”) public void webhook(RequestBody List alarmMessageList) 自定义的实体类AlarmMessage有问题 只能去官网找了 告警实体类官网 Getter EqualsAndHashCode RequiredArgsConstructor NoArgsConstructor(fo…
阅读更多...
系列二十一、Spring中bean的创建顺序

系列二十一、Spring中bean的创建顺序

一、概述 我们知道启动IOC容器时&#xff0c;Spring会为我们创建各种各样的bean&#xff0c;那么思考一个问题&#xff0c;bean的创建顺序是由什么决定的呢&#xff1f;答&#xff1a;bean的创建顺序是由BeanDefinition的注册信息决定的&#xff0c;这个其实很好理解&#xff0…
阅读更多...
解析d3dcompiler_47.dll缺失怎么修复，4种方法修复d3dcompiler_47.dll文件

解析d3dcompiler_47.dll缺失怎么修复，4种方法修复d3dcompiler_47.dll文件

d3dcompiler_47.dll缺失怎么修复&#xff1f;其实在我们使用计算机操作的过程中&#xff0c;有时会遇到一些由dll文件错误导致的问题&#xff0c;其中d3dcompiler_47.dll丢失就是这样一种。那么究竟d3dcompiler_47.dll缺失是什么意思&#xff0c;为何它会发生丢失&#xff0c;以…
阅读更多...
Unity WebGL通过URL的形式接收参数执行初始化

Unity WebGL通过URL的形式接收参数执行初始化

参考博客&#xff1a; http://t.csdnimg.cn/QnfhK 问题背景&#xff1a; 需要在外面的网页指定WebGL的打开初始化逻辑。 步骤&#xff1a; 1.配置jslib&#xff0c;用文本文件创建即可&#xff0c;"__Internal.jslib"。 2.加入一段代码&#xff1a; mergeInto(…
阅读更多...
2023-简单点-机器学习中常用的特殊函数，激活函数[sigmoid tanh ]

2023-简单点-机器学习中常用的特殊函数，激活函数[sigmoid tanh ]

机器学习中的特殊函数 Sigmoidsoftplus函数tanhReLu(x)Leaky-ReluELUSiLu/ SwishMish伽玛函数beta函数Ref Sigmoid 值域: 【0,1】 定义域&#xff1a;【负无穷,正无穷】 特殊点记忆&#xff1a; 经过 [0 , 0.5] 关键点[0,0.5]处的导数是 0.025 相关导数&#xff1a; softplu…
阅读更多...
鹅厂终于开始收割韭菜了！！！获取手机号需要收费 ，吃相难看~

鹅厂终于开始收割韭菜了！！！获取手机号需要收费 ，吃相难看~

微信于2023年8月26日起对手机号验证能力收费&#xff0c;在规则生效时会给予每个小程序1000次免费验证&#xff0c;超出次数则需要到微信小程序官方后台进行充值&#xff0c;费用由微信官方收取。 这一做法&#xff0c;现在让越来越多的老板很头疼了&#xff0c; 如果你要修…
阅读更多...
ArkUI开发进阶—@Builder函数@BuilderParam装饰器的妙用与场景应用【鸿蒙专栏-05】

ArkUI开发进阶—@Builder函数@BuilderParam装饰器的妙用与场景应用【鸿蒙专栏-05】

ArkUI开发进阶—@Builder函数@BuilderParam装饰器的妙用与场景应用 HarmonyOS，作为一款全场景分布式操作系统，为了推动更广泛的应用开发，采用了一种先进而灵活的编程语言——ArkTS。ArkTS是在TypeScript（TS）的基础上发展而来，为HarmonyOS提供了丰富的应用开发工具，使开…
阅读更多...
ELK高级搜索，深度详解ElasticStack技术栈-上篇

ELK高级搜索，深度详解ElasticStack技术栈-上篇

前言 1、黑马视频地址&#xff1a;java中级教程-ELK高级搜索&#xff0c;深度详解ElasticStack技术栈 2、本内容仅用于个人学习笔记&#xff0c;如有侵扰&#xff0c;联系删除 1. 课程简介 1.1 课程内容 ELK是包含但不限于Elasticsearch&#xff08;简称es&#xff09;、Lo…
阅读更多...
嵌入式常见协议---IIC协议

嵌入式常见协议---IIC协议

1.IIC&#xff08;IC&#xff09;协议是什么&#xff1f; 全称 Inter-Integrated Circuit ,字面意思是集成电路之间&#xff0c;是IC BUS简称&#xff0c;中文应该叫集成电路总线&#xff0c;是一种串行通信总线&#xff08;同步串行半双工&#xff09;&#xff0c;使用多主从…
阅读更多...
配置 Mantis 在 Windows 上的步骤

配置 Mantis 在 Windows 上的步骤

配置 Mantis Bug Tracker 在 Windows 上的步骤 Mantis Bug Tracker 是一款开源的缺陷跟踪系统&#xff0c;用于管理软件开发中的问题和缺陷。在 Windows 环境下配置 Mantis 可以帮助开发者更方便地进行项目管理。以下是一个详细的教程&#xff0c;包含了 EasyPHP Devserver 和…
阅读更多...
app上架一直显示审核中状态要怎么处理？

app上架一直显示审核中状态要怎么处理？

当你提交一个应用到App Store上时&#xff0c;它会经历一个审核过程。在这个过程中&#xff0c;苹果的审核人员会检查你的应用是否符合苹果的规定和标准。这个过程通常需要几天的时间&#xff0c;但是如果你的应用一直显示“审核中”状态&#xff0c;那么可能会有一些原因。 1…
阅读更多...
如何使用Cloudreve将个人电脑打造为私有云盘并实现远程访问

如何使用Cloudreve将个人电脑打造为私有云盘并实现远程访问

文章目录 1、前言2、本地网站搭建2.1 环境使用2.2 支持组件选择2.3 网页安装2.4 测试和使用2.5 问题解决 3、本地网页发布3.1 cpolar云端设置3.2 cpolar本地设置 4、公网访问测试5、结语 1、前言 云存储概念兴起后&#xff0c;现在市面上也已经有了很多公有云盘。但一段时间后…
阅读更多...
为什么国密SSL证书越来越受市场青睐

为什么国密SSL证书越来越受市场青睐

随着信息技术的迅猛发展&#xff0c;网络安全问题备受关注。在这个背景下&#xff0c;越来越多的单位纷纷选择国密SSL证书&#xff0c;以构建更为安全可靠的网络环境。那么&#xff0c;为什么这么多单位选择国密SSL证书呢&#xff1f; 1&#xff0c;国家政策支持 近年来&#…
阅读更多...
有哪些不错的golang开源项目？

有哪些不错的golang开源项目？

前言 下面是github上的golang项目&#xff0c;适合练手&#xff0c;可以自己选择一些项目去练习&#xff0c;整理不易&#xff0c;希望能多多点赞收藏一下&#xff01;废话少说&#xff0c;我们直接进入正题>>> 先推荐几个教程性质的项目&#xff08;用于新手学习、…
阅读更多...
拼多多Temu销量大涨，三个月销量冲上热搜，Temu狂飙既要又要合规性证书

拼多多Temu销量大涨，三个月销量冲上热搜，Temu狂飙既要又要合规性证书

电商巨头拼多多野心之大&#xff0c;大到国内市场装不下。于是乎&#xff0c;跨境业务Temu于2022年下半年在美国上线2023年随着销量的不断狂飙&#xff0c;Temu平台对质量也是提出了卖家证明产品质量过关的合规性证书&#xff01; Temu在 8月的单日GMV达5000万美金&#xff0c…
阅读更多...
锐捷：下一代防火墙修改密码

锐捷：下一代防火墙修改密码

一、背景 刚接到的任务&#xff0c;锐捷行业的一台下一代防火墙的管理密码和管理地址都忘记了&#xff0c;并且命令登陆也设置了密码&#xff0c;只能通过重置的方式来进行管理&#xff0c;配置了。 本案例是一台RG-WALL 1600-S3200。 二、配置思路 1、准备环境 2、收集设备软…
阅读更多...
智能测径仪从这五大方面提升了性能

智能测径仪从这五大方面提升了性能

在测径仪的研发升级中&#xff0c;蓝鹏测控从未停下脚步&#xff0c;研究新的技术&#xff0c;让测径仪更好的为产线服务的功能。目前提供两种类型的在线测径仪&#xff0c;普通测径仪与智能测径仪&#xff0c;智能型主要在这五大方面进行了性能提升。 1、自动化程度 智能测径…
阅读更多...
淘宝API接口系列：连接商户与消费者的桥梁

淘宝API接口系列：连接商户与消费者的桥梁

一、引言 淘宝&#xff0c;作为中国最大的电商平台之一&#xff0c;拥有数以亿计的注册用户和海量的商品信息。淘宝API接口作为连接商户与消费者的重要桥梁&#xff0c;为开发者提供了丰富的电商资源&#xff0c;帮助他们创新和优化业务。本文将深入探讨淘宝API接口的相关知识…
阅读更多...
最新文章

Copyright @ 2022~2023