이진 검색 트리를 정렬해야 하는 경우 클래스가 생성되고 그 안에 요소 삽입 및 중위 순회 수행과 같은 작업을 수행하는 메서드가 정의됩니다.
아래는 동일한 데모입니다 -
예시
class BinSearchTreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert_elem(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert_elem(node)
elif self.key <= node.key:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert_elem(node)
def inorder_traversal(self):
if self.left is not None:
self.left.inorder_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.inorder_traversal()
class BinSearchTree:
def __init__(self):
self.root = None
def inorder_traversal(self):
if self.root is not None:
self.root.inorder_traversal()
def add_val(self, key):
new_node = BinSearchTreeNode(key)
if self.root is None:
self.root = new_node
else:
self.root.insert_elem(new_node)
my_instance = BinSearchTree()
my_list = input('Enter the list of numbers... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
my_instance.add_val(x)
print('Sorted list: ')
print(my_instance.inorder_traversal()) 출력
Enter the list of numbers... 67 54 89 0 11 34 99 Sorted list: 0 11 34 54 67 89 99
설명
-
필수 속성을 가진 'BinSearchTreeNode' 클래스가 생성됩니다.
-
'None'에 'left', 'right' 및 'parent' 노드를 할당하는 데 사용되는 'init' 기능이 있습니다.
-
트리에 노드를 추가하는 데 도움이 되는 'insert_elem'이라는 또 다른 메서드가 정의되어 있습니다.
-
트리에서 중위 순회를 수행하는 데 도움이 되는 'inorder_traversal'이라는 또 다른 메서드가 정의되어 있습니다.
-
'BinSearchTree'라는 또 다른 클래스가 정의되어 있습니다.
-
루트를 '없음'으로 설정합니다.
-
트리에서 중위 순회를 수행하는 데 도움이 되는 'inorder_traversal'이라는 메서드가 있습니다.
-
트리에 노드를 추가하는 데 도움이 되는 'add_val'이라는 또 다른 메서드가 정의되어 있습니다.
-
'BinSearchTree'의 인스턴스가 생성됩니다.
-
번호 목록은 사용자가 가져옵니다.
-
이를 이용하여 트리를 생성합니다.
-
목록이 정렬되고 순서대로 순회됩니다.
-
관련 출력이 콘솔에 표시됩니다.