线索二叉树-c++实现

标签: 算法总结  二叉树

基本思想

1.根据用户输入创建二叉树(一般用前序遍历)
2.线索化二叉树(一般用中序遍历线索化)(此时要把head节点加进来)
3.通过输出中序遍历结果来检验线索化是否正确

详细注释在代码中,可以先看main函数中的流程,再看具体函数实现

实验中采用的二叉树如图

在这里插入图片描述

完整代码

#include <iostream>

/**通过枚举类型,child = 0, thread = 1,来表示树中的节点指向的是正常的孩子,还是用来指引线索*/
typedef enum{child, thread} PointTag;

/**创建线索二叉树的结点*/
struct ThBiTreeNode{
    char m_nValue;
    ThBiTreeNode* m_pLeft;
    PointTag m_pLeftTag;
    ThBiTreeNode* m_pRight;
    PointTag m_pRightTag;
};

/**在创建时需要加进去的head*/
ThBiTreeNode* pre;


/**通过前序遍历来构造一个树*/
void CreateBiTree(ThBiTreeNode* &T){
    char c;
    scanf("%c", &c);

    if(c == ' '){
        T = NULL;
    }
    else{
        T = new(ThBiTreeNode);
        T->m_nValue = c;
        T->m_pLeftTag = child;
        T->m_pRightTag = child;
        CreateBiTree(T->m_pLeft);
        CreateBiTree(T->m_pRight);
    }
}


/**构建线索树(填装线索)*/
void InThred(ThBiTreeNode* &T){
    if(T){
        InThred(T->m_pLeft);

        /**左子树为空,改变tag,并指向它的前驱*/
        if(!(T->m_pLeft)){
            T->m_pLeftTag = thread;
            T->m_pLeft = pre;
        }

        /**此次遍历到了B,B在序列中前一个节点为A,如果A没有右节点,那么久把B作为A的后继*/
        if(!(pre->m_pRight)){
            pre->m_pRightTag = thread;
            pre->m_pRight = T;
        }

        /**本次的结点处理完之后,就成为了下一次处理节点的上一个节点*/
        pre = T;

        InThred(T->m_pRight);
    }
}

/**构建线索数(增加head节点),最后把序列最后一个数和head节点的右节点建立线索*/
void InOrderThreadBiTree(ThBiTreeNode* &head, ThBiTreeNode* &T){
    /**先把head节点放进来,判断T是否为空树的话,在添加线索的时候做,T为空树,我head照样可以连接*/
    head = new(ThBiTreeNode);
    head->m_nValue = NULL;
    head->m_pLeftTag = child;
    head->m_pRightTag = thread;

    /**如果传进来的树是一个空树,那么head节点的左子节点指向自己*/
    if(!T){
        head->m_pLeft = head;
    }
    else{
        head->m_pLeft = T;
        pre = head;
        InThred(T);
        /**是在所有都线索化完成之后,才把序列的最后一个的右线索,连接在head节点上*/
        /**在完成上面的线索建立后,pre是指向中序遍历的最后一个元素的,就是树中最右边的元素*/
        pre->m_pRightTag = thread;
        pre->m_pRight = head;
        /**把head的右线索连接在序列最后一个*/
        head->m_pRight = pre;
    } 
}


void vist(ThBiTreeNode* T){
    std::cout << T->m_nValue << std::endl; 
}

/**中序遍历打印二叉树*/
void InorderTraverse(ThBiTreeNode* T){

    ThBiTreeNode* temp;
    /**现在这个temp指向的就是加入了head节点之后树的根节点(不是head)*/
    temp = T->m_pLeft;

    /**如过指向左孩子的指针,和指向根节点的指针是同一个的时候*/
	/**表示这个树要么是空树,要么是遍历结束的时候*/
    while(temp != T){
        while(temp->m_pLeftTag == child){
            temp = temp->m_pLeft;
        }
        vist(temp);

        /**p-rchild != T,就表示这个点不是指向你加入的那个head节点,就表明,现在这个遍历的结点是有真正的后继的*/
        while(temp->m_pRightTag == thread && temp->m_pRight != T){
            /**这个时候,树已经线索化完成了,p的右孩子现在指向的是它序列中的后继*/
            temp = temp->m_pRight;
            vist(temp);
        }
        temp = temp->m_pRight;
    }
}

int main(){
    /**原始树*/
    ThBiTreeNode* T;

    /**加了头的树*/
    ThBiTreeNode* T_head;

    /**根据输入创建基本二叉树*/
    CreateBiTree(T);

    /**把head节点加进去,并且建立线索*/
    InOrderThreadBiTree(T_head, T);

    /**中序遍历带有head的树*/
    InorderTraverse(T_head);

    system("pause");
    return 0;
}

运行结果如图所示

在这里插入图片描述

版权声明:本文为qq_39998712原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39998712/article/details/108625567

智能推荐

PoolThreadCache

缓存构成   PoolThreadCache的缓存由三部分构成:tiny、small 和 normal。 tiny   缓存数据大小区间为[16B, 496B]数据,数组长度为32,根据数据大小计算索引的办法:数据大小除以16,如下代码所示: small   缓存数据大小区间为[512B, 4KB]数据,数组长度为4,根据数据大小计算索引的办法:数据大小除以512,然后log2得到指数,如下代码所...

Intellij IDEA 搭建Spring Boot项目(一)

Intellij IDEA 搭建Spring Boot项目 标签(空格分隔): SpringBoot JAVA后台 第一步 选择File –> New –> Project –>Spring Initialer –> 点击Next  第二步 自己修改 Group 和 Artif...

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

猜你喜欢

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...