Python實現二叉樹相關算法

guyan0319 發布于2019-07-31 10:06 / 1243人閱讀

摘要：節點定義二叉樹定義先序遍歷遞歸方式先序遍歷，遞歸方式非遞歸方式先序遍歷，非遞歸方式中序遍歷遞歸方式中序遍歷，遞歸方式非遞歸方式中序遍歷，非遞歸方式后序遍歷遞歸方式后序遍歷，遞歸方式非遞歸方式后序遍歷，非遞歸方式分層遍歷分層遍歷，使用隊

節點定義

class Node(object):
    def __init__(self, left_child, right_child, value):
        self._left_child = left_child
        self._right_child = right_child
        self._value = value

    @property
    def left_child(self):
        return self._left_child

    @property
    def right_child(self):
        return self._right_child

    @left_child.setter
    def left_child(self, value):
        self._left_child = value

    @right_child.setter
    def right_child(self, value):
        self._right_child = value

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self, value):
        self._value = value

二叉樹定義

class Tree(object):
    def __init__(self, value):
        self._root = Node(None, None, value=value)

    @property
    def root(self):
        return self._root

先序遍歷 遞歸方式

"""
先序遍歷，遞歸方式
"""
def preoder(root):
    if not isinstance(root, Node):
        return None
    preorder_res = []
    if root:
        preorder_res.append(root.value)
        preorder_res += preoder(root.left_child)
        preorder_res += preoder(root.right_child)

    return preorder_res

非遞歸方式

"""
先序遍歷，非遞歸方式
"""
def pre_order_not_recursion(root):
    if not isinstance(root, Node):
        return None

    stack = [root]
    result = []
    while stack:
        node = stack.pop(-1)
        if node:
            result.append(node.value)
            stack.append(node.right_child)
            stack.append(node.left_child)
    return result

中序遍歷 遞歸方式

"""
中序遍歷，遞歸方式
"""
def middle_order(root):
    if not isinstance(root, Node):
        return None
    middle_res = []
    if root:
        middle_res += middle_order(root.left_child)
        middle_res.append(root.value)
        middle_res += middle_order(root.right_child)
    return middle_res

非遞歸方式

"""
中序遍歷，非遞歸方式
"""
def middle_order_bot_recursion(root):
    if not isinstance(root, Node):
        return None

    result = []
    stack = [root.right_child, root.value, root.left_child]
    while stack:
        temp = stack.pop(-1)
        if temp:
            if isinstance(temp, Node):
                stack.append(temp.right_child)
                stack.append(temp.value)
                stack.append(temp.left_child)
            else:
                result.append(temp)
    return result

后序遍歷 遞歸方式

"""
后序遍歷，遞歸方式
"""
def post_order(root):
    if not isinstance(root, Node):
        return None
    post_res = []
    if root:
        post_res += post_order(root.left_child)
        post_res += post_order(root.right_child)
        post_res.append(root.value)
    return post_res

非遞歸方式

"""
后序遍歷，非遞歸方式
"""
def post_order_not_recursion(root):
    if not isinstance(root, Node):
        return None

    stack = [root.value, root.right_child, root.left_child]
    result = []

    while stack:
        temp_node = stack.pop(-1)
        if temp_node:
            if isinstance(temp_node, Node):
                stack.append(temp_node.value)
                stack.append(temp_node.right_child)
                stack.append(temp_node.left_child)
            else:
                result.append(temp_node)

    return result

分層遍歷

"""
分層遍歷，使用隊列實現
"""
def layer_order(root):
    if not isinstance(root, Node):
        return None

    queue = [root.value, root.left_child, root.right_child]
    result = []
    while queue:
        temp = queue.pop(0)
        if temp:
            if isinstance(temp, Node):
                queue.append(temp.value)
                queue.append(temp.left_child)
                queue.append(temp.right_child)
            else:
                result.append(temp)

    return result

計算二叉樹結點個數

"""
計算二叉樹結點個數，遞歸方式
NodeCount(root) = NodeCount(root.left_child) + NodeCount(root.right_child)
"""
def node_count(root):
    if root and not isinstance(root, Node):
        return None

    if root:
        return node_count(root.left_child) + node_count(root.right_child) + 1
    else:
        return 0


"""
計算二叉樹結點個數，非遞歸方式
借用分層遍歷計算
"""
def node_count_not_recursion(root):
    if root and not isinstance(root, Node):
        return None

    return len(layer_order(root))

計算二叉樹深度

"""
計算二叉樹深度，遞歸方式
tree_deep(root) = 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))
"""
def tree_deep(root):
    if root and not isinstance(root, Node):
        return None

    if root:
        return 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))
    else:
        return 0

"""
計算二叉樹深度，非遞歸方法
同理參考分層遍歷的思想
"""
def tree_deep_not_recursion(root):
    if root and not isinstance(root, Node):
        return None
    result = 0
    queue = [(root, 1)]
    while queue:
        temp_node, temp_layer = queue.pop(0)
        if temp_node:
            queue.append((temp_node.left_child, temp_layer+1))
            queue.append((temp_node.right_child, temp_layer+1))
            result = temp_layer + 1

    return result-1

計算二叉樹第k層節點個數

"""
計算二叉樹第k層節點個數，遞歸方式
kth_node_count(root, k) = kth_node_count(root.left_count, k-1) + kth_node_count(root.right_count, k-1)
"""
def kth_node_count(root, k):
    if root and not isinstance(root, Node):
        return None

    if not root or k <= 0:
        return 0
    if k == 1:
        return 1
    return kth_node_count(root.left_child, k-1) + kth_node_count(root.right_child, k-1)

