基础概念
定义：一种特殊的树结构，每个节点最多有两个子节点，称为左子节点和右子节点
例子： 想象一颗圣诞树，每个节点最多有两个分支，分别代表左子节点和右子节点
特点：
- 节点最多有两个子节点: 每个节点最多有两个子节点，左子节点和右子节点
- 根节点: 二叉树只有一个根节点，它是树的起点
- 层级结构: 二叉树可以被分为不同的层级，从根节点开始，依次向下
基本操作
- 插入 (Insert): 在二叉树中插入新节点需要找到合适的位置，并更新指针关系，保证二叉树的性质
- 删除 (Delete): 从二叉树中删除节点需要找到该节点，并更新指针关系，保证二叉树的性质
- 查找 (Search): 在二叉树中查找特定节点需要从根节点开始，依次向下比较节点数据，直到找到目标节点
应用场景
- 排序算法: 二叉树可以用来实现排序算法，例如堆排序
- 数据存储: 二叉树可以用来存储数据，例如数据库索引
- 表达式树: 二叉树可以用来表示数学表达式
二叉树的遍历
二叉树的遍历方式有三种，根据根节点出现的顺序区分
此外还可以按照每一层的方式遍历，层序遍历