树

树是一种层级数据结构，由节点和边组成。它适合表示具有父子关系的数据。

常见场景：

• 文件目录；
• 组织架构；
• HTML DOM；
• 数据库索引；
• 表达式解析。

一、基本概念

概念	说明
根节点	树的起点
父节点	一个节点的上级
子节点	一个节点的下级
叶子节点	没有子节点的节点
深度	从根到该节点的路径长度
高度	从该节点到叶子的最长路径

二、二叉树

二叉树中每个节点最多有两个子节点，通常称为左孩子和右孩子。

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

三、遍历方式

遍历	顺序
前序遍历	根 -> 左 -> 右
中序遍历	左 -> 根 -> 右
后序遍历	左 -> 右 -> 根
层序遍历	按层从上到下

二叉搜索树的中序遍历结果是有序的。

四、二叉搜索树

二叉搜索树满足：

• 左子树所有节点小于根节点；
• 右子树所有节点大于根节点；
• 左右子树也都是二叉搜索树。

查找、插入、删除平均复杂度为 O(log n)，但退化成链表时会变成 O(n)。

五、常见树结构

• 满二叉树；
• 完全二叉树；
• 平衡二叉树；
• B 树；
• B+ 树；
• 红黑树；
• Trie 字典树。

六、练习

• 创建二叉树。
• 实现前序、中序、后序遍历。
• 计算树的高度。
• 统计叶子节点数量。
• 实现二叉搜索树查找和插入。