线索二叉树讲解
发布日期:2021-06-29 14:17:47
浏览次数:3
分类:技术文章
本文共 941 字,大约阅读时间需要 3 分钟。
前言
这是我听老师讲课做的笔记。
作者:RodmaChen 关注我的,更多数据结构与算法知识还在更新
目录
线索二叉树
LTag
和RTag
表示的就是标志,当LTag
等于0
,那么lchild
的指针域就指向左孩子,如果等于1
,就说明没有孩子,就放他的前驱(前驱就是他的父节点,后继就是遍历序列后一个数)。
相关的概念和定义
- 线索:指向结点前驱和后继的指针,叫做线索。
- 线索链表: 以这种结点结构(上图,五个域)构成的二叉链表作为二叉树的存储结构,叫做线索链表。
- 线索二叉树(Threaded Binary Tree) :加上线索的二叉 树称之为线索二叉树。
- 线索化:对二叉树以某种次序遍历使其变为线索二叉 树的过程叫做线索化。
边学边练
(1)画出图(a)的先序、中序、后序线索化
解题思路:先写遍历序列在画图
解题答案:先序序列:ABDCEFGHI
中序序列:DBAFECHGI 后序序列:DBFEHIGCA 画图:其中实线为指针(指向左、右子树),虚线为线索(指向前驱和后继)。
(2)已知一棵完全二叉树的第6层(设根为第1层)有8个叶结
点,则该完全二叉树的结点个数最多是(c)考研题难度 A.39 B.52 C.111 D.119这道题有两个坑:
第一个:他不只有六层
第二个:并没有说第六层只有八个结点
解题思路:
1.第6层最多的结点是2^5
,由于有8
个叶子结点,所以还有24
个结点是空的或者是存在的。 2.由于要有最多的结点,则说明还有第7层(叶子结点是最后一个),第7层结点数是24x2
个,所以最多有 2^6-1+24x2
(3)对于前序遍历与中序遍历结果相同的二叉树为(F); 对于前序遍历和后序遍历结果相同的二叉树为(B)。
A.一般二叉树 B.只有根结点的二叉 C.根结点无左孩子的二叉树 D.根结点无右孩子的二叉树 E.所有结点只有左子数的二叉树 F.所有结点只有右子树的二叉树N0R
0NR NLR LRN
(4) 一棵左子树为空的二叉树在先序线索化后,其中
空的链域的个数是:( ) A.不确定 B. 0 C. 1 D. 2 思路:前驱后继总结
本人博客:
本人b站求关注: 转载说明:跟我说明,务必注明来源,附带本人博客连接。
请给我点个赞鼓励我吧
转载地址:https://chenyunzhi.blog.csdn.net/article/details/106291553 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月21日 01时54分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
自我学习37:请描述一下网页从开始请求到最后展示的完整过程
2019-04-29
自我学习38:如何区分前后端BUG
2019-04-29
自我学习39:接口自动化测试用例&功能测试用例区别
2019-04-29
mirror去兔子补丁下载 附安装教程
2019-04-29
mirror去兔子补丁 v3.0附安装教程
2019-04-29
mirror去兔子补丁为什么还有兔子_mirror去兔子补丁使用教程
2019-04-29
3dmax2012安装教程
2019-04-29
OC渲染器(Octane Render)整合版安装包 附安装教程
2019-04-29
操作系统期末大题复习
2019-04-29
hive:分区表,hbase外表
2019-04-29
想要成为运维,想要成为后期的架构师?这些知识是必备的!
2019-04-29
linux 是如何 快速一键安装禅道的呐?
2019-04-29
运维面试基础试题(四)
2019-04-29
一键安装Openstack单节点 必能成功
2019-04-29
面试紧张怎么办
2019-04-29
关系型数据库 ,nosql数据库简介
2019-04-29
Centos 7搭建NTP时间同步服务器
2019-04-29
centos7 基于rsync+inotify 实现定时备份
2019-04-29
指定IP进行 文件的分发
2019-04-29
基于http搭建本地yum仓库
2019-04-29