Python二叉樹怎么實現(xiàn)

本篇內(nèi)容介紹了“Python二叉樹怎么實現(xiàn)”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

Python實現(xiàn)二叉樹

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

以下是一個簡單的二叉樹實現(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類定義了一個節(jié)點，包含數(shù)據(jù)元素data，以及左右子節(jié)點指針left和right。insert方法用于向二叉樹中插入節(jié)點，find方法用于查找二叉樹中是否存在特定節(jié)點，inorder_traversal方法用于對二叉樹進行中序遍歷。

下面是如何使用這個Node類來創(chuàng)建一個二叉樹：

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

# 查找節(jié)點

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)建了一個根節(jié)點root，然后使用insert方法向樹中插入節(jié)點，最后使用find方法查找節(jié)點并使用inorder_traversal方法對二叉樹進行中序遍歷。

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

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

在這個示例中，我們新增了delete方法來刪除指定的節(jié)點；minimum方法來查找樹中的最小節(jié)點；is_bst方法來判斷當前樹是否為二叉搜索樹；height方法來計算樹的深度。

我們可以用以下代碼來測試新增的方法：

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

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

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

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

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

最后附上完整的二叉樹類實現(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)建二叉樹
    root = Node(50)
    root.insert(30)
    root.insert(20)
    root.insert(40)
    root.insert(70)
    root.insert(60)
    root.insert(80)

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

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

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

運行代碼后，可以得到以下輸出：

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

這個示例包含了插入、查找、刪除、遍歷、判斷是否為二叉搜索樹和計算樹的深度等。

“Python二叉樹怎么實現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！