数据结构——线索化二叉树和哈夫曼树[通俗易懂]

数据结构——线索化二叉树和哈夫曼树[通俗易懂]线索化二叉树和哈夫曼树基础知识介绍与代码分析一、基础知识介绍二、代码分析:线索二叉树(采用中序遍历)#include “pch.h”#include <iostream>using namespace std;//定义线索二叉树typedef struct Tree{ int data, LTag, RTag; //定义数据域与标记域 Tre…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

线索化二叉树和哈夫曼树基础知识介绍与代码分析

一、基础知识介绍

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、代码分析:

线索二叉树(采用中序遍历)

#include "pch.h"
#include <iostream>
using namespace std;
//定义线索二叉树
typedef struct Tree
{ 

int data, LTag, RTag;	//定义数据域与标记域
Tree *lchild, *rchild;
}Tree,*Trees;
Trees pre = NULL;	//设置前驱线索
//初始化二叉树
void InitBitTree(Trees*boot)
{ 

*boot = (Trees)malloc(sizeof(Tree));
(*boot)->lchild = (*boot)->rchild = NULL;
(*boot)->LTag = (*boot)->RTag = 0;
}
//创建二叉树
void CreateBtTree(Trees &boot)
{ 

int num;
cout << "请输入数据:";
cin >> num;
if (num==0)
{ 

boot = NULL;
}
else
{ 

boot =(Trees) malloc(sizeof(Tree));
boot->data = num;
boot->lchild = boot->rchild = 0;
boot->LTag = boot->RTag = 0;
CreateBtTree(boot->lchild);
CreateBtTree(boot->rchild);
}
}
//添加线索
void InssertLineTree(Trees &boot)
{ 

if (boot!=NULL)
{ 

InssertLineTree(boot->lchild);//线索化左子树
if (boot->lchild==NULL)
{ 

boot->LTag = 1;
boot->lchild = pre;//设置前驱线索
}
if (pre!=NULL&&pre->rchild==NULL)
{ 

pre->rchild = boot ;
pre->RTag = 1;
}
//当前访问节点为下一个节点的前驱/
pre = boot;
//线索化右子树
InssertLineTree(boot->rchild);
}
}
//创建头结点
Trees InOrderThread(Trees &rt)
{ 

Trees throot;
if (!(throot = (Trees)malloc(sizeof(Tree))))
{ 

cout << "头结点创建失败!" << endl;
exit(0);
}
throot->LTag = 0;//左标记为0 指向左子树
throot->RTag = 1;//右标记为1 指向遍历的前驱
throot->rchild = throot;//右子树指向头结点本身
if (!throot)
{ 

//二叉树如果为空,左指针指向头结点本身
throot->lchild = throot;
}
else
{ 

throot->lchild = rt;
pre = throot;
//插入线索
InssertLineTree(rt);
pre->rchild = throot;
pre->RTag = 1;
throot->rchild = pre;
}
return throot;
}
//中序遍历查找前驱
void InPre(Trees boot)
{ 

Trees q = NULL;
if (boot->LTag==1)
{ 

pre = boot->lchild;
}
else
{ 

for (q=boot->lchild; q->RTag==0;q=q->rchild )
{ 

pre=q;
}
}
if (pre)
{ 

cout << "用中序遍历找到的前驱为:" << pre->data << endl;
}
else
{ 

cout << "用中序遍历无前驱:" << endl;
}
}
//中序遍历后序节点
void InNext(Trees boot)
{ 

Trees q = NULL;
if (boot->RTag == 1)
{ 

pre = boot->rchild;
}
else
{ 

for (q = boot->rchild; q->LTag == 0; q = q->lchild)
{ 

pre = q;
}
}
if (pre)
{ 

cout << "用中序遍历找到的后继为:" << pre->data << endl;
}
else
{ 

cout << "用中序遍历无后继:" << endl;
}
}
//中序遍历查找线索二叉树第一个节点
Trees InFirst(Trees boot)
{ 

Trees p = boot;
if (!p)
{ 

return 0;
}
while (p->LTag==0)
{ 

p = p->lchild;
}
return p;
//中序遍历左 根 右 二叉树左左端节
//二叉树的最左端的节点
}
//中序遍历线索二叉树
void TinOrder(Trees &throot)
{ 

Trees p;
p = throot->lchild;
while (p!=throot)
{ 

while (p->LTag==0)//有左子树
{ 

p = p->lchild;
}
cout<<p->data<<endl;
while (p->RTag==1&&p->rchild!=throot)
{ 

p = p->rchild;
cout << p->data << endl;
}
p = p->rchild;
}
cout << endl;
}
int main()
{ 

Trees boot = NULL;
cout << "创建线索二叉树,如果输入0结束:" << endl;
CreateBtTree(boot);
Trees throot;	//头结点
throot=InOrderThread(boot);
//进行遍历
TinOrder(throot);
InPre(boot);
InNext(boot);
Trees bt=InFirst(boot);
cout << "中序遍历线索二叉树的第一个节点为:" << bt->data << endl;
return 0;
}

