Question

一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为BADCFEG，则后序遍历序列为什么？并画出这颗二叉树

Answer 1

问：一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为BADCFEG，则后序遍历序列为什么？并画出这颗二叉树

答：这颗二叉树的后序遍历序列为DBAFEGC。

问：已知一个栈S的入栈顺序为1234567，同时在任何时候都可以入栈或者出栈。如下序列是否是正确的出栈。如果不是，请写明原因 2136547 3125467

答：对于序列2136547，我们可以尝试模拟一下出栈的过程，从栈顶开始匹配出栈序列，具体过程如下： 入栈1，栈中元素为1 入栈2，栈中元素为1, 2 入栈3，栈中元素为1, 2, 3 出栈2，栈中元素为1, 3 入栈6，栈中元素为1, 3, 6 出栈3，栈中元素为1, 6 出栈1，栈中元素为6 出栈6，栈为空 入栈5，栈中元素为5 出栈4，无法匹配，出栈序列不正确 因此，序列2136547不是正确的出栈序列。

答：对于序列3125467，同样可以模拟出栈的过程，具体如下： 入栈1，栈中元素为1 入栈2，栈中元素为1, 2 入栈3，栈中元素为1, 2, 3 出栈3，栈中元素为1, 2 入栈5，栈中元素为1, 2, 5 入栈4，栈中元素为1, 2, 5, 4 出栈4，栈中元素为1, 2, 5 出栈5，栈中元素为1, 2 出栈2，栈中元素为1 出栈1，栈为空 入栈6，栈中元素为6 出栈6，栈为空 入栈7，栈中元素为7 出栈7，栈为空 因此，序列3125467是正确的出栈序列。

答：入栈顺序是升序排列，任意数A后面比A小的数都按照降序排列

答：2136547是3125467不是

问：假设用于通信的电文仅由abcd四个字母组成，字母在电文中出现的频率分别为0.3,0.2,0.4,0.1,请字母的出现频率构造一颗哈夫曼树，并为这四个字母编码

答：根据哈夫曼树的构造过程，我们需要先将这四个字母按照出现频率从小到大排序，然后构造出一棵二叉树。具体的步骤如下： 1. 将四个字母按照出现频率从小到大排序：d(0.1)，b(0.2)，a(0.3)，c(0.4)。 2. 取出最小的两个字母d和b，将它们合并成一个节点，其权值为它们的频率之和0.1+0.2=0.3，形成一个新的子树，将它作为根节点。 3. 再从剩余的节点中取出最小的两个字母a和新节点d-b，将它们合并成一个节点，其权值为它们的频率之和0.3+0.3=0.6，形成一个新的子树，将它作为新的根节点。 4. 最后再将剩下的两个字母c和新节点a-d-b合并成一个节点，其权值为它们的频率之和0.4+0.6=1，形成最终的哈夫曼树。

答：根据哈夫曼树的构造过程，我们可以得到每个字母的编码：d: 00b: 01a: 10c: 11

问：谢谢

答：好的