【数据结构】2——二叉树遍历

数据结构2——二叉树遍历

单纯记录

一、二叉树遍历

1，先序遍历：根左右

     1/   \2     3/ \   / \
4   5 6   7首先访问根节点 1。
然后遍历左子树：
访问根节点 2。
遍历左子树：访问节点 4。
遍历右子树：访问节点 5。
最后遍历右子树：
访问根节点 3。
遍历左子树：访问节点 6。
遍历右子树：访问节点 7。
所以，该二叉树的先序遍历结果为：1 2 4 5 3 6 7。

递归实现

class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef preorderTraversal(root):if root is not None:print(root.value, end=" ")  # 访问根节点preorderTraversal(root.left)  # 递归访问左子树preorderTraversal(root.right)  # 递归访问右子树# 创建节点
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)# 执行先序遍历
preorderTraversal(root)

非递归实现（栈）

def preorderTraversalIterative(root):# 检查根节点是否为空，若为空则直接返回if root is None:return# 初始化栈并将根节点推入栈中stack = [root]# 当栈不为空时循环执行while stack:# 弹出栈顶节点并输出其值node = stack.pop()print(node.value, end=" ")# 先将右子节点推入栈（因为先序遍历是先访问左子节点）if node.right:stack.append(node.right)# 再将左子节点推入栈if node.left:stack.append(node.left)# 使用迭代方法执行先序遍历
preorderTraversalIterative(root)

2.中序遍历：左根右

        1/ \2   3/ \   \4   5   6

递归

class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef inorderTraversal(root):if root is not None:inorderTraversal(root.left)  # 递归访问左子树print(root.value, end=" ")  # 访问根节点inorderTraversal(root.right)  # 递归访问右子树# 创建节点
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)# 执行中序遍历
inorderTraversal(root)

非递归

过程：

• 根节点1入栈，移动到左子节点2。
• 节点2入栈，移动到左子节点4。
• 节点4入栈，由于4没有左子节点，从栈中弹出节点4，访问（打印）节点4。
• 移动到节点4的右子节点5，节点5入栈，由于5没有左子节点，从栈中弹出节点5，访问（打印）节点5。
• 回到节点2，移动到节点2的右子节点5，节点5已经访问过，移动到节点2的右子节点3。
• 节点3入栈，移动到左子节点6。
• 节点6入栈，由于6没有左子节点，从栈中弹出节点6，访问（打印）节点6。
• 回到节点3，由于3没有右子节点，从栈中弹出节点3，访问（打印）节点3。
• 回到节点1，由于1没有右子节点，从栈中弹出节点1，访问（打印）节点1。
• 遍历结束。
• 非递归中序遍历的输出结果为：4, 5, 2, 6, 3, 1

def inorderTraversalIterative(root):stack = []  # 创建一个空栈current = root  # 初始化当前节点为根节点while stack or current:  # 当栈不为空或者当前节点不为空时循环while current:  # 当前节点不为空时，一直向左遍历stack.append(current)  # 将当前节点压入栈中current = current.left  # 移动到左子节点current = stack.pop()  # 弹出栈顶元素作为当前节点print(current.value, end=" ")  # 访问当前节点current = current.right  # 移动到右子节点# 使用迭代方法执行中序遍历
inorderTraversalIterative(root)

3 .后序遍历：左右根

        1/ \2   3/ \   \4   5   6

递归

class TreeNode:def __init__(self, value):self.value = value  # 节点存储的值self.left = None    # 左子节点初始为空self.right = None   # 右子节点初始为空def postorderTraversal(root):# 检查当前节点是否为空if root is not None:# 递归遍历左子树postorderTraversal(root.left)# 递归遍历右子树postorderTraversal(root.right)# 访问根节点print(root.value, end=" ")# 创建具体的二叉树节点
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)# 执行后序遍历
postorderTraversal(root)

非递归（两个栈）

def postorderTraversalIterative(root):if not root:return# stack1 用于存储节点，stack2 用于逆序输出stack1, stack2 = [root], []while stack1:node = stack1.pop()if node:stack2.append(node)# 先压入左子节点，再压入右子节点，保证左子节点在栈内先弹出if node.left:stack1.append(node.left)if node.right:stack1.append(node.right)# 从栈中弹出节点并访问，由于是逆序访问，所以输出顺序是正确的while stack2:node = stack2.pop()print(node.value, end=" ")# 使用迭代方法执行后序遍历
postorderTraversalIterative(root)

二、层次遍历（广度优先遍历）

首先访问根节点，然后是所有子节点，接着是子节点的子节点，以此类推。这种遍历方式通常用于查找最短路径或最小深度。

        1/ \2   3/ \   \4   5   6

按照层次遍历的具体步骤：
创建一个空队列。

• 将根节点1入队。
• 循环开始：
  a. 出队节点1，访问它（打印1）。
  b. 将节点1的左子节点2和右子节点3入队。
• 下一次循环：
  a. 出队节点2，访问它（打印2）。
  b. 将节点2的左子节点4和右子节点5入队。
  c. 出队节点3，访问它（打印3）。
  d. 将节点3的右子节点6入队。
• 继续循环：
  a. 出队节点4，访问它（打印4）。
  b. 出队节点5，访问它（打印5）。
  c. 出队节点6，访问它（打印6）。
• 队列为空，遍历结束。

队列实现

from collections import dequeclass TreeNode:def __init__(self, value):self.value = value  # 节点存储的值self.left = None    # 左子节点初始为空self.right = None   # 右子节点初始为空def levelOrderTraversal(root):if not root:return []result = []  # 存储遍历的结果queue = deque([root])  # 使用deque（双端队列）作为队列while queue:node = queue.popleft()  # 从队列中取出一个节点result.append(node.value)  # 将节点值添加到结果列表中if node.left:queue.append(node.left)  # 将左子节点添加到队列if node.right:queue.append(node.right)  # 将右子节点添加到队列return result# 创建具体的二叉树节点
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)# 执行层次遍历
print(levelOrderTraversal(root))