python 二叉樹深度優先搜索和廣度優先搜索

kaka 發布于2019-07-31 11:18 / 1484人閱讀

摘要：左子樹右子樹非空左孩子入隊非空右孩子入隊如果根節點為空，則返回空列表模擬一個隊列儲存節點首先將根節點入隊列表為空時，循環終止非空左孩子入隊非空右孩子入隊

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廣度優先

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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