课后作业

第三十课

如无过程，上传图片中阐明思路也可以，或者涉及哪些知识点，也可以写出来

1. 给定一棵二叉树,其前序遍历结果为:ABDECFG,中序遍历结果为:DEBACFG.请问这棵树的正确后序遍历结果是什么？

• A. EDBFGCA
• B. EDBGCFA
• C. DEBGFCA
• D. DBEGFCA

• ❌
• 历史解析:
  • 正确答案：C 、EDBFGCA
  • 根据前序遍历和中序遍历的结果，我们可以推导出二叉树的具体结构

          A
        /   \
       B     C
      /       \
     D        F
      \        \
       E        G
  
  • 根据这个二叉树的结构，我们可以得到后序遍历的结果为：EDBGFCA

2. 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为( )

• A. ABDEGJHCFI
• B. ABDEGHJFIC
• C. ABCDEFGHIJ
• D. ABDEGHJCFI

• ❌
• 历史解析:
  • 正确答案：D 、ABDEGHJCFI
  • 根据后序遍历和中序遍历的结果，我们可以推导出二叉树的具体结构

          A
        /   \
       B     C
      / \     \
     D   E     F
        / \   /
       G   H I
            \
             J
  
  • 根据这个二叉树的结构，我们可以得到前序遍历的结果为：ABDEGHJCFI
  • 注意审题，是不是选错了选项

3. 前序遍历和中序遍历相同的二叉树为且仅为( )

• A.只有1个点的二叉树
• B.根结点没有左子树的二叉树
• C.非叶子结点只有左子树的二叉树
• D.非叶子结点只有右子树的二叉树

• ❌
• 历史解析:
  • 正确答案：D 、非叶子结点只有右子树的二叉树
  • 前序遍历和中序遍历相同的二叉树意味着每次遍历到一个节点时，这个节点总是出现在遍历的最前面
  • 对于这种二叉树，必须满足以下条件：
    1. 该树的每个非叶子节点只有右子树（或者没有左子树）。
    2. 因为如果有左子树，在中序遍历时会先访问左子树节点，而在前序遍历时会先访问根节点，所以两种遍历结果会不同。
  • 对于选项A（只有1个点的二叉树），前序遍历和中序遍历的结果都是这个唯一的点，这是符合条件的，但是并不能涵盖所有情况。
  • 对于选项B（根结点没有左子树的二叉树），如果根节点有右子树，前序遍历和中序遍历的结果会相同，这个情况也是符合的。
  • 对于选项C（非叶子结点只有左子树的二叉树），前序遍历会先访问根节点，然后左子树，而中序遍历会先访问左子树，然后根节点，因此两者不同。
  • 对于选项D（非叶子结点只有右子树的二叉树），前序遍历和中序遍历都会先访问根节点，然后右子树，因此两者相同。

4. 令根结点的高度为 1，则一棵含有 2021 个结点的二叉树的高度至少为多少？

• A. 10
• B. 11
• C. 12
• D. 2021

• ✅
• 历史解析:
  • 正确答案：B 、11
  • 要计算一棵含有 2021 个结点的二叉树的最小高度，我们需要考虑它的高度最小的情况下。最小高度发生在树是完全平衡的情况下（即每个层级的结点数量尽量多）
  • 对于完全平衡的二叉树，树的高度 h 与结点数量 n 之间的关系是：n >= 2^h - 1
  • 一棵含有 2021 个结点的二叉树，其最大结点数为 2^11 - 1 = 2047，所以高度至少为 11。