当前位置: 首页 > article >正文

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

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

单纯记录


文章目录

  • 数据结构2——二叉树遍历
  • 一、二叉树遍历
    • 1,先序遍历:根左右
      • 递归实现
      • 非递归实现(栈)
    • 2.中序遍历:左根右
      • 递归
      • 非递归
    • 3 .后序遍历:左右根
      • 递归
      • 非递归(两个栈)
  • 二、层次遍历(广度优先遍历)
    • 队列实现


一、二叉树遍历

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 = value
        self.left = None
        self.right = None

def 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 = value
        self.left = None
        self.right = None

def 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 deque

class 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))

http://www.kler.cn/a/298972.html

相关文章:

  • 如何在window 使用 conda 环境下载大模型
  • 读书笔记~管理修炼-缄默效应
  • 了解RPC
  • UE5 移植Editor或Developer模块到Runtime
  • 全脐点曲面当且仅当平面或者球面的一部分
  • uniapp开发app,cover-view不能隐藏,使用v-if,v-show都不行的解决办法
  • 用hiredis连接redis
  • 如何优化谷歌排名更有效?
  • Linux之Shell命令
  • 【YouTube采集】按搜索关键词批量爬取视频数据,并封装成exe界面软件!
  • ubuntu使用命令行查看硬件信息
  • STM32 的 CAN 通讯全攻略
  • io多路复用
  • cross-plateform 跨平台应用程序-06-uni-app 介绍
  • Spring Boot 执行流程已经 负载均衡执行流程图
  • java实现文本相似度计算
  • 基于C#的UDP协议消息传输
  • sql中索引查看是否生效
  • 计算机网络 --- 【1】欢迎来到计算机网络/计算机网络基本概念/计算机网络、互连网、互联网的区别
  • Springcould -第一个Eureka应用 --- day02
  • Apache POI用法
  • [网鼎杯 2020 朱雀组]Nmap 历程记录
  • Java 远程执行服务器上的命令
  • HP电脑如何启动硬件检测
  • 数据结构应用实例(六)——最短路径
  • CCF刷题计划——坐标变换(其二)(前缀和)