バイナリツリー実装



バイナリツリーとは?


データ構造の1つとして、複数のツリー構造がありますが、ここで使用するツリーには、サイズ別のバイナリツリーが表示されます.
バイナリツリーを使用すると、データ値をより効率的に検索できます.
たとえば、50, 100, 150, 250, 300をランダムに混合するとバイナリツリーに入れ、

上の図に示すように、データが含まれています.木の上の節点より大きい水面を右に、小さいと左に移動します.

    def search(self, target):
        if target == self.node:
            return True
        elif target > self.node:
            if self.right:
                self.right.search(target)
            else:
                return False
        else:
            if self.left:
                self.left.search(target)
            else:
                return False

#delete def
def deleteNode(tree, elem):
    if tree is None:
        print("No Number")
        return tree
    if tree.node > elem:
        tree.left = deleteNode(tree.left, elem)
    elif tree.node < elem:
        tree.right = deleteNode(tree.right, elem)
    else:
        print("Success")
        if tree.right is None:
            tmp = tree.left
            tree = None
            return tmp
        elif tree.left is None:
            tmp = tree.right
            tree = None
            return tmp
        elif tree.left and tree.right:
            l_tmp = tree.left
            r_tmp = tree.right
            while r_tmp.left:
                r_tmp = r_tmp.left
            r_tmp.left = l_tmp
            return tree.right
        else:
            print("Success")
            return None
    return tree

tree = deleteNode(tree, 292)
tree.descending()

#target = int(input(" what delete num ?"))
print("-----------")
tree = deleteNode(tree, 254)
tree = deleteNode(tree, 100)
tree.descending()
tree = deleteNode(tree, 33)
tree = deleteNode(tree, 250)
tree = deleteNode(tree, 61)
tree = deleteNode(tree, 123)
tree.descending()

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


Insert実装

"""
   Program: Binary Tree
   Date: 2021. 10.  29
   Author: Lee Seung   Ju
"""
from random import *
# class part
class BinTree:
    # 생성자
    def __init__(self, elem):
        self.node = elem
        self.left = None
        self.right = None
    # 값을 넣으면 노드와 값을 비교한 후 다른 행동을 합니다.
    def insert(self, elem):
        if elem > self.node:
            if self.right:
                self.right.insert(elem)
            else: # -> elif self.right == None:
                self.right = BinTree(elem)
        else:
            if self.left:
                self.left.insert(elem)
            else: # -> elif self.left == None:
                self.left = BinTree(elem)
# main part
seed(1)
tree = BinTree(250)
for i in range(10):
    tree.insert(randint(1, 500))
insertを行う場合、最初のelemは木のnodeと比較される.大きい場合は、右側ノードに値があるかどうかを確認すると、右側ノードのinsertに移動し、値がない場合は、右側ノードの新規作成が表示されます.左側も同様に実行します.
そうなると下図のようになります.

これにより、各ノードは左ツリーと右ツリーにNoneを配置します.そうしてこそ木がNoneかどうかを知ることができるからだ.

上下出力を実現

"""
   Program: Binary Tree
   Date: 2021. 10.  29
   Author: Lee Seung   Ju
"""
from random import *
# class part
class BinTree:
    # 생성자
    def __init__(self, elem):
        self.node = elem
        self.left = None
        self.right = None
    # 값을 넣으면 노드와 값을 비교한 후 다른 행동을 합니다.
    def insert(self, elem):
        if elem > self.node:
            if self.right:
                self.right.insert(elem)
            else: # -> elif self.right == None:
                self.right = BinTree(elem)
        else:
            if self.left:
                self.left.insert(elem)
            else: # -> elif self.left == None:
                self.left = BinTree(elem)
    # 오름차순 출력
    def ascending(self):
        if self.left:
            self.left.ascending()
        print(self.node)
        if self.right:
            self.right.ascending()
    # 내림차순 출력
    def descending(self):
        if self.right:
            self.right.descending()
        print(self.node)
        if self.left:
            self.left.descending()
# main part
seed(1)
tree = BinTree(250)
for i in range(10):
    tree.insert(randint(1, 500))
print("--- 오름차순 출력 ---")
tree.ascending()
print("--- 내림차순 출력 ---")
tree.descending()

結果



実はコードは簡単ですが、内容は奥深いようです.大きさを比較するのではなく、木のNoneの有無で出力が決まるのが印象的でした.アップロードは簡単な小数の最初の出力であるべきなので、まず左の木を確認し、それから自分のノートで出力し、最後に右の木を確認します.
その後、ツリーのアップロードメソッドを再度呼び出し、再帰的に出力します.