二叉树

1. 基本概念

• 定义：二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

• 节点：树的基本单元，包含数据和指向子节点的指针。

• 根节点：树的最上层节点，没有父节点。

• 叶子节点：没有子节点的节点。

2. 类型

• 完全二叉树：除了最后一层外，每一层都被完全填满，且最后一层的节点都集中在左侧。

• 满二叉树：每个节点都有两个子节点，且所有叶子节点都在同一层。

• 平衡二叉树：任何节点的两个子树的高度差不超过1。

• 二叉搜索树（BST 、 Binary Search Tree）：对于每个节点，左子树的所有节点值小于该节点，右子树的所有节点值大于该节点。

• 堆：（大顶堆、小顶堆）其实就是一个二叉树

3. 存储方式

顺序存储方式(数组) —— 完全二叉树、满二叉树

链式存储方式 —— 一般二叉树

4. 遍历方法

• 前序遍历（根-左-右）：首先访问根节点，然后遍历左子树，最后遍历右子树。

• 中序遍历（左-根-右）：首先遍历左子树，然后访问根节点，最后遍历右子树。

• 后序遍历（左-右-根）：首先遍历左子树，然后遍历右子树，最后访问根节点。

• 层序遍历：按层级逐层遍历，从上到下，从左到右。

5. 应用

• 表达式树：用于表示算术表达式。

• 搜索算法：二叉搜索树可用于高效查找。

• 优先队列：可以用堆实现，堆是一种特殊的二叉树。

• 数据压缩：如霍夫曼编码使用二叉树进行编码。

6. 基本操作

• 插入：在合适的位置插入新节点。

• 删除：根据节点的情况（叶子节点、有一个子节点或有两个子节点）进行不同的删除操作。

• 查找：在二叉搜索树中，可以利用其特性高效查找节点。