Pythonでバイナリツリーを実装する方法

Python によるバイナリ ツリーの実装

Python は、バイナリ ツリー ノード クラスを定義することで、オブジェクト指向プログラミングを使用してバイナリ ツリーを実装できます。各ノードには、データ要素、左右の子ノード ポインター、およびノー​​ドの挿入、ノードの検索、ノードの削除などのいくつかの操作メソッドが含まれています。

以下は、単純なバイナリ ツリーの実装例です:

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 クラスは、データ要素データと左右の子ノード ポインターを含むノードを定義します。そしてそのとおりです。 insert メソッドはバイナリ ツリーにノードを挿入するために使用され、find メソッドはバイナリ ツリーに特定のノードが存在するかどうかを確認するために使用され、inorder_traversal メソッドはバイナリ ツリーの順序トラバーサルを実行するために使用されます。

この Node クラスを使用してバイナリ ツリーを作成する方法は次のとおりです:

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

# 查找节点

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]

上記のコードでは、最初にルート ノード root が作成され、次に、insert メソッドを使用して、ノードをツリーに追加し、最後に find メソッドを使用してノードを見つけ、inorder_traversal メソッドを使用してバイナリ ツリーの順序トラバーサルを実行します。

二分木には、挿入、検索、および走査の方法に加えて、ノードの削除、二分探索木であるかどうかの決定、木の深さの計算などの他の操作方法もあります。以下は、もう少し完全なバイナリ ツリーのサンプル コードです:

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 メソッド、ツリー内の最小のノードを見つけるための minimum メソッド、is_bst メソッドを追加しました。現在のツリーが二分探索ツリーであるかどうかを判断するには、高さ方法を使用してツリーの深さを計算します。

次のコードを使用して、新しいメソッドをテストできます:

# 创建二叉树
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)

# 删除节点
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))

この方法で、比較的完全なバイナリ ツリーの実装が完了し、Python でオブジェクト指向プログラミングを使用する方法も示しました。データ構造を実装するためのアイデア。

最後に、完全なバイナリ ツリー クラス実装コードが添付されます:

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__':
    # 创建二叉树
    root = Node(50)
    root.insert(30)
    root.insert(20)
    root.insert(40)
    root.insert(70)
    root.insert(60)
    root.insert(80)

    # 删除节点
    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))

コードを実行すると、次の出力が得られます:

ノード 20 の削除 :
[30, 40, 50, 60, 70, 80]
Is it a BST?: True
Tree height: 3

この例挿入と検索、削除、トラバース、二分探索木かどうかの判断、木の深さの計算などが含まれます。

以上がPythonでバイナリツリーを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。