1． 请编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法。 2． 请编程实现哈夫曼树的构造，以及对该赫夫曼树的编码。 3． 请编程实现利用二叉树求解表达式的值。

1. **二叉树遍历**
- **中序遍历** (递归)

     def inorder_traversal_recursive(root):
         if root is not None:
             inorder_traversal_recursive(root.left)
             print(root.val, end=" ")  # 左 -> 根 -> 右
             inorder_traversal_recursive(root.right)

- **中序遍历** (非递归)

     def inorder_traversal_iterative(root):
         stack = []
         result = []
         while root or stack:
             while root:
                 stack.append(root)
                 root = root.left
             root = stack.pop()
             result.append(root.val)
             root = root.right
         return ' '.join(map(str, result))  # 左 -> 根 -> 右

同样的，**后序遍历** 的递归和非递归版本类似，只需调整访问顺序为根 -> 右 -> 左。

2. **哈夫曼树和编码**
- **构造**:

     class Node:
         def __init__(self, char, freq):
             self.char = char
             self.freq = freq
             self.left = None
             self.right = None

     def build_huffman_tree(freqs):
         nodes = [Node(c, f) for c, f in freqs.items()]
         heapq.heapify(nodes)

         while len(nodes) > 1:
             left = heapq.heappop(nodes)
             right = heapq.heappop(nodes)
             merged = Node(None, left.freq + right.freq)
             merged.left = left
             merged.right = right
             heapq.heappush(nodes, merged)

         return nodes[0]

- **编码**:

     def huffman_encoding(node, code=''):
         if node is None:
             return ''
         elif node.char is not None:
             return code + str(len(code)), node.char
         else:
             return huffman_encoding(node.left, code + '0') + huffman_encoding(node.right, code + '1')

3. **二叉树求解表达式值**
- 这通常涉及到构建一个解析树，可以使用递归的方法，例如前序遍历表示操作数，中序遍历表示运算符。具体实现会依赖于特定的算术运算规则。对于简单算术表达式如`"(a+b)*c"`，可以先转换成逆波兰表示法（后缀表达式），然后计算。

# 假设有一个函数parse_expression()能将给定的字符串转为后缀表达式列表
def evaluate_postfix(expression):
    stack = []
    for token in expression:
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            stack.append(eval(f"{a} {token} {b}"))
    return stack[0]