算法笔记：二叉树

1 基本二叉树

• 二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为“左子节点”和“右子节点”。
  • 二叉树的根是唯一没有父节点的节点，而所有其他节点都有一个父节点和零个或两个子节点。

1.1 基础术语

• 节点（Node）: 二叉树的基本单位。每个节点都有一个关键字（或称为“键值”或“数据”）。
• 根节点（Root Node）: 没有父节点的节点。
• 叶节点（Leaf Node）: 没有子节点的节点。
• 子树（Subtree）: 任何节点都可以视为其下的所有节点组成的一个新树。
• 深度（Depth）: 从根节点到某一节点的简单路径上的边数。
• d层（Level）: 树中所有深度为d的节点的集合。

1.2 二叉树的遍历

以如下二叉树为例

1.2.1 前序遍历

 先访问根节点，然后访问左子树，再访问右子树

ABDHIEJCFKG

1.2.1.1 非递归实现

1.2.2 中序遍历 

先访问左子树，再访问根节点，最后访问右子树

HDIBEJAFKCG

1.2.2.1 非递归实现

1.2.3 后序排列

 先访问左子树，再访问右子树，最后访问根节点

HIDJEBKFGCA

1.2.3.1 非递归实现

注：下面我实现了一种两步进栈法，不知道是对的还是不对的（输出的结果是一样的）

1.2.4 层次遍历

逐层的从根节点开始，每层从左至右遍历

ABCDEFGHIJK

1.2.5 前序+中序，唯一确定一棵二叉树

• 同理，由二叉树的后序序列和中序序列同样可以唯一地确定一棵二叉树
• 但是，已知二叉树的前序遍历序列和后序遍历序列却无法确定一棵二叉树。
  • 比如：已知一棵二叉树的前序遍历序列为A、B，后序遍历序列为B、A
  • 我们虽然可以很容易地得知结点A为根结点，但是无法确定结点B是结点A的左儿子还是右儿子，因为B无论是结点A的右儿子还是左儿子都是符合已知条件的。

1.3 二叉树的性质

1.3.1 每一层最多多少个节点

一棵非空二叉树的第 i 层上最多有个结点（i≥1）

1.3.2 每一棵树最多多少个节点

一棵高度为k的二叉树，最多具有个结点

1.3.3 叶子节点数量和度数为2的节点数量

对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:  n0＝n2＋1 成立。

1.3.4 具有n个节点的完全二叉树的高度

1.4 二叉树的实现

1.4.1 顺序存储

1.4.1.1 完全二叉树的顺序存储

1.4.1.2 普通二叉树的顺序存储

1.4.1.3 顺序存储的特点

• 存储空间的浪费。
• 一般只用于一些特殊的场合，如静态的、并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。

1.4.2 链式存储

1.4.2.1 标准形式举例

1.4.2.2 广义标准形式举例

2 斜二叉树

只有左子节点或只有右子节点的二叉树称为斜二叉树

3 满二叉树

所有的分支要么左右子节点都有，要么没有子节点，且所有叶子结点都在同一层上

4 完全二叉树

除了最后一层外，每一层都是完全填满的，并且所有节点都尽量向左填充

另一种说法：在满二叉树的最底层自右至左依次(注意：不能跳过任何一个结点)去掉若干个结点得到的二叉树

完全二叉树特点：

• 叶子结点只能出现在最下两层；
• 最下层的叶子结点一定集中在左边并且连续；
• 若结点度为1，则该节点只有左子节点；
• 完全二叉树的深度为 (n是树中节点的数量）
• 在高度为h的完全二叉树中，节点数最少为，最多为
• 对于个索引为i的点（索引从1开始计数）
  • 父节点（若存在）的索引是
  • 左子节点（若存在）的索引是2i
  • 右子节点（若存在）的索引是2i+1
• 对任一结点，如果其右子树的高度为k，则其左子树的高度为k或k＋1

满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树

5 线索二叉树

• 线索二叉树是一种对二叉树的改进，旨在通过线索（也就是额外的指针）加速对树的遍历操作
• 在普通的二叉树中，每个节点有两个子节点：左子节点和右子节点。但有些节点的子节点可能为空，这些空指针字段不存储任何信息
  • 
• 线索二叉树通过利用这些空指针字段来存储与当前节点在某种遍历顺序（如前序、中序或后序）下相邻的节点。
  • 这样，在遍历树时，就不需要使用栈或递归，从而提高了遍历的速度
• 在线索二叉树中，每个节点有两个额外的标志位，分别表示左指针和右指针是否被用作线索
  • 如果左子节点为空，则左指针字段存储该节点在某种遍历顺序下的前驱节点
  • 如果右子节点为空，则右指针字段存储该节点在某种遍历顺序下的后继节点
• 

5.1 创建线索二叉树

创建线索二叉树通常需要两次遍历：

1. 第一次遍历是普通的前序、中序或后序遍历，用于建立二叉树的基本结构。
2. 第二次遍历用于添加线索。这通常通过保存前一个访问的节点并在访问下一个节点时更新其线索来完成。

5.2 优缺点

优点：

• 遍历更快：由于已经存储了前驱和后继信息，遍历操作更加高效。
• 不需要额外的数据结构：不需要使用栈或递归。

缺点：

• 额外的存储开销：需要额外的字段来存储线索和标志位。
• 修改复杂：插入或删除节点时，需要更新相应的线索，这使得操作更加复杂。、

参考内容：数据结构与算法（八）-二叉树（斜二叉树、满二叉树、完全二叉树、线索二叉树）-腾讯云开发者社区-腾讯云 (tencent.com)OO