快捷導(dǎo)航

Python學(xué)習(xí)之二叉樹(shù)實(shí)現(xiàn)的示例詳解

更新時(shí)間：2023年04月10日 15:14:03 作者：逃逸的卡路里

這篇文章主要為大家詳細(xì)介紹了Python實(shí)現(xiàn)二叉樹(shù)的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的小伙伴可以了解一下

Python實(shí)現(xiàn)二叉樹(shù)

Python實(shí)現(xiàn)二叉樹(shù)可以使用面向?qū)ο缶幊痰姆绞剑ㄟ^(guò)定義二叉樹(shù)節(jié)點(diǎn)類來(lái)實(shí)現(xiàn)。每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素、左右子節(jié)點(diǎn)指針和一些操作方法，如插入節(jié)點(diǎn)、查找節(jié)點(diǎn)、刪除節(jié)點(diǎn)等。

以下是一個(gè)簡(jiǎn)單的二叉樹(shù)實(shí)現(xiàn)示例：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return str(data) + " Not Found"
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return str(data) + " Not Found"
            return self.right.find(data)
        else:
            return str(self.data) + " is found"

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

在上述代碼中，Node類定義了一個(gè)節(jié)點(diǎn)，包含數(shù)據(jù)元素data，以及左右子節(jié)點(diǎn)指針left和right。insert方法用于向二叉樹(shù)中插入節(jié)點(diǎn)，find方法用于查找二叉樹(shù)中是否存在特定節(jié)點(diǎn)，inorder_traversal方法用于對(duì)二叉樹(shù)進(jìn)行中序遍歷。

下面是如何使用這個(gè)Node類來(lái)創(chuàng)建一個(gè)二叉樹(shù)：

root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 查找節(jié)點(diǎn)

print(root.find(70)) # Output: 70 is found
print(root.find(90)) # Output: 90 Not Found

# 中序遍歷
print(root.inorder_traversal(root)) # Output: [20, 30, 40, 50, 60, 70, 80]

在上述代碼中，首先創(chuàng)建了一個(gè)根節(jié)點(diǎn)root，然后使用insert方法向樹(shù)中插入節(jié)點(diǎn)，最后使用find方法查找節(jié)點(diǎn)并使用inorder_traversal方法對(duì)二叉樹(shù)進(jìn)行中序遍歷。

除了插入、查找和遍歷方法，二叉樹(shù)還有其他的操作方法，如刪除節(jié)點(diǎn)、判斷是否為二叉搜索樹(shù)、計(jì)算樹(shù)的深度等。下面是一個(gè)稍微完整一些的二叉樹(shù)示例代碼：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

在這個(gè)示例中，我們新增了delete方法來(lái)刪除指定的節(jié)點(diǎn)；minimum方法來(lái)查找樹(shù)中的最小節(jié)點(diǎn)；is_bst方法來(lái)判斷當(dāng)前樹(shù)是否為二叉搜索樹(shù)；height方法來(lái)計(jì)算樹(shù)的深度。

我們可以用以下代碼來(lái)測(cè)試新增的方法：

# 創(chuàng)建二叉樹(shù)
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 刪除節(jié)點(diǎn)
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))

# 判斷是否為二叉搜索樹(shù)
print("Is it a BST?:", root.is_bst())

# 計(jì)算樹(shù)的深度
print("Tree height:", root.height(root))

這樣我們就完成了一個(gè)比較完整的二叉樹(shù)的實(shí)現(xiàn)，同時(shí)也演示了如何在Python中使用面向?qū)ο缶幊趟枷雭?lái)實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)。

最后附上完整的二叉樹(shù)類實(shí)現(xiàn)代碼：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def find(self, data):
        if data < self.data:
            if self.left is None:
                return None
            return self.left.find(data)
        elif data > self.data:
            if self.right is None:
                return None
            return self.right.find(data)
        else:
            return self

    def delete(self, data):
        if self is None:
            return self

        if data < self.data:
            self.left = self.left.delete(data)
        elif data > self.data:
            self.right = self.right.delete(data)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp
            temp = self.right.minimum()
            self.data = temp.data
            self.right = self.right.delete(temp.data)
        return self

    def minimum(self):
        if self.left is None:
            return self
        return self.left.minimum()

    def is_bst(self):
        if self.left:
            if self.left.data > self.data or not self.left.is_bst():
                return False

        if self.right:
            if self.right.data < self.data or not self.right.is_bst():
                return False

        return True

    def height(self, node):
        if node is None:
            return 0

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def inorder_traversal(self, root):
        res = []
        if root:
            res = self.inorder_traversal(root.left)
            res.append(root.data)
            res = res + self.inorder_traversal(root.right)
        return res

if __name__ == '__main__':
    # 創(chuàng)建二叉樹(shù)
    root = Node(50)
    root.insert(30)
    root.insert(20)
    root.insert(40)
    root.insert(70)
    root.insert(60)
    root.insert(80)

    # 刪除節(jié)點(diǎn)
    print("Deleting node 20:")
    root.delete(20)
    print(root.inorder_traversal(root))

    # 判斷是否為二叉搜索樹(shù)
    print("Is it a BST?:", root.is_bst())

    # 計(jì)算樹(shù)的深度
    print("Tree height:", root.height(root))

運(yùn)行代碼后，可以得到以下輸出：

Deleting node 20:
[30, 40, 50, 60, 70, 80]
Is it a BST?: True
Tree height: 3

這個(gè)示例包含了插入、查找、刪除、遍歷、判斷是否為二叉搜索樹(shù)和計(jì)算樹(shù)的深度等。希望對(duì)看到的小伙伴有幫助。

到此這篇關(guān)于Python學(xué)習(xí)之二叉樹(shù)實(shí)現(xiàn)的示例詳解的文章就介紹到這了,更多相關(guān)Python二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: