资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/python 二叉树深度优先搜索和广度优先搜索

python 二叉树深度优先搜索和广度优先搜索

kaka / 1551人阅读

摘要：左子树右子树非空左孩子入队非空右孩子入队如果根节点为空，则返回空列表模拟一个队列储存节点首先将根节点入队列表为空时，循环终止非空左孩子入队非空右孩子入队

class TreeNode:

</>复制代码 
  1. def __init__(self, value=None, left=None, right=None):
  2.     self.value = value
  3.     self.left = left  # 左子树
  4.     self.right = right  # 右子树

node1 = TreeNode("A",

</>复制代码 
  1.              TreeNode("B",
  2.                       TreeNode("D"),
  3.                       TreeNode("E")
  4.                       ),
  5.              TreeNode("C",
  6.                       TreeNode("F"),
  7.                       TreeNode("G")
  8.                       )
  9.              )

def preTraverse(root):

</>复制代码 
  1. if root is None:
  2.     return
  3. print(root.value)
  4. preTraverse(root.left)
  5. preTraverse(root.right)

def midTraverse(root):

</>复制代码 
  1. if root is None:
  2.     return
  3. midTraverse(root.left)
  4. print(root.value)
  5. midTraverse(root.right)

def afterTraverse(root):

</>复制代码 
  1. if root is None:
  2.     return
  3. afterTraverse(root.left)
  4. afterTraverse(root.right)
  5. print(root.value)

def dfs(root):

</>复制代码 
  1. res = []
  2. if root is None:
  3.     return res
  4. q = []
  5. q.append(root)
  6. while len(q) > 0:
  7.     r = q.pop()
  8.     print(r.value)
  9.     if r.left is not None:
  10.         # 非空左孩子入队
  11.         q.append(r.left)
  12.     if r.right is not None:
  13.         # 非空右孩子入队
  14.         q.append(r.right)
  15.     res.append(r.value)
  16. return res

def bfs(root):

</>复制代码 
  1. # write your code here
  2. res = []
  3. # 如果根节点为空，则返回空列表
  4. if root is None:
  5.     return res
  6. # 模拟一个队列储存节点
  7. q = []
  8. # 首先将根节点入队
  9. q.append(root)
  10. # 列表为空时，循环终止
  11. while len(q) > 0:
  12.     length = len(q)
  13.     r = q.pop(0)
  14.     print(r.value)
  15.     if r.left is not None:
  16.         # 非空左孩子入队
  17.         q.append(r.left)
  18.     if r.right is not None:
  19.         # 非空右孩子入队
  20.         q.append(r.right)
  21.     res.append(r.value)
  22. return res

dfs(node1)
print("-------------------")
bfs(node1)

GPU云服务器 云服务器 广度优先搜索 广度优先搜索算法代码 深度优先搜索 python广度优先

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44984.html

相关文章

  • 树和树的算法

    摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。 树和树的算法 一、树 1.1 树的概念 树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

    RaoMeng 评论0 收藏0

  • 树和树的算法

    摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。 树和树的算法 一、树 1.1 树的概念 树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

    PiscesYE 评论0 收藏0

  • 前端也需要好好的精进自己的算法

    摘要：算法前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。 算法 前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。欢迎大家关注。 数组和堆栈 数组去重 旋转数组 如何快速找出两个数之和等于某一个值的两个数？ 快排 排序算法大总结 快速找到数组中的最大值 多维数组的展开 二分查找 有效的括...

    hersion 评论0 收藏0

发表评论

登陆后可评论

0条评论

kaka

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<