Question

3.请写出表达式 (3+5)(4-1) 的前缀表达式和后缀表达式

Answer 1

问：3.请写出表达式 (3+5)(4-1) 的前缀表达式和后缀表达式

答：表达式 (3+5)(4-1) 的前缀表达式为 "* + 3 5 - 4 1"，后缀表达式为 "3 5 + 4 1 - *"。

答：前缀表达式（也称为逆波兰表达式）是把运算符写在操作数之前的表达式，后缀表达式（也称为后缀波兰表达式）是把运算符写在操作数之后的表达式。

答：在表达式 (3+5)(4-1) 中，加号和乘号都是二元运算符，减号是一元运算符。在转换为前缀表达式时，需要把运算符和操作数写在一起，并把乘号写在最前面。在转换为后缀表达式时，需要把操作数和运算符写在一起，并把乘号写在最后面。

答：例如，表达式 (3+5)(4-1) 的前缀表达式为 "* + 3 5 - 4 1"，其中 "*" 表示乘号，"+" 表示加号，"-" 表示减号，3、5、4、1 分别表示四个操作数。后缀表达式为 "3 5 + 4 1 - "，其中同样使用 ""、"+"、"-" 分别表示乘号、加号、减号，3、5、4、1 分别表示四个操作数。

问：2.设六个字母A、B、C、D、E、F出现的频率为A26，B9，C14，D16，E29，F6，请以这些字母出现的频率构建哈夫曼（Huffman）树，并写出以上字母的哈夫曼编码。

答：首先，我们可以将这六个字母看做六个节点，每个节点的权值就是这个字母出现的频率。初始化：将这六个节点放在一个数组里面，按照权值从小到大排序。取出数组中最小的两个节点（A和F），构建一颗新的二叉树，这颗二叉树的根节点的权值为A和F的权值之和，A和F分别为根节点的左右儿子。将新构建的二叉树放回数组中，并将数组按照权值从小到大排序。取出数组中最小的两个节点（B和新构建的二叉树），构建一颗新的二叉树，这颗二叉树的根节点的权值为B和新构建的二叉树的权值之和，B和新构建的二叉树分别为根节点的左右儿子。

答：将新构建的二叉树放回数组中，并将数组按照权值从小到大排序。取出数组中最小的两个节点（C和新构建的二叉树），构建一颗新的二叉树，这颗二叉树的根节点的权值为C和新构建的二叉树的权值之和。

问：能给个图吗？谢谢

问：不要编码也行

答：65 E / \ 26 39 / \ / \ / \ C DA F B (C+B) / \ / \ A F B (A+F)

答：根据哈夫曼树的定义，我们可以得到以下字母的哈夫曼编码：A：0B：10C：110D：111E：1F：01

问：第一个问题两个括号之间有乘号是吧？

答：是的，没错哈

问：哈夫曼的能手画一下吧，看不太懂

答：在上班

答：你直接对着画就好了，你同学都看懂了，非常满意

问：设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。DEBCA

答：您提供的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。首先，我们来回顾一下二叉树的三种遍历方式：前序遍历：先访问根节点，然后访问左子树，最后访问右子树。中序遍历：先访问左子树，然后访问根节点，最后访问右子树。后序遍历：先访问左子树，然后访问右子树，最后访问根节点。通过前序遍历序列和中序遍历序列，我们可以构建出一棵二叉树。因为前序遍历序列的第一个字符A是该二叉树的根节点，所以我们可以找到中序遍历序列中的A，并根据A前面的字符来确定A的左子树，A后面的字符来确定A的右子树。

答：经过这样的分析，我们可以得到如下的二叉树：

答：A / \ B C / / \D E F

答：然后我们就可以使用后序遍历的方式来遍历该二叉树，得到后序遍历序列DEBCA。因此，对于您提出的问题，后序遍历序列为DEBCA。