数据结构与算法之二叉树(六)

目录

• 树形结构
• 树的基本概念
• 有序树，无序树，森林
• 二叉树介绍
• 其他二叉树

一 树形结构

二叉树.png 多叉树.png

生活中的二叉树

组织架构.png 项目结构.png

二 树(Tree)的基本概念

节点

• 节点，根节点，父节点，子节点，兄弟节点

• 一棵树可以没有任何节点，称为空树

• 一棵树可以只有一个节点，即只有根节点

• 子树，左子树，右子树

• 节点的度：子树的个树

• 树的度：所有节点度中的最大值

• 叶子节点：度为0的节点

• 非叶子节点：度不为0的节点

image.png

深度高度
层数(level)：根节点在第一层，根节点的子节点在第二层，以此类推。
节点的深度(depth)：从根节点到当前节点的唯一路径上的节点总数
节点的高度(height)：从当前节点到最远叶子节点的路径上的节点总数
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
树的深度等于树的高度

三 有序树，无序树，森林

有序树：树中任意节点的子节点之间有顺序关系
无序树：树中任意节点的子节点之间没有顺序关系，也称为自由树
森林：由m(m>=0)课互不相交的树组成的集合

四 二叉树

4.1 二叉树的特点

• 每个节点的度最大为2（最多拥有2棵子树）
• 左子树和右子树是有顺序的
• 即使某节点只有一棵子树，也要区分左右子树

image.png

4.2 二叉树的性质

1.非空二叉树的第i层，最多有 2^i-1个节点（i >= 1）
2.在高度为h的二叉树上，最多有2^h - 1 个节点（h >= 1）
3.对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有 n0 = n2 + 1

假设度为1的节点个数为n1，那么二叉树的节点总数为 n=n0 + n1 + n2
二叉树的边树 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
因此 n0 = n2 + 1

image.png

4.3 真二叉树(Proper Binary Tree)

真二叉树：所有节点的度都要么为0，要么为2

真二叉树.png

4.4 满二叉树(Full Binary Tree)

满二叉树：所有节点的度要么为0，要么为2，并且所有的叶子节点都在最后一层。

满二叉树.png

假设满二叉树的高度为h（h >= 1）

• 第i层的节点数量为 2^i-1
• 叶子节点数量为 2^h-1

假设总节点数量为n，则
n = 2 ^h - 1 = 2⁰ + 2¹ + ... + 2^h-1
h = log2^{(n + 1)}

• 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数最多
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

4.5 完全二叉树(Complete Binary Tree)

完全二叉树：叶子节点只会出现最后2层，并且最后一层的叶子节点都靠左对对齐

完全二叉树.png

• 完全二叉树从根节点至倒数第二层是一颗满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

4.5.1 完全二叉树的性质

• 度为1的节点只有左子树
• 度为1的节点，要么是1个，要么是0个
• 同样节点数量的二叉树，完全二叉树的高度最小

假设完全二叉树的高度为h（h >= 1），那么

• 至少有2^h-1个节点（2⁰ + 2¹ + ... + 2^h-2 + 1）
• 最多有2^h - 1个节点，（2⁰ + 2¹ + ... + 2^h-1，满二叉树）
• 假设总节点数量为n，则
  • 2^h-1 <= n < 2^h
  • h - 1 <= log2ⁿ < h
  • h = floor(log2ⁿ) + 1
  • floor是向下取整，ceiling是向上取整意思

4.5.2 完全二叉树的性质

一棵有n个节点的完全二叉树(n > 0)，从上到下，从左到右，对节点从1开始编号，对任意第i个节点

• 如果 i = 1，它是根节点
• 如果 i > 1，它的父节点编号为floor(i / 2)
• 如果 2i <= n，它的左子节点编号为2i
• 如果 2i > n，它无左子节点
• 如果 2i + 1 <= n，它的右子节点编号为2i + 1
• 如果 2i + 1 > n，它无右子节点

完全二叉树.png

五 其他二叉树

完满二叉树: 所有非叶子节点的度都为2
完美二叉树:所有非叶子节点的度都为2，并且所有的叶子节点都在最后一层
完全二叉树:所有节点的度要么为0，要么为2，并且所有的叶子节点都在最后一层。

---

本文会持续更新中，更多精彩内容敬请期待。

---

本文参考 MJ老师的 恋上数据结构与算法

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。