"""
計算二叉樹第K層節點個數，非遞歸方式
"""
def kth_node_count_not_recursion(root, k):
    if root and not isinstance(root, Node):
        return None

    if not root or k <= 0:
        return 0

    if k == 1:
        return 1

    queue = [(root, 1)]
    result = 0
    while queue:
        temp_node, temp_layer = queue.pop(0)
        if temp_node:
            if temp_layer == k:
                result += 1
            elif temp_layer > k:
                return result
            else:
                queue.append((temp_node.left_child, temp_layer+1))
                queue.append((temp_node.right_child, temp_layer+1))
    return result

計算二叉樹葉子節點個數

"""
計算二叉樹葉子節點個數，遞歸方式
關鍵點是葉子節點的判斷標準，左右孩子皆為None
"""
def leaf_count(root):
    if root and not isinstance(root, Node):
        return None

    if not root:
        return 0
    if not root.left_child and not root.right_child:
        return 1

    return leaf_count(root.left_child) + leaf_count(root.right_child)

判斷兩個二叉樹是不是相同

"""
判斷兩個二叉樹是不是相同，遞歸方式
isSame(root1, root2) = (root1.value == root2.value)
                    and isSame(root1.left, root2.left) 
                    and isSame(root1.right, root2.right)
"""
def is_same_tree(root1, root2):
    if not root1 and not root2:
        return True

    if root1 and root2:
        return (root1.value == root2.value) and 
               is_same_tree(root1.left_child, root2.left_child) and 
               is_same_tree(root1.right_child, root2.right_child)
    else:
        return False

判斷是否為二分查找樹BST

"""
判斷是否為二分查找樹BST，遞歸方式
二分查找樹的定義搞清楚，二分查找樹的中序遍歷結果為遞增序列
"""
def is_bst_tree(root):
    if root and not isinstance(root, Node):
        return None

    def is_asc(order):
        for i in range(len(order)-1):
            if order[i] > order[i+1]:
                return False
        return True

    return is_asc(middle_order_bot_recursion(root))

測試方法

if __name__ == "__main__":
    tree = Tree(1)
    tree1 = Tree(1)
    node6 = Node(None, None, 7)
    node5 = Node(None, None, 6)
    node4 = Node(None, None, 5)
    node3 = Node(None, None, 4)
    node2 = Node(node5, node6, 3)
    node1 = Node(node3, node4, 2)
    tree.root.left_child = node1
    tree.root.right_child = node2
    tree1.root.left_child = node2
    tree1.root.right_child = node2
    print(is_bst_tree(tree.root))

GPU云服務器云服務器二叉樹算法實現二叉樹最優二叉樹算法圖 python二叉樹

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/43252.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
Python_數據結構與算法

摘要：什么是數據結構數據的組織結構方式一組數據如何存儲，基本數據類型，，的封裝算法與數據結構的區別數據結構只是靜態的描述了數據元素之間的關系。高效的程序需要在數據結構的基礎上設計和選擇算法。數據結構和算法基礎什么是數據結構和算法：兵法，計算的方法。算法是獨立存在的一種解決問題的方法和思想。算法的特征：輸入：算法具有0個或多個輸入輸出：算法至少有1個或多個輸出有窮性：算法在有限的...

Kylin_Mountain 2019-07-30 16:02 評論0 收藏0
Python數據結構——二叉堆的實現

摘要：二叉堆的有趣之處在于，其邏輯結構上像二叉樹，卻是用非嵌套的列表來實現。二叉堆結構性質為了更好地實現堆，我們采用二叉樹。圖完全二叉樹有意思的是我們用單個列表就能實現完全樹。下列所示的代碼是完全二叉堆的實現。優先隊列的二叉堆實現在前面的章節里我們學習了先進先出（FIFO）的數據結構：隊列（Queue）。隊列有一種變體叫做優先隊列（Priority Queue）。優先隊列的出隊（Dequ...

stackfing 2019-07-24 18:19 評論0 收藏0

發表評論

登陸后可評論

0條評論

guyan0319

男|高級講師

我要關注我要私信

TA的文章

程序人生 - 祝賀登榜《數據結構與算法領域內容榜》NO.29

閱讀 810·2021-09-06 15:02
Javascript運行機制

閱讀 2451·2019-08-30 15:43
代碼質量把控和項目進度之間的平衡

閱讀 2175·2019-08-30 11:26
帶著問題學習webpack

閱讀 2383·2019-08-26 12:12
一年前端女生面試經驗分享

閱讀 3551·2019-08-23 18:24
node-blog：用 node 搭建的個人開源博客

閱讀 3270·2019-08-23 18:16
JavaScript中的繼承

閱讀 704·2019-08-23 17:02
ES6箭頭函數

閱讀 2254·2019-08-23 15:34

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

Python實現二叉樹相關算法

相關文章

樹和樹的算法

樹和樹的算法

Python_數據結構與算法

Python數據結構——二叉堆的實現

發表評論

0條評論

guyan0319

男|高級講師

TA的文章

程序人生 - 祝賀登榜《數據結構與算法領域內容榜》NO.29

Javascript運行機制

代碼質量把控和項目進度之間的平衡

帶著問題學習webpack

一年前端女生面試經驗分享

node-blog：用 node 搭建的個人開源博客

JavaScript中的繼承

ES6箭頭函數

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

Python實現二叉樹相關算法

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！