python 实现binary tree traversal二叉树遍历算法

binary tree traversal二叉树遍历算法介绍

二叉树遍历是树结构中的一种重要操作，它指的是按照某种顺序访问树中的每个节点，且每个节点仅被访问一次。对于二叉树，有三种基本的遍历方式：前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）。此外，还有层次遍历（Level-order Traversal）这种非递归遍历方式。

1. 前序遍历（Preorder Traversal）

前序遍历的顺序是：先访问根节点，然后遍历左子树，最后遍历右子树。

递归实现：

def preorderTraversal(root):if root is None:return []result = [root.val]result.extend(preorderTraversal(root.left))result.extend(preorderTraversal(root.right))return result

非递归实现（使用栈）：

def preorderTraversalIterative(root):if root is None:return []stack, result = [root], []while stack:node = stack.pop()result.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result

2. 中序遍历（Inorder Traversal）

中序遍历的顺序是：先遍历左子树，然后访问根节点，最后遍历右子树。

递归实现：

def inorderTraversal(root):if root is None:return []result = inorderTraversal(root.left)result.append(root.val)result.extend(inorderTraversal(root.right))return result

非递归实现（使用栈）：

def inorderTraversalIterative(root):if root is None:return []stack, result = [], []current = rootwhile current or stack:while current:stack.append(current)current = current.leftcurrent = stack.pop()result.append(current.val)current = current.rightreturn result

3. 后序遍历（Postorder Traversal）

后序遍历的顺序是：先遍历左子树，然后遍历右子树，最后访问根节点。

递归实现：

def postorderTraversal(root):if root is None:return []result = postorderTraversal(root.left)result.extend(postorderTraversal(root.right))result.append(root.val)return result

非递归实现（使用栈，稍微复杂一些，需要记录节点是否已访问过其右子树）：

def postorderTraversalIterative(root):if root is None:return []stack, result, visited = [root], [], set()while stack:node = stack[-1]if (node.left and node.left not in visited) or (node.right and node.right not in visited):if node.right:stack.append(node.right)visited.add(node.right)if node.left:stack.append(node.left)visited.add(node.left)else:stack.pop()result.append(node.val)return result[::-1]  # 因为是逆序入栈的，所以需要反转结果

4. 层次遍历（Level-order Traversal）

层次遍历使用队列来实现，按照从上到下、从左到右的顺序访问节点。

实现：

from collections import dequedef levelOrderTraversal(root):if root is None:return []queue, result = deque([root]), []while queue:node = queue.popleft()result.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return result

以上是二叉树遍历的几种基本方式及其实现。

binary tree traversal二叉树遍历算法python实现样例

二叉树遍历算法有三种：前序遍历、中序遍历和后序遍历。下面分别介绍这三种遍历算法的实现。

1. 前序遍历（Preorder Traversal）：先访问根节点，再递归地遍历左子树和右子树。

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef preorderTraversal(root):if root is None:return []result = []result.append(root.val)result.extend(preorderTraversal(root.left))result.extend(preorderTraversal(root.right))return result

2. 中序遍历（Inorder Traversal）：先递归地遍历左子树，再访问根节点，最后递归地遍历右子树。

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorderTraversal(root):if root is None:return []result = []result.extend(inorderTraversal(root.left))result.append(root.val)result.extend(inorderTraversal(root.right))return result

3. 后序遍历（Postorder Traversal）：先递归地遍历左子树和右子树，再访问根节点。

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef postorderTraversal(root):if root is None:return []result = []result.extend(postorderTraversal(root.left))result.extend(postorderTraversal(root.right))result.append(root.val)return result

这些算法可以通过传入根节点的对象（例如实例化的 TreeNode 对象）来使用。每种遍历算法的返回值是一个列表，包含了按照对应顺序遍历的节点值。