首页python 实现二叉树遍历

python 实现二叉树遍历

时间: 2024-12-26 21:05:33 浏览: 43

在Python中，二叉树的遍历主要有三种基本方法：前序遍历、中序遍历和后序遍历。这三种遍历可以递归实现，也可以采用迭代的方式，通常会配合栈数据结构。 1. **前序遍历** (Preorder Traversal): 先访问根节点，然后递归地遍历左子树，最后遍历右子树。递归形式如`def preorder(root)`，迭代形式可通过栈存储待访问节点。 ```python # 递归方式 def preorder_traversal(node): if node is not None: print(node.val) # 访问节点值 preorder_traversal(node.left) # 左子树 preorder_traversal(node.right) # 右子树 # 迭代方式 def preorder_iterative(root): stack, output = [root], [] while stack: root = stack.pop() if root is not None: output.append(root.val) stack.extend([root.right, root.left]) return output ``` 2. **中序遍历** (Inorder Traversal): 先递归地遍历左子树，然后访问根节点，最后遍历右子树。递归形式同上，迭代也类似，只是访问节点的顺序不同。 3. **后序遍历** (Postorder Traversal): 先递归地遍历左右子树，最后访问根节点。递归形式是`def postorder_traversal(node)`，迭代需要两个栈： ```python def postorder_iterative(root): stack1, stack2, output = [root], [], [] while stack1 or stack2: while stack1 and stack1[-1].val is not None: pop_node = stack1.pop() stack2.append(pop_node) if pop_node.left is not None: stack1.append(pop_node.left) else: output.append(pop_node.val) if stack2: stack1.pop() # 移除已经访问过的节点，准备访问右子树 stack1.append(stack2.pop()) return output ```

阅读全文