inorder 또는 postorder traversal을 사용하여 입력을 받아 이진 트리를 구축해야 하는 경우 루트 요소를 설정하고, inorder traversal을 수행하고, post order traversal을 수행하는 메서드가 있는 클래스가 정의됩니다. 클래스의 인스턴스를 생성하여 사용할 수 있습니다.
아래는 동일한 데모입니다 -
예시
class BinaryTree_struct:
def __init__(self, key=None):
self.key = key
self.left = None
self.right = None
def set_root(self, key):
self.key = key
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()
def post_order_traversal(self):
if self.left is not None:
self.left.post_order_traversal()
if self.right is not None:
self.right.post_order_traversal()
print(self.key, end=' ')
def construct_btree(post_ord, in_ord):
if post_ord == [] or in_ord == []:
return None
key = post_ord[-1]
node = BinaryTree_struct(key)
index = in_ord.index(key)
node.left = construct_btree(post_ord[:index], in_ord[:index])
node.right = construct_btree(post_ord[index:-1], in_ord[index + 1:])
return node
post_ord = input('The input for post-order traversal is : ').split()
post_ord = [int(x) for x in post_ord]
in_ord = input('The input for in-order traversal is : ').split()
in_ord = [int(x) for x in in_ord]
my_instance = construct_btree(post_ord, in_ord)
print('Binary tree has been constructed...')
print('Verification in process..')
print('Post-order traversal is... ', end='')
my_instance.post_order_traversal()
print()
print('In-order traversal is... ', end='')
my_instance.inorder_traversal()
print() 출력
The input for post-order traversal is : 1 2 3 4 5 The input for in-order traversal is : 5 4 3 2 1 Binary tree has been constructed... Verification in process.. Post-order traversal is... 1 2 3 4 5 In-order traversal is... 5 4 3 2 1
설명
-
필수 속성을 가진 'BinaryTree_struct' 클래스가 생성됩니다.
-
왼쪽과 오른쪽 노드를 '없음'으로 설정하는 데 사용되는 '초기화' 기능이 있습니다.
-
이진 트리의 루트를 설정하는 데 도움이 되는 'set_root' 메서드가 있습니다.
-
순회를 수행하는 'inorder_traversal'이라는 또 다른 메서드, 즉 왼쪽→노드→오른쪽
-
'post_order_traversal'이라는 이름의 또 다른 메서드가 정의되어 트리를 사후 순서로 탐색하는 데 도움이 됩니다(예:Left→Right→Node.
). -
이전에 지정된 요소를 사용하여 이진 트리를 구성하는 데 도움이 되는 'construct_btree'라는 메서드가 정의되어 있습니다.
-
특정 요소를 검색하는 데 도움이 되는 'search_elem'이라는 메서드가 정의되어 있습니다.
-
'BinaryTree_struct' 클래스의 객체가 생성됩니다.
-
'construct_btree' 메소드는 이전에 지정된 요소를 취하여 이진 트리를 구성하는 데 사용됩니다.
-
이 트리에서 사후 순회 및 순회 순회가 수행됩니다.
-
관련 출력이 콘솔에 표시됩니다.