二叉树基础全解：存储方式、遍历原理与查找树对比

二叉树基础全解：存储方式、遍历原理与查找树对比

作者：星之辰
标签：#二叉树 #数据结构 #查找树 #平衡树 #散列表对比
适用场景：面试基础、工程入门、算法进阶

引子：从线性到非线性，为什么必须掌握“树”？

编程初学者都逃不开线性结构（数组、链表、栈、队列），但一进阶算法，面试和业务就离不开树。树结构让你能高效组织、查找、管理和遍历大规模数据，内存、性能和算法设计能力直接“跃升一大步”。

一、树与二叉树：基本定义与家族成员

• 树（Tree）：节点、父子关系、根节点、叶子节点、兄弟节点。

• 高度/深度/层数：

  • 高度：从下往上数（如楼房高度）。
  • 深度：从上往下数（如鱼在水下的深度）。
  • 层数：根节点为第1层，依次递增。

二叉树（Binary Tree）：每个节点最多两个子节点（左、右）。

• 满二叉树：每层节点数都达最大，叶子全在最底层。
• 完全二叉树：叶子节点都在最底或次底层，最后一层叶子全