写一个程序(1)输入二叉树的字符序列，建立二叉链表 (2)中序遍历二叉树:递归算法。 *(3)中序遍历二叉树:非递归算法。 (最好也能实现先序，后序非递归算 法) (4)求二叉树的高度。 (5)求二叉树的叶子个数。 *(6)将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数 *(7)建立中序线索二叉树，并实现中序遍历。 (8)借助队列实现二叉树的层次遍历。 (9)在主函数中设计一个简单的菜单，分别调试上述算法 *(10)综合训练:为N个权值设计哈夫曼编码。

好的，以下是对你的问题的回答：

1. 以下是输入二叉树字符序列并建立二叉链表的程序，其中使用了队列来辅助建立二叉树：

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

def create_tree(s):
    if not s:
        return None
    root = Node(s[0])
    queue = [root]
    i = 1
    while queue:
        cur = queue.pop(0)
        if i < len(s):
            if s[i] != '#':
                cur.left = Node(s[i])
                queue.append(cur.left)
            i += 1
        if i < len(s):
            if s[i] != '#':
                cur.right = Node(s[i])
                queue.append(cur.right)
            i += 1
    return root

2. 以下是中序遍历二叉树的递归算法：

def inorder_traversal(root):
    if not root:
        return
    inorder_traversal(root.left)
    print(root.val, end=' ')
    inorder_traversal(root.right)

3. 以下是中序遍历二叉树的非递归算法：

def inorder_traversal(root):
    stack = []
    cur = root
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            print(cur.val, end=' ')
            cur = cur.right

4. 以下是求二叉树的高度的程序：

def get_height(root):
    if not root:
        return 0
    left_height = get_height(root.left)
    right_height = get_height(root.right)
    return max(left_height, right_height) + 1

5. 以下是求二叉树的叶子个数的程序：

def get_leaf_count(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return get_leaf_count(root.left) + get_leaf_count(root.right)

6. 以下是将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数的程序：

def get_leaf_count(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return get_leaf_count(root.left) + get_leaf_count(root.right)

def get_forest_leaf_count(root):
    if not root:
        return 0
    return get_leaf_count(root) + get_forest_leaf_count(root.left) + get_forest_leaf_count(root.right)

7. 以下是建立中序线索二叉树，并实现中序遍历的程序：

class ThreadedNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.is_threaded_left = False
        self.is_threaded_right = False

def create_threaded_tree(root, pre=None):
    if not root:
        return pre
    pre = create_threaded_tree(root.left, pre)
    if not root.left:
        root.is_threaded_left = True
        root.left = pre
    if pre and not pre.right:
        pre.is_threaded_right = True
        pre.right = root
    pre = root
    pre = create_threaded_tree(root.right, pre)
    return pre

def inorder_traversal(root):
    cur = root
    while cur:
        while not cur.is_threaded_left:
            cur = cur.left
        print(cur.val, end=' ')
        while cur.is_threaded_right:
            cur = cur.right
            print(cur.val, end=' ')
        cur = cur.right

8. 以下是借助队列实现二叉树的层次遍历的程序：

def level_order_traversal(root):
    if not root:
        return
    queue = [root]
    while queue:
        cur = queue.pop(0)
        print(cur.val, end=' ')
        if cur.left:
            queue.append(cur.left)
        if cur.right:
            queue.append(cur.right)

9. 以下是一个简单的菜单程序，用于调试上述算法：

def main():
    s = input('请输入二叉树的字符序列：')
    root = create_tree(s)
    while True:
        print('\n请选择要执行的算法：')
        print('1. 中序遍历二叉树（递归）')
        print('2. 中序遍历二叉树（非递归）')
        print('3. 求二叉树的高度')
        print('4. 求二叉树的叶子个数')
        print('5. 计算森林中叶子个数')
        print('6. 建立中序线索二叉树，并实现中序遍历')
        print('7. 层次遍历二叉树')
        print('0. 退出程序')
        choice = int(input('请输入选项：'))
        if choice == 1:
            inorder_traversal(root)
        elif choice == 2:
            inorder_traversal(root)
        elif choice == 3:
            print(get_height(root))
        elif choice == 4:
            print(get_leaf_count(root))
        elif choice == 5:
            print(get_forest_leaf_count(root))
        elif choice == 6:
            create_threaded_tree(root)
            inorder_traversal(root)
        elif choice == 7:
            level_order_traversal(root)
        elif choice == 0:
            break
        else:
            print('无效的选项，请重新输入！')

if __name__ == '__main__':
    main()

10. 以下是为N个权值设计哈夫曼编码的程序：

class HuffmanNode:
    def __init__(self, val, weight):
        self.val = val
        self.weight = weight
        self.left = None
        self.right = None

def create_huffman_tree(weights):
    nodes = [HuffmanNode(i, weight) for i, weight in enumerate(weights)]
    while len(nodes) > 1:
        nodes.sort(key=lambda x: x.weight)
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = HuffmanNode(None, left.weight + right.weight)
        parent.left = left
        parent.right = right
        nodes.append(parent)
    return nodes[0]

def get_huffman_code(root):
    code = {}

    def dfs(node, cur_code=''):
        if not node:
            return
        if node.val is not None:
            code[node.val] = cur_code
        dfs(node.left, cur_code + '0')
        dfs(node.right, cur_code + '1')

    dfs(root)
    return code

以上是对你的问题的回答，希望能对你有所帮助！