二叉树

基础概念

定义：一种特殊的树结构，每个节点最多有两个子节点，称为左子节点和右子节点

例子：  想象一颗圣诞树，每个节点最多有两个分支，分别代表左子节点和右子节点

特点：

• 节点最多有两个子节点:  每个节点最多有两个子节点，左子节点和右子节点
• 根节点:  二叉树只有一个根节点，它是树的起点
• 层级结构:  二叉树可以被分为不同的层级，从根节点开始，依次向下

基本操作

• 插入 (Insert): 在二叉树中插入新节点需要找到合适的位置，并更新指针关系，保证二叉树的性质
• 删除 (Delete): 从二叉树中删除节点需要找到该节点，并更新指针关系，保证二叉树的性质
• 查找 (Search): 在二叉树中查找特定节点需要从根节点开始，依次向下比较节点数据，直到找到目标节点

应用场景

• 排序算法: 二叉树可以用来实现排序算法，例如堆排序
• 数据存储: 二叉树可以用来存储数据，例如数据库索引
• 表达式树:  二叉树可以用来表示数学表达式

二叉树的遍历

二叉树的遍历方式有三种，根据根节点出现的顺序区分

• 根节点 → 左子树 → 右子树：前序遍历
• 左子树 → 根节点 → 右子树：中序遍历
• 左子树 → 右子树 → 根节点：后序遍历

此外还可以按照每一层的方式遍历，层序遍历