算法笔记：二叉树

1 基本二叉树

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

1.1 基础术语

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

1.2 二叉树的遍历

以如下二叉树为例

1.2.1 前序遍历

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

ABDHIEJCFKG

1.2.2 中序遍历 

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

HDIBEJAFKCG

1.2.3 后序排列

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

HIDJEBKFGCA

1.2.4 层次遍历

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

ABCDEFGHIJK

2 斜二叉树

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

3 满二叉树

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

4 完全二叉树

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

完全二叉树特点：

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

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

5 线索二叉树

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

5.1 创建线索二叉树

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

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

5.2 优缺点

优点：

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

缺点：

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

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