结果为:

居中

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170981.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 开源协议均为什么协议_常见的计算机网络协议有哪些

    开源协议均为什么协议_常见的计算机网络协议有哪些一直对各种开源协议比较模糊,特意在网上搜索了一下资料,整理总结,以作记录如果不喜欢长篇大论的话,看下图就可以了基本概念了解:1.Contributors和RecipientsCon

  • win10如何永久关闭数字签名

    win10如何永久关闭数字签名1、如何永久关闭Win10驱动程序方法一:永久有效步骤如下:1、在开始按钮点击右键,选择“Windowspowershell(管理员)”2、执行以下命令(复制后,在命令提示符中单击鼠标右键即可完成粘贴,然后按回车键执行):bcdedit.exe/setnointegritycheckson3、命令瞬间执行完毕,若想恢复默认验证,执行如下命令即可:bcdedi…

  • navicat 15.02 激活码[在线序列号]

    navicat 15.02 激活码[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 入门级Unity安装教程

    入门级Unity安装教程这是一篇面向对unity感兴趣,想要学习unity,但是还处于入门阶段的小伙伴的超详细unity安装教程。因为是面向入门的小伙伴,所以文章写的有点长,还配有许多图片,这样才能更详细的介绍安装流程。但是不必担心太长看起来太费劲,各位只要照着教程一步步来就可以了。跟着这章博文走,最终你的电脑一定能张开双臂,成功拥抱unity。那么,现在进入正题吧!1.进入官网unity的官网链接:unity.cn…

  • verilog同步fifo_verilog 异步复位

    verilog同步fifo_verilog 异步复位写在前面在上篇文章:同步FIFO的两种Verilog设计方法(计数器法、高位扩展法)中我们介绍了FIFO的基本概念,并对同步FIFO的两种实现方法进行了仿真验证。而异步FIFO因为读写时钟不一致,显然无法直接套用同步FIFO的实现方法,所以在本文我们将用Verilog实现异步FIFO的设计。1、什么是异步FIFO异步FIFO有两个时钟信号,读和写接口分别采用不同时钟,这两个时钟可能时钟频率不同,也可能时钟相位不同,可能是同源时钟,也可能是不同源时钟。在现代…

  • python 两个list 求交集,并集,差集

    python 两个list 求交集,并集,差集在python中,数组可以用list来表示。如果有两个数组,分别要求交集,并集与差集,怎么实现比较方便呢?当然最容易想到的是对两个数组做循环,即写两个for循环来实现。这种写法大部分同学应该都会,而且也没有太多的技术含量,本博主就不解释了。这里给大家使用更为装bility的一些方法。老规矩,talkischeap,showmethecode#!/usr/bin/envpython#

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号