バイナリツリー実装
バイナリツリーとは?
データ構造の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の有無で出力が決まるのが印象的でした.アップロードは簡単な小数の最初の出力であるべきなので、まず左の木を確認し、それから自分のノートで出力し、最後に右の木を確認します.
その後、ツリーのアップロードメソッドを再度呼び出し、再帰的に出力します.
Reference
この問題について(バイナリツリー実装), 我々は、より多くの情報をここで見つけました
https://velog.io/@seungju0000/이진트리BinaryTree-구현
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
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()
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の有無で出力が決まるのが印象的でした.アップロードは簡単な小数の最初の出力であるべきなので、まず左の木を確認し、それから自分のノートで出力し、最後に右の木を確認します.
その後、ツリーのアップロードメソッドを再度呼び出し、再帰的に出力します.
Reference
この問題について(バイナリツリー実装), 我々は、より多くの情報をここで見つけました https://velog.io/@seungju0000/이진트리BinaryTree-구현テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol