当前位置： 首页 > news >正文

数据结构——5.3 二叉树的遍历和线索二叉树

news 来源：原创 2024/5/20 2:41:32

第五章 树与二叉树

5.3 二叉树的遍历和线索二叉树

  • 概念

  1. 线索二叉树：为了快速得到遍历序列的前驱和后继

  • 理解

  1. 线索二叉树是一种物理结构，二叉树一种逻辑结构

  2. n个结点的线索二叉树具有2n个链域指针，除了根节点外，每个结点都被一个指针指向，因此用掉了n-1个指针，还剩下n+1个指针用作线索

  3. 指针指向的左右，若为0则是正常的子节点，若为1则为线索

  • 技巧

  1. 中序遍历二叉树的终点一定是最右边的叶子

  2. 后序遍历的出入栈能够体现根节点到某一结点的路径

  3. 二叉树的先序、中序、后序遍历中，所有叶节点的先后顺序是不变的

  4. 若先序与后序结果相反：

    1. 叶结点只有一个

    2. 每层只有一个结点

    3. 结点数等于高度

    4. 不可能存在一个结点同时有左右孩子

    5. 中序序列中根节点在序列首或序列尾；

    6. 次根结点（移除根节点后变成根节点的结点，即原根节点的孩子结点）在不含根节点的序列中也在序列首或序列尾

  5. 若先序与后序结果相同，则该二叉树只有一个根节点

  6. 先序和后序序列组合

    1. 不能确定二叉树，必须要有中序参与

    2. 可以确定结点间的祖先关系，如先序XY，后序YX则X为Y的双亲，例如：先序aebdc、后序bcdea，则根节点a的孩子只有e

  7. 后序线索树的遍历需要栈的支持

  8. 前序序列与中序序列组合可以表述唯一的二叉树

    1. 前序序列作为入栈的次序，中序序列作为出栈的次序

    2. 若已知入栈次序和入栈元素个数n，则出栈的序列个数有： 1 n + 1 C 2 n n \frac{1}{n + 1}C_{2n}^{n} n+11​C2nn​个，即可能的二叉树个数

  9. 如果想要二叉树先序序列和中序序列相同，则所有非叶节点必须只有右子树

相关文章：

  • leetcode142. 环形链表 II
  • 【RISC-V DSP设计】基于CEVA DSP架构的指令集分析（二）-函数列表
  • 边缘计算第二版施巍松——第七章 边缘计算资源调度
  • 基于Skywalking开发分布式监控（二）
  • Spring Security学习（四）——登陆认证（包括自定义登录页）
  • [日常使用] Shell常用命令
  • PHP+vue+mysql校园学生社团管理系统574cc
  • 【LeetCode】122. 买卖股票的最佳时机 II（中等）——代码随想录算法训练营Day32
  • react渲染流程是怎样的
  • reprod_log复现精度对比小工具
  • sql语句学习(二)--增删改
  • 算法训练营day24（补）,回溯4-2
  • Python爬虫 Beautiful Soup库详解#4
  • 5 scala的函数式编程简介
  • LeetCode.145. 二叉树的后序遍历
  • -------------------- 第二讲-------- 第一节------在此给出链表的基本操作
  • axios 和 cookie 的那些事
  • - C#编程大幅提高OUTLOOK的邮件搜索能力!
  • canvas 绘制双线技巧
  • canvas 五子棋游戏
  • CAP 一致性协议及应用解析
  • CentOS6 编译安装 redis-3.2.3
  • create-react-app项目添加less配置
  • ECMAScript 6 学习之路 （ 四 ） String 字符串扩展
  • javascript 哈希表
  • JavaScript设计模式系列一：工厂模式
  • Mocha测试初探
  • vagrant 添加本地 box 安装 laravel homestead
  • win10下安装mysql5.7
  • windows下mongoDB的环境配置
  • 不发不行！Netty集成文字图片聊天室外加TCP/IP软硬件通信
  • 彻底搞懂浏览器Event-loop
  • 发布国内首个无服务器容器服务，运维效率从未如此高效
  • 记一次删除Git记录中的大文件的过程
  • 浅谈Kotlin实战篇之自定义View图片圆角简单应用(一)
  • 如何设计一个比特币钱包服务
  • 使用Maven插件构建SpringBoot项目,生成Docker镜像push到DockerHub上
  • 问题之ssh中Host key verification failed的解决
  • 消息队列系列二（IOT中消息队列的应用）
  • - 语言经验 - 《c++的高性能内存管理库tcmalloc和jemalloc》
  • JavaScript 新语法详解：Class 的私有属性与私有方法 ...
  • 不要一棍子打翻所有黑盒模型，其实可以让它们发挥作用 ...
  • ​人工智能之父图灵诞辰纪念日，一起来看最受读者欢迎的AI技术好书
  • #includecmath
  • #我与虚拟机的故事#连载20：周志明虚拟机第 3 版：到底值不值得买？
  • $(function(){})与(function($){....})(jQuery)的区别
  • (2020)Java后端开发----（面试题和笔试题）
  • （day 2）JavaScript学习笔记（基础之变量、常量和注释）
  • （Mac上）使用Python进行matplotlib 画图时，中文显示不出来
  • （python）数据结构---字典
  • （小白学Java）Java简介和基本配置
  • （一）插入排序
  • (原创)攻击方式学习之(4) - 拒绝服务(DOS/DDOS/DRDOS)
  • （转）visual stdio 书签功能介绍
  • （转载）虚幻引擎3--【UnrealScript教程】章节一：20.location和rotation