如何在Python中以节点结构形式打印二叉树？附表达式树排序需求

嘿，我刚好有一套完整的实现方案，能完美解决你说的把字符串数学表达式转成二叉树，还能保证每个节点的左子节点始终小于右子节点，最后按层级打印的需求。咱们一步步拆解来看：

核心实现步骤 #

1. 定义二叉树节点类 #

首先得有个基础的节点结构，用来存储每个元素（操作数或运算符）以及左右子节点：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

2. 构建表达式解析树（buildParseTree） #

这个函数负责把字符串形式的数学表达式（带括号、多位数）转换成二叉树结构，核心是用栈来处理括号和运算符优先级：

def buildParseTree(expr):
    # 先清理表达式中的空格
    expr = expr.replace(" ", "")
    stack = []
    current_node = None
    i = 0
    # 定义运算符优先级：*/ 高于 +-
    precedence = {'+':1, '-':1, '*':2, '/':2}

    while i < len(expr):
        char = expr[i]
        # 处理左括号：创建节点并入栈，作为当前节点的父节点
        if char == '(':
            new_node = TreeNode(char)
            if stack:
                parent = stack[-1]
                if not parent.left:
                    parent.left = new_node
                else:
                    parent.right = new_node
            stack.append(new_node)
            current_node = new_node
            i += 1
        # 处理右括号：弹出栈顶，回到父节点层级
        elif char == ')':
            stack.pop()
            current_node = stack[-1] if stack else None
            i += 1
        # 处理多位数操作数
        elif char.isdigit():
            num_str = ""
            while i < len(expr) and expr[i].isdigit():
                num_str += expr[i]
                i += 1
            new_node = TreeNode(int(num_str))
            # 把数字节点挂到当前节点的左/右子节点
            if not current_node.left:
                current_node.left = new_node
            else:
                current_node.right = new_node
        # 处理运算符：根据优先级调整树结构
        elif char in precedence:
            new_node = TreeNode(char)
            # 如果栈顶运算符优先级不低于当前，弹出作为当前节点的父节点
            while stack and stack[-1].value in precedence and precedence[stack[-1].value] >= precedence[char]:
                parent = stack.pop()
                parent.right = new_node
                new_node = parent
            # 把构建好的运算符节点挂到父节点下
            if stack:
                parent = stack[-1]
                if not parent.left:
                    parent.left = new_node
                else:
                    parent.right = new_node
            stack.append(new_node)
            current_node = new_node
            i += 1
    # 栈中最后剩下的就是树的根节点
    return stack[0] if stack else None

3. 节点排序逻辑 #

这个递归函数会遍历整棵树，确保每个节点的左子节点“小于”右子节点，遵循你提到的规则：

• 操作数（数字）的优先级低于任何运算符，所以操作数 < 运算符
• 数字之间直接比较数值大小
• 运算符之间按优先级比较（*// > +/-）

def sortTreeNodes(node):
    if not node:
        return
    # 先递归排序左右子树
    sortTreeNodes(node.left)
    sortTreeNodes(node.right)

    # 定义节点值的排序权重：数字权重0，运算符按优先级设为1或2
    def get_rank(val):
        if isinstance(val, int):
            return 0
        precedence = {'+':1, '-':1, '*':2, '/':2}
        return precedence.get(val, 0)

    # 判断是否需要交换左右子节点
    if node.left and node.right:
        left_val = node.left.value
        right_val = node.right.value
        left_rank = get_rank(left_val)
        right_rank = get_rank(right_val)
        need_swap = False

        # 情况1：都是数字，左值大于右值则交换
        if isinstance(left_val, int) and isinstance(right_val, int):
            if left_val > right_val:
                need_swap = True
        # 情况2：左是运算符，右是数字，交换（数字更小）
        elif isinstance(left_val, str) and isinstance(right_val, int):
            need_swap = True
        # 情况3：都是运算符，左优先级高于右则交换
        elif isinstance(left_val, str) and isinstance(right_val, str):
            if left_rank > right_rank:
                need_swap = True

        if need_swap:
            node.left, node.right = node.right, node.left

4. 按层级打印树（printNodeInLevels） #

用队列实现广度优先遍历，按层输出每个节点的值：

def printNodeInLevels(root):
    if not root:
        print("空树")
        return
    queue = [root]
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.pop(0)
            current_level.append(str(node.value))
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print(f"Level: {' '.join(current_level)}")

测试示例 #

咱们用你提到的表达式((2 * 75) / 4)来测试：

# 构建解析树
expr = "((2 * 75) / 4)"
tree_root = buildParseTree(expr)

# 对树节点进行排序
sortTreeNodes(tree_root)

# 按层打印结果
print("按层级排序后的二叉树：")
printNodeInLevels(tree_root)

输出结果 #

按层级排序后的二叉树：
Level: /
Level: 4 *
Level: 2 75

解释一下结果：原本的根节点/左子节点是*（优先级2），右子节点是4（操作数，权重0），排序后交换了两者的位置；而*的左右子节点2和75已经符合左小右大，所以保持不变。

内容的提问来源于stack exchange，提问作者SriniShine