二叉树基本概念及 STL 中的树形结构
哪些公司问过
叠纸1
答案要点
- 二叉树每个节点最多两个子节点,分左右子树
- 特殊形态:满二叉树、完全二叉树、二叉搜索树、平衡二叉树
- 遍历:前序、中序、后序(深度优先),层序(广度优先,借助队列)
- STL 中 set、map、multiset、multimap 主流实现基于红黑树,操作 O(log n),multi 系列允许重复键
- priority_queue 基于数组实现的二叉堆;unordered 系列基于哈希表而非树
易错点
- 把 unordered_map 说成基于红黑树
- 混淆完全二叉树与满二叉树的定义
- 认为 C++ 标准强制规定必须用红黑树,实际只规定了复杂度要求
面试官常见追问
- 平衡二叉搜索树(AVL)和红黑树有什么区别?什么是严格平衡?
- 为什么 STL 选红黑树而不是 AVL?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场