邓公《数据结构》第五章习题总结

邓公《数据结构》
第五章 二叉树
Q5
From the node node u of the binary tree of n nodes to the root node node by node, the following mistakes are:从n个节点的二叉树的叶节点u逐个节点地上溯到根节点的过程中，以下说法中错误的是：

A The passing nodes are all ancestors of u.经过的节点都是u的祖先。
B The worst time complexity is O(n)最坏时间复杂度为O(n)
C The path that is passed is uniquely determined经过的路径是唯一确定的
D Each time it goes up one level, the depth of the current node decreases by one and the height increases by one.每上溯一层，当前节点的深度减小1，而高度增加1。

正确答案：D

【注】做题时看清楚题目是选择正确的还是错误的，很关键！
【分析】
Each layer goes up one layer, and the depth decreases by one, but the increase in height may be greater than one, because the height of a node is determined by the higher of its left and right subtrees.每上溯一层，深度减小1，但高度的增加可能大于1，因为节点的高度由其左、右子树中较高者决定。

Q7
Similar to pre-order and in-order traversal, accessing the binary tree in the order of left child->right child->root node is called post-order traversal. The first visited node in the post-order traversal is与先序、中序遍历类似，以左子->右子->根节点的顺序来访问二叉树称为后序遍历。后序遍历中第一个被访问的节点是：

A The deepest node in the left chain左侧链中最深的节点
B Root node根节点
C The deepest node in the right chain右侧链中最深的节点
D None of the above以上皆不是

正确答案：D
【注】第一次做错选A，左侧链理解错误，觉得题意是指左子树部分最深的子节点。
【分析】
Starting from the root node, for each node in the middle, you can go left to the left and not to the left. If there is no way to go, then the node is the first node to be visited in the subsequent traversal.从根节点开始，对于中途每个节点，能往左就往左，不能往左就往右，若左右都无路可走，则该节点是后序遍历中第一个被访问的节点。

Q10
When using a queue to hierarchically traverse a binary tree, the nodes in the queue at any time satisfy:借助队列对二叉树进行层次遍历时,任意时刻队列中的节点满足：

A Both are on the path from the root node to the current node均位于从根节点到当前节点的路径上
B Both are descendants of the current node均是当前节点的后代
C The difference in height does not exceed 1高度相差不超过1
D The difference in depth does not exceed 1深度相差不超过1

正确答案：D
【注】第一次错选C，是因为把深度和高度一下子弄混了