3.4 树（30题）

<h3>基本概念</h3> <h1>1. 一棵深度为4的完全二叉树有多少个节点？</h1> 分析过程： <ul> <li>完全二叉树的定义：除了最后一层外，其他各层的节点数都达到最大值，且最后一层的节点都集中在该层最左边。</li> <li>深度为4的完全二叉树，前3层是满的，第4层可能不满但节点都在最左边。</li> </ul> 计算步骤： <ol> <li>前3层的节点数：2^0+2^1+2^2=1+2+4=7</li> <li>第4层的节点数最少为1，最多为 2^3=8</li> <li>因此，总节点数范围为 7+1=8到 7+8=15</li> </ol> 答案： <ul> <li>一棵深度为4的完全二叉树最多有15个节点，最少有8个节点。</li> </ul> <h1>2. 一棵深度为5的满二叉树有多少个节点？</h1> 分析过程： 满二叉树的定义：每一层上的所有结点都有两个子结点的二叉树。深度为5的满二叉树，每一层的节点数都是满的。 计算步骤： 总节点数：=1+2+4+8+16=31 或者2^5-1=31 答案：一棵深度为5的满二叉树有31个节点。 <h1>3. 一棵深度为5的二叉树最少有多少个节点？</h1> 分析过程： 一棵深度为5的二叉树，最少的情况是只有根节点和一条最长的路径。 计算步骤： 根节点1个每一层只有一个节点，直到第5层 答案： 一棵深度为5的二叉树最少有5个节点。 <h1>4. 一棵深度为5的二叉树最多有多少个节点？</h1> 分析过程： 一棵深度为5的二叉树，最多的情况是满二叉树。计算过程见第2题。 <h1>5. 一棵深度为5的完全二叉树有多少个叶子节点？</h1> 分析过程： <ul> <li>完全二叉树的叶子节点数可以通过总节点数来计算。</li> <li>深度为5的完全二叉树，总节点数范围为16到31。</li> </ul> 计算步骤： <ol> <li>对于完全二叉树，叶子节点数为 ⌈n/2⌉，其中 n 是总节点数。</li> <li>最少情况：16个节点，叶子节点数为 ⌈16/2⌉=8</li> <li>最多情况：31个节点，叶子节点数为 ⌈31/2⌉=16 ⌈31/2⌉表示向上取整。</li> </ol> 答案： <ul> <li>一棵深度为5的完全二叉树最少有8个叶子节点，最多有16个叶子节点。 <h1>6. 一棵深度为5的满二叉树有多少个分支节点？</h1> 分析过程：</li> </ul> 满二叉树的分支节点数可以通过总节点数来计算。深度为5的满二叉树，总节点数为31。 计算步骤：分支节点数 = 总节点数 - 叶子节点数叶子节点数 = 16 分支节点数 = 31 - 16 = 15 <h3>答案：</h3> 一棵深度为5的满二叉树有15个分支节点。 <h1>7. 一棵深度为5的二叉树最少有多少个叶子节点？</h1> 分析过程： 一棵深度为5的二叉树，最少的情况是只有根节点和一条最长的路径。 计算步骤： 根节点1个每一层只有一个节点，直到第5层最后一层的节点就是叶子节点 答案： 一棵深度为5的二叉树最少有1个叶子节点。 <h1>8. 一棵深度为5的二叉树最多有多少个分支节点？</h1> 分析过程： 一棵深度为5的二叉树，最多的情况是满二叉树。 计算步骤： 总节点数 = 31 叶子节点数 = 16 分支节点数 = 31 - 16 = 15 答案： 一棵深度为5的二叉树最多有15个分支节点。 <h1>9. 一棵深度为5的完全二叉树有多少个节点？</h1> 分析过程： <ul> <li>完全二叉树的定义：除了最后一层外，其他各层的节点数都达到最大值，且最后一层的节点都集中在该层最左边。</li> <li>深度为5的完全二叉树，前4层是满的，第5层可能不满但节点都在最左边。</li> </ul> 计算步骤： <ol> <li>前4层的节点数：2^0+2^1+2^2+2^3=15</li> <li>第5层的节点数最少为1，最多为 2^4=16</li> <li>因此，总节点数范围为 15+1=16 到 15+16=31</li> </ol> 答案： <ul> <li>一棵深度为5的完全二叉树最多有31个节点，最少有16个节点。</li> </ul> <h3>二叉树的遍历</h3> <h1>10. 一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，求后序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： <ul> <li>先序遍历：ABDECF</li> <li>中序遍历：DBEAFC</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>在中序遍历中，A将中序遍历分为左子树（DBE）和右子树（FC）。</li> <li>左子树的先序遍历是BDE，中序遍历是DBE。</li> <li>右子树的先序遍历是CF，中序遍历是FC。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BDE</li> <li>中序遍历：DBE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>先序遍历：CF</li> <li>中序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 后序遍历： <ul> <li>左子树：DEB</li> <li>右子树：FC</li> <li>根节点A</li> </ul> 答案： <ul> <li> 后序遍历序列：DEBFCA <h1>11. 一棵二叉树的中序遍历序列为DBEAFC，后序遍历序列为DEBFCA，求先序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>中序遍历：DBEAFC</li> <li>后序遍历：DEBFCA</li> </ul> 步骤： <ol> <li>后序遍历的最后一个节点A是根节点。</li> <li>在中序遍历中，A将中序遍历分为左子树（DBE）和右子树（FC）。</li> <li>左子树的后序遍历是DEB，中序遍历是DBE。</li> <li>右子树的后序遍历是FC，中序遍历是FC。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>后序遍历：DEB</li> <li>中序遍历：DBE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>后序遍历：FC</li> <li>中序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 先序遍历： <ul> <li>根节点A</li> <li>左子树：BDE</li> <li>右子树：CF</li> </ul> 答案： <ul> <li> 先序遍历序列：ABDECF <h1>12. 一棵二叉树的先序遍历序列为ABDECF，后序遍历序列为DEBFCA，求中序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>先序遍历：ABDECF</li> <li>后序遍历：DEBFCA</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>后序遍历的最后一个节点A是根节点。</li> <li>在先序遍历中，A后面的节点（BDECF）是左子树和右子树的节点。</li> <li>在后序遍历中，A前面的节点（DEBFC）是左子树和右子树的节点。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BDE</li> <li>后序遍历：DEB</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>先序遍历：CF</li> <li>后序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 中序遍历： <ul> <li>左子树：DBE</li> <li>根节点A</li> <li>右子树：FC</li> </ul> 答案： <ul> <li> 中序遍历序列：DBEAFC <h1>13. 一棵二叉树的先序遍历序列为ABDECF，层次遍历序列为ABCDEF，求中序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>先序遍历：ABDECF</li> <li>层次遍历：ABCDEF</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>层次遍历的第一个节点A也是根节点。</li> <li>在先序遍历中，A后面的节点（BDECF）是左子树和右子树的节点。</li> <li>在层次遍历中，A后面的节点（BCDEF）是左子树和右子树的节点。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BDE</li> <li>层次遍历：BDE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>先序遍历：CF</li> <li>层次遍历：CF</li> <li>根节点C</li> <li>左子树F</li> </ul> 中序遍历： <ul> <li>左子树：DBE</li> <li>根节点A</li> <li>右子树：FC</li> </ul> 答案： <ul> <li>中序遍历序列：DBEAFC</li> </ul> <h1>14. 一棵二叉树的中序遍历序列为DBEAFC，层次遍历序列为ABCDEF，求先序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： <ul> <li>中序遍历：DBEAFC</li> <li>层次遍历：ABCDEF</li> </ul> 步骤： <ol> <li>层次遍历的第一个节点A是根节点。</li> <li>在中序遍历中，A将中序遍历分为左子树（DBE）和右子树（FC）。</li> <li>左子树的层次遍历是BDE，中序遍历是DBE。</li> <li>右子树的层次遍历是CF，中序遍历是FC。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>层次遍历：BDE</li> <li>中序遍历：DBE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>层次遍历：CF</li> <li>中序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 先序遍历： <ul> <li>根节点A</li> <li>左子树：BDE</li> <li>右子树：CF</li> </ul> 答案： <ul> <li> 先序遍历序列：ABDECF <h1>15. 一棵二叉树的后序遍历序列为DEBFCA，层次遍历序列为ABCDEF，求中序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>后序遍历：DEBFCA</li> <li>层次遍历：ABCDEF</li> </ul> 步骤： <ol> <li>后序遍历的最后一个节点A是根节点。</li> <li>层次遍历的第一个节点A也是根节点。</li> <li>在后序遍历中，A前面的节点（DEBFC）是左子树和右子树的节点。</li> <li>在层次遍历中，A后面的节点（BCDEF）是左子树和右子树的节点。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>后序遍历：DEB</li> <li>层次遍历：BDE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>后序遍历：FC</li> <li>层次遍历：CF</li> <li>根节点C</li> <li>左子树F</li> </ul> 中序遍历： <ul> <li>左子树：DBE</li> <li>根节点A</li> <li>右子树：FC</li> </ul> 答案： <ul> <li> 中序遍历序列：DBEAFC <h1>16. 一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，求层次遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>先序遍历：ABDECF</li> <li>中序遍历：DBEAFC</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>在中序遍历中，A将中序遍历分为左子树（DBE）和右子树（FC）。</li> <li>左子树的先序遍历是BDE，中序遍历是DBE。</li> <li>右子树的先序遍历是CF，中序遍历是FC。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BDE</li> <li>中序遍历：DBE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>先序遍历：CF</li> <li>中序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 层次遍历： <ul> <li>根节点A</li> <li>左子树B</li> <li>右子树C</li> <li>左子树D</li> <li>右子树E</li> <li>左子树F</li> </ul> 答案： <ul> <li> 层次遍历序列：ABCDEF <h1>17. 一棵二叉树的中序遍历序列为DBEAFC，后序遍历序列为DEBFCA，求层次遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>中序遍历：DBEAFC</li> <li>后序遍历：DEBFCA</li> </ul> 步骤： <ol> <li>后序遍历的最后一个节点A是根节点。</li> <li>在中序遍历中，A将中序遍历分为左子树（DBE）和右子树（FC）。</li> <li>左子树的后序遍历是DEB，中序遍历是DBE。</li> <li>右子树的后序遍历是FC，中序遍历是FC。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>后序遍历：DEB</li> <li>中序遍历：DBE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>后序遍历：FC</li> <li>中序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 层次遍历： <ul> <li>根节点A</li> <li>左子树B</li> <li>右子树C</li> <li>左子树D</li> <li>右子树E</li> <li>左子树F</li> </ul> 答案： <ul> <li> 层次遍历序列：ABCDEF <h1>18. 一棵二叉树的先序遍历序列为ABDECF，后序遍历序列为DEBFCA，求层次遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>先序遍历：ABDECF</li> <li>后序遍历：DEBFCA</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>后序遍历的最后一个节点A是根节点。</li> <li>在先序遍历中，A后面的节点（BDECF）是左子树和右子树的节点。</li> <li>在后序遍历中，A前面的节点（DEBFC）是左子树和右子树的节点。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BDE</li> <li>后序遍历：DEB</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>先序遍历：CF</li> <li>后序遍历：FC</li> <li>根节点C</li> <li>左子树F</li> </ul> 层次遍历： <ul> <li>根节点A</li> <li>左子树B</li> <li>右子树C</li> <li>左子树D</li> <li>右子树E</li> <li>左子树F</li> </ul> 答案： <ul> <li> 层次遍历序列：ABCDEF <h1>19. 一棵二叉树的先序遍历序列为ABDECF，层次遍历序列为ABCDEF，求后序遍历序列。(请画图分析，下面只给出简略分析过程)</h1> 分析过程： </li> <li>先序遍历：ABDECF</li> <li>层次遍历：ABCDEF</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>层次遍历的第一个节点A也是根节点。</li> <li>在先序遍历中，A后面的节点（BDECF）是左子树和右子树的节点。</li> <li>在层次遍历中，A后面的节点（BCDEF）是左子树和右子树的节点。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BDE</li> <li>层次遍历：BDE</li> <li>根节点B</li> <li>左子树D</li> <li>右子树E</li> </ul> 右子树： <ul> <li>先序遍历：CF</li> <li>层次遍历：CF</li> <li>根节点C</li> <li>左子树F</li> </ul> 后序遍历： <ul> <li>左子树：DEB</li> <li>右子树：FC</li> <li>根节点A</li> </ul> 答案： <ul> <li>后序遍历序列：DEBFCA</li> </ul> <h3>哈夫曼树</h3> <h1>20. 给定字符频率分别为A: 45, B: 13, C: 12, D: 16, E: 9, F: 5，构建哈夫曼树并计算带权路径长度。</h1> 分析过程： <ol> <li>创建一个优先队列（最小堆），将每个字符及其频率作为节点加入队列。</li> <li>重复以下步骤，直到队列中只剩下一个节点： <ul> <li>从队列中取出两个频率最小的节点。</li> <li>创建一个新的内部节点，其频率为这两个节点频率之和。</li> <li>将这个新节点重新加入队列。</li> </ul></li> <li>最后剩下的节点即为哈夫曼树的根节点。</li> <li>计算每个字符的带权路径长度（WPL）：字符频率 × 该字符在树中的路径长度。</li> </ol> 步骤： <ol> <li>初始化优先队列：(A, 45), (B, 13), (C, 12), (D, 16), (E, 9), (F, 5)</li> <li>取出两个最小频率节点 (F, 5) 和 (E, 9)，创建新节点 (FE, 14)</li> <li>更新队列：(A, 45), (B, 13), (C, 12), (D, 16), (FE, 14)</li> <li>取出两个最小频率节点 (C, 12) 和 (FE, 14)，创建新节点 (CFE, 26)</li> <li>更新队列：(A, 45), (B, 13), (D, 16), (CFE, 26)</li> <li>取出两个最小频率节点 (B, 13) 和 (D, 16)，创建新节点 (BD, 29)</li> <li>更新队列：(A, 45), (CFE, 26), (BD, 29)</li> <li>取出两个最小频率节点 (CFE, 26) 和 (BD, 29)，创建新节点 (CFEBD, 55)</li> <li>更新队列：(A, 45), (CFEBD, 55)</li> <li>取出两个最小频率节点 (A, 45) 和 (CFEBD, 55)，创建新节点 (ACFEBD, 100) <pre><code class="language-javascript"> (ACFEBD, 100) / \ (A, 45) (CFEBD, 55) / \ (BD, 29) (CFE, 26) / \ / \ (B, 13) (D, 16) (FE, 14) (C, 12) / \ (F, 5) (E, 9)</code></pre> 带权路径长度（WPL）：</li> </ol> A: 45 × 1 = 45 B: 13 × 3 = 39 C: 12 × 3 = 36 D: 16 × 3 = 48 E: 9 × 4 = 36 F: 5 × 4 = 20 总WPL： 45 + 39 + 36 + 48 + 36 + 20 = 224 答案： 带权路径长度为224 <h1>21. 给定字符频率分别为A: 10, B: 15, C: 30, D: 16, E: 29，构建哈夫曼树并计算带权路径长度。</h1> 分析过程： <ol> <li>初始化优先队列：(A, 10), (B, 15), (C, 30), (D, 16), (E, 29)</li> <li>取出两个最小频率节点 (A, 10) 和 (B, 15)，创建新节点 (AB, 25)</li> <li>更新队列：(C, 30), (D, 16), (E, 29), (AB, 25)</li> <li>取出两个最小频率节点 (D, 16) 和 (AB, 25)，创建新节点 (DAB, 41)</li> <li>更新队列：(C, 30), (E, 29), (DAB, 41)</li> <li>取出两个最小频率节点 (C, 30) 和 (E, 29)，创建新节点 (CE, 59)</li> <li>更新队列：(DAB, 41), (CE, 59)</li> <li>取出两个最小频率节点 (DAB, 41) 和 (CE, 59)，创建新节点 (DABCE, 100)</li> </ol> 哈夫曼树： <pre><code class="language-javascript"> (DABCE, 100) / \ (DAB, 41) (CE, 59) / \ / \ (AB, 25) (D, 16) (C, 30) (E, 29) / \ (A, 10) (B, 15)</code></pre> 带权路径长度（WPL）： A: 10 × 3 = 30 B: 15 × 3 = 45 C: 30 × 2 = 60 D: 16 × 2 = 32 E: 29 × 2 = 58 总WPL： 30 + 45 + 60 + 32 + 58 = 225 答案： 带权路径长度为225 <h1>22. 给定字符频率分别为A: 25, B: 20, C: 15, D: 10, E: 10, F: 5，构建哈夫曼树并计算带权路径长度。</h1> 分析过程： <ol> <li>初始化优先队列：(A, 25), (B, 20), (C, 15), (D, 10), (E, 10), (F, 5)</li> <li>取出两个最小频率节点 (F, 5) 和 (D, 10)，创建新节点 (FD, 15)</li> <li>更新队列：(A, 25), (B, 20), (C, 15), (E, 10), (FD, 15)</li> <li>取出两个最小频率节点 (E, 10) 和 (FD, 15)，创建新节点 (EFD, 25)</li> <li>更新队列：(A, 25), (B, 20), (C, 15), (EFD, 25)</li> <li>取出两个最小频率节点 (C, 15) 和 (B, 20)，创建新节点 (CB, 35)</li> <li>更新队列：(A, 25), (EFD, 25), (CB, 35)</li> <li>取出两个最小频率节点 (A, 25) 和 (EFD, 25)，创建新节点 (AEFD, 50)</li> <li>更新队列：(CB, 35), (AEFD, 50)</li> <li>取出两个最小频率节点 (CB, 35) 和 (AEFD, 50)，创建新节点 (CBAEFD, 85)</li> </ol> 哈夫曼树： <pre><code class="language-javascript"> (CBAEFD, 85) / \ (CB, 35) (AEFD, 50) / \ / \ (B, 20) (C, 15) (A, 25) (EFD, 25) / \ (E, 10) (FD, 15) / \ (F, 5) (D, 10)</code></pre> 带权路径长度（WPL）： A: 25 × 2 = 50 B: 20 × 2 = 40 C: 15 × 2 = 30 D: 10 × 3 = 30 E: 10 × 3 = 30 F: 5 × 3 = 15 总WPL： 50 + 40 + 30 + 30 + 30 + 15 = 195 答案： 带权路径长度为195 <h1>23. 给定字符频率分别为A: 5, B: 9, C: 12, D: 13, E: 16, F: 45，构建哈夫曼树并计算带权路径长度。</h1> 分析过程： <ol> <li>初始化优先队列：(A, 5), (B, 9), (C, 12), (D, 13), (E, 16), (F, 45)</li> <li>取出两个最小频率节点 (A, 5) 和 (B, 9)，创建新节点 (AB, 14)</li> <li>更新队列：(C, 12), (D, 13), (E, 16), (F, 45), (AB, 14)</li> <li>取出两个最小频率节点 (C, 12) 和 (AB, 14)，创建新节点 (CAB, 26)</li> <li>更新队列：(D, 13), (E, 16), (F, 45), (CAB, 26)</li> <li>取出两个最小频率节点 (D, 13) 和 (E, 16)，创建新节点 (DE, 29)</li> <li>更新队列：(F, 45), (CAB, 26), (DE, 29)</li> <li>取出两个最小频率节点 (CAB, 26) 和 (DE, 29)，创建新节点 (CABDE, 55)</li> <li>更新队列：(F, 45), (CABDE, 55)</li> <li>取出两个最小频率节点 (F, 45) 和 (CABDE, 55)，创建新节点 (FCABDE, 100)</li> </ol> 哈夫曼树： <pre><code class="language-javascript"> (FCABDE, 100) / \ (F, 45) (CABDE, 55) / \ (DE, 29) (CAB, 26) / \ / \ (D, 13) (E, 16) (AB, 14) (C, 12) / \ (A, 5) (B, 9)</code></pre> 带权路径长度（WPL）： A: 5 × 4 = 20 B: 9 × 4 = 36 C: 12 × 3 = 36 D: 13 × 3 = 39 E: 16 × 3 = 48 F: 45 × 1 = 45 总WPL： 20 + 36 + 36 + 39 + 48 + 45 = 224 答案： 带权路径长度为224 <h1>24. 给定字符频率分别为A: 1, B: 2, C: 3, D: 4, E: 5, F: 6, G: 7, H: 8，构建哈夫曼树并计算带权路径长度。</h1> 构建哈夫曼树 <ol> <li> 初始状态： <ul> <li>字符频率：A: 1, B: 2, C: 3, D: 4, E: 5, F: 6, G: 7, H: 8</li> </ul> </li> <li> 步骤： <ul> <li>每次选择两个频率最小的节点，合并成一个新的节点，新节点的频率为两个节点频率之和。</li> <li>重复上述步骤，直到只剩下一个节点。</li> </ul> </li> </ol> 具体步骤： <ol> <li> 初始节点： <ul> <li>A: 1</li> <li>B: 2</li> <li>C: 3</li> <li>D: 4</li> <li>E: 5</li> <li>F: 6</li> <li>G: 7</li> <li>H: 8</li> </ul> </li> <li> 第一次合并： <ul> <li>选择A (1) 和 B (2)，合并成新节点 AB (3)</li> <li>剩余节点：AB (3), C (3), D (4), E (5), F (6), G (7), H (8)</li> </ul> </li> <li> 第二次合并： <ul> <li>选择AB (3) 和 C (3)，合并成新节点 ABC (6)</li> <li>剩余节点：ABC (6), D (4), E (5), F (6), G (7), H (8)</li> </ul> </li> <li> 第三次合并： <ul> <li>选择D (4) 和 E (5)，合并成新节点 DE (9)</li> <li>剩余节点：ABC (6), DE (9), F (6), G (7), H (8)</li> </ul> </li> <li> 第四次合并： <ul> <li>选择ABC (6) 和 F (6)，合并成新节点 ABCF (12)</li> <li>剩余节点：ABCF (12), DE (9), G (7), H (8)</li> </ul> </li> <li> 第五次合并： <ul> <li>选择G (7) 和 H (8)，合并成新节点 GH (15)</li> <li>剩余节点：ABCF (12), DE (9), GH (15)</li> </ul> </li> <li> 第六次合并： <ul> <li>选择DE (9) 和 ABCF (12)，合并成新节点 DE_ABCF (21)</li> <li>剩余节点：DE_ABCF (21), GH (15)</li> </ul> </li> <li> 第七次合并： <ul> <li>选择DE_ABCF (21) 和 GH (15)，合并成新节点 DE_ABCF_GH (36)</li> <li>剩余节点：DE_ABCF_GH (36)</li> </ul> 计算带权路径长度根据哈夫曼树的结构，我们可以计算每个字符的路径长度： </li> </ol> A: 1，路径长度为4 B: 2，路径长度为4 C: 3，路径长度为3 D: 4，路径长度为3 E: 5，路径长度为3 F: 6，路径长度为3 G: 7，路径长度为2 H: 8，路径长度为2 计算带权路径长度：96。 <h3>其他</h3> <h1>25. 一棵深度为5的完全二叉树，第3层有多少个节点？</h1> 分析过程： 完全二叉树的定义：除了最后一层外，其他各层的节点数都达到最大值，且最后一层的节点都集中在该层最左边。深度为5的完全二叉树，前4层是满的，第5层可能不满但节点都在最左边。 计算步骤： 第1层的节点数：2^0=1 第2层的节点数：2^1=2 第3层的节点数：2^2=4 答案： 第3层有4个节点。 <h1>26. 一棵二叉树的先序遍历结果是ABDCFE，中序遍历结果是DBACFE，求该树有多少个叶子节点。</h1> 分析过程： <ul> <li>先序遍历：ABDCFE</li> <li>中序遍历：DBACFE</li> </ul> 步骤： <ol> <li>先序遍历的第一个节点A是根节点。</li> <li>在中序遍历中，A将中序遍历分为左子树（DB）和右子树（CFE）。</li> <li>左子树的先序遍历是BD，中序遍历是DB。</li> <li>右子树的先序遍历是CFE，中序遍历是CFE。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>先序遍历：BD</li> <li>中序遍历：DB</li> <li>根节点B</li> <li>左子树D</li> </ul> 右子树： <ul> <li>先序遍历：CFE</li> <li>中序遍历：CFE</li> <li>根节点C</li> <li>左子树F</li> <li>右子树E</li> </ul> 树的结构： <pre><code class="language-javascript"> A / \ B C / / \ D F E</code></pre> 叶子节点： D, F, E 答案： 该树有3个叶子节点。 <h1>27. 一棵二叉树的前序遍历结果是1245367，中序遍历结果是4251637，求该树有多少个节点。</h1> 分析过程： <ul> <li>前序遍历：1245367</li> <li>中序遍历：4251637</li> </ul> 步骤： <ol> <li>前序遍历的第一个节点1是根节点。</li> <li>在中序遍历中，1将中序遍历分为左子树（425）和右子树（637）。</li> <li>左子树的前序遍历是245，中序遍历是425。</li> <li>右子树的前序遍历是367，中序遍历是637。</li> <li>递归处理左子树和右子树。</li> </ol> 左子树： <ul> <li>前序遍历：245</li> <li>中序遍历：425</li> <li>根节点2</li> <li>左子树4</li> <li>右子树5</li> </ul> 右子树： <ul> <li>前序遍历：367</li> <li>中序遍历：637</li> <li>根节点3</li> <li>左子树6</li> <li>右子树7</li> </ul> 树的结构： <pre><code class="language-javascript"> 1 / \ 2 3 / \ / \ 4 5 6 7</code></pre> 答案： 该树有7个节点。 <h1>28. 一棵二叉树的前序遍历和中序遍历结果相同，且节点数为15，求该树的深度。</h1> 分析过程： 前序遍历和中序遍历结果相同，说明该树是一棵只有右孩子的树（即每个节点只有右子节点）。 步骤： 节点数为15。在只有右孩子的树中，深度等于节点数。 答案： 该树的深度为15。 <h1>29. 一棵二叉树的节点总数为19，且只有度为0和度为2的节点，求该树的叶子节点数。</h1> 分析过程： <ul> <li>设叶子节点数为 L，度为2的节点数为 I。</li> <li>根据二叉树的性质，有 L=I+1。</li> <li>节点总数 N=L+I。</li> </ul> 计算步骤： <ol> <li>N=19</li> <li>L=I+1</li> <li>N=L+I</li> <li>将 L=I+1代入 N=L+I： 19=(I+1)+I I=9</li> <li>L=I+1=10</li> </ol> 答案： <ul> <li>该树有10个叶子节点。</li> </ul> <h1>30. 一棵二叉树的层序遍历结果是1, 2, 3, 4, 5, 6, 7，且为完全二叉树，求其深度。</h1> 分析过程： 完全二叉树的定义：除了最后一层外，其他各层的节点数都达到最大值，且最后一层的节点都集中在该层最左边。层序遍历结果：1, 2, 3, 4, 5, 6, 7 计算步骤： 层序遍历结果共有7个节点。完全二叉树的节点数与深度的关系：对于深度为 ℎ h 的完全二叉树，节点数 𝑛 n 满足： 2^(ℎ−1)≤𝑛<2^ℎ 答案：该树的深度为3。

数据结构与算法——编程实践

3.4 树（30题）

页面列表