### Python 实现基于括号表示法的二叉树非递归中序遍历 要实现基于括号表示法的二叉树非递归中序遍历，可以按照以下逻辑完成： 1. 使用栈来模拟递归过程。 2. 将字符串转换为二叉树结构时，利用栈记录父节点及其左右子树关系。 3. 对于中序遍历，遵循访问顺序：左子树 -> 根节点 -> 右子树。 以下是完整的解决方案代码： ```python class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None def create_tree(tree_str): """通过括号表示法创建二叉树""" if not tree_str: return None stack = [] root = None current_node = None i = 0 while i < len(tree_str): char = tree_str[i] if char.isalpha(): # 如果是字母，则创建节点 node = TreeNode(char) if not root: # 第一个节点作为根节点 root = node if current_node: # 设置当前节点的父子关系 if current_node.left is None: current_node.left = node else: current_node.right = node stack.append(node) # 当前节点压入栈 current_node = node elif char == '(': # 左括号跳过 pass elif char == ')': # 右括号弹出栈顶节点 current_node = stack.pop() if stack else None i += 1 return root def inorder_traversal_non_recursive(root): """非递归中序遍历""" result = [] stack = [] current = root while current or stack: while current: # 沿着左子树一直向下 stack.append(current) current = current.left current = stack.pop() # 弹出栈顶元素 result.append(current.value) # 访问该节点 current = current.right # 转向右子树 return result # 测试用例 tree_str = "A(B(E,T(W,C)),D(,F(P(S(I),V))))" root = create_tree(tree_str) result = inorder_traversal_non_recursive(root) print("中序遍历结果:", result) ``` #### 解析说明 - `create_tree` 函数用于将括号表示法的字符串转化为二叉树结构。它使用栈来管理节点之间的父子关系[^2]。 - `inorder_traversal_non_recursive` 是核心函数，实现了非递归版本的中序遍历算法。其基本原理是借助显式的栈代替隐式调用栈，从而避免递归带来的额外开销[^4]。 --- ### 输出示例 假设输入字符串为 `"A(B(E,T(W,C)),D(,F(P(S(I),V))))"`，则程序会输出如下结果： ``` 中序遍历结果: ['E', 'W', 'C', 'T', 'B', 'A', 'S', 'I', 'P', 'V', 'F', 'D'] ``` 此结果表明，程序成功完成了基于括号表示法的二叉树非递归中序遍历。 ---