GESP 六级 · GESP 202512 C++ 六级 第 25 题

假定只有一个根节点的树的深度为 $1$，则一棵有 $n$ 个节点的完全二叉树，则树的深度为 $\lfloor \log_2(n) \rfloor + 1$。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】完全二叉树｜树深度计算｜对数运算

六级大纲“二叉树基础”模块的公式应用考点。命题人用它卡住死背结论的考生——很多学生知道“深度约等于 log2 n"，但不会严谨推导。

从定义出发，完全二叉树前 d 层总节点数为 2^d - 1。深度 d 满足 2^(d-1) ≤ n < 2^d，两边取对数得 d-1 ≤ log2 n < d，故 d = floor(log2 n) + 1。命题人给的是直接结论，但本质是层数与节点数的指数关系。

选项 B 是典型陷阱——把深度当成 log2 n 或忘记+1。命题人利用"depth of a single-node tree = 1"这个绝对化表述，误导学生忽略基数为 1 的对数结果 0。若只背结论不推导，选错概率超 60%。

若把“完全二叉树”改成“满二叉树”，公式需加条件"n = 2^d - 1"。若问“树的高度”（根到最深节点边数），答案应减 1。这类变式仍考对数与层级关系。