数据结构与算法学习笔记(7) 树

前情回顾

文章目录

• 数据结构与算法学习笔记(7) 树
• • 一.树和二叉树的定义
  • • 1.树
    • • 树的定义
      • 树的基本术语
      • 树结构与线性结构比较
    • 2.二叉树
    • • 二叉树的定义
      • 二叉树与树的差别
      • 二叉树基本形态
    • 3.树和二叉树的抽象数据类型定义
  • 二.二叉树的性质与存储结构
  • • 1.二叉树的性质
    • • ①二叉树性质1、2、3
      • ②两种特殊形式的二叉树:满二叉树和完全二叉树
      • • 定义与特点
        • 两者关系
      • ③二叉树的性质4、5(完全二叉树的两个性质)
    • 2.二叉树的存储结构
    • • ①顺序存储
      • ②链式存储
      • • 二叉链表
        • 三叉链表
  • 三.遍历二叉树和线索二叉树
  • • 1.遍历方法概述
    • • • 先序遍历二叉树的操作定义
        • 中序遍历二叉树的操作定义
        • 后序遍历二叉树的操作定义
        • 例
    • 2.根据遍历序列确定二叉树
    • 3.二叉树的遍历方法实现
    • • 先序遍历递归算法
      • 中序遍历递归算法
      • 后序遍历递归算法
      • 三种递归遍历算法的比较分析
      • 中序遍历非递归算法
      • 二叉树的层次遍历算法
    • 4.二叉树遍历算法的应用
    • • 建立二叉树的算法
      • • 按先序遍历序列建立二叉树的二叉链表
      • 复制二叉树
      • 计算二叉树的深度
      • 计算二叉树结点总数
      • 计算二叉树叶子结点数
    • 5.线索二叉树
    • • 线索二叉树的存储
      • • 先序线索二叉树
        • 中序线索二叉树
        • 后序线索二叉树
      • 增设头结点
  • 四.树和森林
  • • 1.树的存储结构
    • • 双亲表示法
      • 孩子链表
      • 孩子兄弟表示法(二叉树表示法、二叉链表表示法)
    • 2.树与二叉树的转换
    • • 树转为二叉树
      • 二叉树转为树
    • 3，森林与二叉树的转换(二叉树与多棵树之间的关系)
    • • 森林转二叉树
      • 二叉树转为森林
    • 4.树与森林的遍历
    • • 树的遍历(三种方式)
      • 森林的遍历
  • 五.哈夫曼树
  • • 1.引入
    • 2.基本概念
    • • • 路径、路径长度、权
        • 哈夫曼树
        • • 哈夫曼树特点
    • 3.哈夫曼树的构造算法
    • • 哈夫曼算法(构造哈夫曼树的方法)
      • • 哈夫曼算法特点
        • 哈夫曼树构造算法的实现
      • 哈夫曼树的应用--哈夫曼编码
      • • 哈夫曼编码的性质
        • 哈夫曼编码的算法实现
    • 4.哈夫曼树的应用
    • • 文件的编码和解码
      • • 编码
        • 解码
  • 七.部分代码实现
  • • • 补充复习：C++模板、STL
      • • 插曲：心态炸裂
    • 树与二叉树的链式实现(C++)
    • • 构造树
      • 遍历树

一.树和二叉树的定义

1.树

树的定义

递归嵌套定义

• 树的其他表示方式

  

就有点像这个markdown语法:

• A
• B
  • E
    • K
    • L
  • F
• C
  • G
• D
  • H
    • M
  • I
  • J

树的基本术语

结点的度，也是分支个数，也是后继个数

• 

  • 有序树：树中结点的各子树从左至右有次序(最左边为第一个孩子)

  • 无序树：树中结点的各子树无次序

  • 森林：是m(m≥0)棵互不相交的树的集合

    树变森林：

    

    

树结构与线性结构比较

2.二叉树

二叉树的定义

二叉树与树的差别

二叉树与树是两个概念，二叉树不是树的特殊情况

• 例

  

• 虽然是两个概念，但是有关树的基本术语对二叉树都适用

二叉树基本形态

3.树和二叉树的抽象数据类型定义

树：

• 主要学习二叉树的抽象数据类型定义

  

  • 基本操作很多，下为几个主要的：

    

二.二叉树的性质与存储结构

1.二叉树的性质

①二叉树性质1、2、3

• 每层结点个数

  

  • 第i层上至少有1个结点

• 总共结点个数

  

• 叶子数与度为2的结点数的关系

  

  n表示结点总个数

  n 1 n_1 n1​表示度为1的结点