【算法第十一天7.25】二叉树前、中、后递归、非递归遍历

**二叉树前、中、后递归、非递归遍历**

在计算机科学中，二叉树是一种常见的数据结构，它由一个根节点和若干个子树组成。二叉树的遍历是指按照某种顺序访问每个结点的过程。在本文中，我们将讨论二叉树前、中、后递归、非递归遍历的实现。

### 前序递归遍历前序递归遍历是指先访问根节点，然后再访问左子树和右子树。这种方式可以使用递归函数来实现。

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef preorder_traversal(root):
 """
 前序递归遍历 :param root: 二叉树的根节点 :return: 遍历结果 """
 if root is not None:
 print(root.value) # 访问根节点 preorder_traversal(root.left) # 访问左子树 preorder_traversal(root.right) # 访问右子树# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("前序递归遍历:")
preorder_traversal(root)

def inorder_traversal(root):
 """
 中序递归遍历 :param root: 二叉树的根节点 :return: 遍历结果 """
 if root is not None:
 inorder_traversal(root.left) # 访问左子树 print(root.value) # 访问根节点 inorder_traversal(root.right) # 访问右子树# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("中序递归遍历:")
inorder_traversal(root)

def postorder_traversal(root):
 """
 后序递归遍历 :param root: 二叉树的根节点 :return: 遍历结果 """
 if root is not None:
 postorder_traversal(root.left) # 访问左子树 postorder_traversal(root.right) # 访问右子树 print(root.value) # 访问根节点# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("后序递归遍历:")
postorder_traversal(root)

def preorder_non_recursive(root):
 """
 前序非递归遍历 :param root: 二叉树的根节点 :return: 遍历结果 """
 if root is None:
 return stack = [root]
 while len(stack) >0:
 node = stack.pop()
 print(node.value) # 访问根节点 if node.right is not None:
 stack.append(node.right)
 if node.left is not None:
 stack.append(node.left)

# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("前序非递归遍历:")
preorder_non_recursive(root)

def inorder_non_recursive(root):
 """
 中序非递归遍历 :param root: 二叉树的根节点 :return: 遍历结果 """
 if root is None:
 return stack = []
 while True:
 while root is not None:
 stack.append(root)
 root = root.left # 访问左子树 node = stack.pop()
 print(node.value) # 访问根节点 root = node.right # 访问右子树 if len(stack) ==0 and root is None:
 break# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("中序非递归遍历:")
inorder_non_recursive(root)

def postorder_non_recursive(root):
 """
 后序非递归遍历 :param root: 二叉树的根节点 :return: 遍历结果 """
 if root is None:
 return stack = [root]
 while len(stack) >0:
 node = stack.pop()
 print(node.value) # 访问根节点 if node.left is not None:
 stack.append(node.left)
 if node.right is not None:
 stack.append(node.right)

# 示例代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("后序非递归遍历:")
postorder_non_recursive(root)