06 树结构
节点关系、深度优先、层序与表达式树
对应本节 12 道题。点击题目展开答案和理由，保留此前生成的详细解析。
第 01 题 问题 1
根、父节点、子节点分别表示什么？
参考答案
根没有父节点；父节点直接连接其子节点。
解析
树内的层级关系由连接决定，节点的数值大小未必相关。
第 02 题 问题 2
叶节点一定存最小值吗？
参考答案
不一定。
解析
叶只表示没有子节点；普通树没有数值顺序约束。
第 03 题 问题 3
有序树中的“有序”是否一定指按键大小排序？
参考答案
不一定，通常指兄弟节点位置/次序有意义。
解析
不要把有序树、二叉树与二叉搜索树混为一谈。
第 04 题 问题 4
二叉树每个节点有几个子节点？
参考答案
最多两个，通常区分左与右。
解析
二叉并不要求每个节点恰好有两个孩子。
第 05 题 问题 5
根 A，左 B、右 C；B 左 D、右 E。前序遍历顺序？
参考答案
A,B,D,E,C。
解析
前序为根、左子树、右子树。
第 06 题 问题 6
同一棵树的中序遍历顺序？
参考答案
D,B,E,A,C。
解析
中序为左子树、根、右子树；普通树中序不保证键有序。
第 07 题 问题 7
同一棵树的后序遍历顺序？
参考答案
D,E,B,C,A。
解析
后序为左子树、右子树、根；常用于先处理子结构。
第 08 题 问题 8
同一棵树的层序遍历顺序？
参考答案
A,B,C,D,E。
解析
用 FIFO 队列逐层访问，通常左孩子先入队。
第 09 题 问题 9
遍历 n 个节点的时间是多少？
参考答案
O(n)，假定处理每个节点为常数时间。
解析
每个节点访问一次；单条搜索路径的成本不能当作完整遍历成本。
第 10 题 问题 10
递归遍历的额外栈空间由什么决定？
参考答案
树高 h，通常为 O(h)。
解析
均衡树约 O(log n)，退化链形树可 O(n)。
第 11 题 问题 11
表达式树 ((a+b)*(c-d)) 的根和两子树运算符是什么？
参考答案
根 *，左子树 +，右子树 −。
解析
运算符节点连接操作数子树；后序可用于求值。
第 12 题 问题 12
二叉搜索树中序有序，普通二叉树也必然有序吗？
参考答案
不必然。
解析
只有全树满足 BST 的左右键范围规则时，才能推出中序有序。