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

kaka 发布于2019-07-31 11:18 / 1477人阅读

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

class TreeNode:

def __init__(self, value=None, left=None, right=None):
    self.value = value
    self.left = left  # 左子树
    self.right = right  # 右子树

node1 = TreeNode("A",

             TreeNode("B",
                      TreeNode("D"),
                      TreeNode("E")
                      ),
             TreeNode("C",
                      TreeNode("F"),
                      TreeNode("G")
                      )
             )

def preTraverse(root):

if root is None:
    return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)

def midTraverse(root):

if root is None:
    return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)

def afterTraverse(root):

if root is None:
    return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)

def dfs(root):

res = []
if root is None:
    return res
q = []
q.append(root)
while len(q) > 0:
    r = q.pop()
    print(r.value)
    if r.left is not None:
        # 非空左孩子入队
        q.append(r.left)
    if r.right is not None:
        # 非空右孩子入队
        q.append(r.right)
    res.append(r.value)
return res

def bfs(root):

# write your code here
res = []
# 如果根节点为空，则返回空列表
if root is None:
    return res
# 模拟一个队列储存节点
q = []
# 首先将根节点入队
q.append(root)
# 列表为空时，循环终止
while len(q) > 0:
    length = len(q)
    r = q.pop(0)
    print(r.value)
    if r.left is not None:
        # 非空左孩子入队
        q.append(r.left)
    if r.right is not None:
        # 非空右孩子入队
        q.append(r.right)
    res.append(r.value)
return res

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

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

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

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

树和树的算法

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

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

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

PiscesYE 2019-07-30 17:45 评论0 收藏0
前端也需要好好的精进自己的算法

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

hersion 2019-08-23 10:36 评论0 收藏0