연결 리스트를 이용하여 이진 트리 데이터 구조를 구현해야 하는 경우 루트 노드를 설정하는 방법, in-order traversal을 수행하는 방법, 루트 노드의 왼쪽에 요소를 삽입하는 방법, 요소를 삽입하는 방법 루트 노드의 오른쪽에 값을 검색하는 방법이 정의되어 있습니다.
아래는 동일한 데모입니다 -
예시
class BinaryTree_structure:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
def in_order_traversal(self):
if self.left is not None:
self.left.in_order_traversal()
print(self.key, end=' ')
if self.right is not None:
self.right.in_order_traversal()
def insert_left(self, new_node):
self.left = new_node
def insert_right(self, new_node):
self.right = new_node
def search_val(self, key):
if self.key == key:
return self
if self.left is not None:
temp = self.left.search_val(key)
if temp is not None:
return temp
if self.right is not None:
temp = self.right.search_val(key)
return temp
return None
btree = None
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('quit')
while True:
print('The inorder traversal of binary tree ', end='')
if btree is not None:
btree.in_order_traversal()
print()
do = input('What would you like to do? ').split()
operation = do[0].strip().lower()
if operation == 'insert':
data = int(do[1])
new_node = BinaryTree_structure(data)
sub_op = do[2].strip().lower()
if sub_op == 'at':
btree = new_node
else:
position = do[4].strip().lower()
key = int(position)
ref_node = None
if btree is not None:
ref_node = btree.search_val(key)
if ref_node is None:
print('No such key exists')
continue
if sub_op == 'left':
ref_node.insert_left(new_node)
elif sub_op == 'right':
ref_node.insert_right(new_node)
elif operation == 'quit':
break 출력
Menu (this assumes no duplicate keys) insert <data> at root insert <data> left of <data> insert <data> right of <data> quit The inorder traversal of binary tree What would you like to do? insert 45 at root The inorder traversal of binary tree 45 What would you like to do? insert 78 left of 45 The inorder traversal of binary tree 78 45 What would you like to do? insert 90 right of 45 The inorder traversal of binary tree 78 45 90 What would you like to do? quit
설명
-
'BinaryTree_structure' 클래스가 생성됩니다.
-
트리의 루트 값을 설정하는 데 도움이 되는 'set_root' 기능이 있습니다.
-
'in_order_traversal'이라는 메서드가 정의되어 'Left->Node->Right' 순서로 트리를 탐색하는 데 도움이 됩니다.
-
루트 값의 왼쪽에 요소를 추가하는 데 도움이 되는 'insert_left'라는 또 다른 메서드가 정의되어 있습니다.
-
루트 값의 오른쪽에 요소를 추가하는 데 도움이 되는 'insert_right'라는 또 다른 메서드가 정의되어 있습니다.
-
스택의 맨 위에서 값을 삭제하고 삭제된 값을 반환하는 'search_val'이라는 또 다른 메서드가 정의되어 있습니다.
-
'루트에 삽입', '왼쪽에 삽입', '오른쪽에 삽입' 및 '종료'와 같은 4가지 옵션이 제공됩니다.
-
사용자의 입력/선택에 따라 각각의 동작이 수행됩니다.
-
이 출력은 콘솔에 표시됩니다.