GESP 六级 · GESP 202509 C++ 六级 第 21 题

一棵有 $n$ 个节点的二叉树一定有 $n - 1$ 条边。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】树的性质｜数据结构基础

六级考查数据结构核心概念，这道题卡住的是考生对"树"本质的模糊认知。命题人放这道题，就是想看你是否真的理解"树"的定义，而不是死记硬背结论。

看到"二叉树"先别被"二"带偏，回归定义：树是连通无环图。图论里有个铁律——连通图边数至少为$V-1$，无环图边数至多为$V-1$，两者同时成立就是恰好$V-1$。所以无论它是二叉、三元还是普通树，只要节点数$n$确定，边数必为$n-1$。这一类题的通法是：抓住"树"的本质（连通无环），而不是纠结"几叉"。

选项B的陷阱在于把"二"当成变量：有人觉得二叉树每个节点可能有两个孩子，边数会不会是$2n$或者$n+1$？其实"二"只是描述分支数上限，不影响整体拓扑。命题人故意用"二叉"这个词制造语义干扰，诱导你过度思考结构细节。如果你只背"树有$n-1$条边"这个结论，却没理解"连通无环"这个本质，就会掉进"二"的陷阱里。

如果把题改成"一棵有$n$个节点的二叉树至多有$n-1$条边"，答案就变B了——因为"至多"暗示可能更少，但树不可能少于$n-1$。刷到这种题，先问自己：命题人想考我"树"的定义，还是想考我"二"的描述？