二叉树(Binary Tree)

定义

二叉树是每个节点最多有两个子节点（左孩子和右孩子）的树形数据结构。特殊形态包括满二叉树、完全二叉树和退化为链表的斜树。

原理

二叉树通常用含左右指针的节点表示，也可用数组表示完全二叉树。核心操作是遍历，分为深度优先的前序、中序、后序，以及广度优先的层序遍历。前序为根左右，中序为左根右，后序为左右根；层序借助队列逐层访问。遍历是绝大多数树算法的基础。

复杂度

• 遍历：O(n)
• 查找/插入/删除（普通二叉树）：O(n)
• 平衡时各操作可降至 O(log n)
• 空间复杂度：O(n)

应用场景

• 表达式解析树、语法树
• 哈夫曼编码树
• 堆、二叉搜索树等的结构基础
• 文件系统与决策树