Python에서 이진 트리 인쇄
이 기사에서는 이진 트리와 이를 사용하는 방법에 대해 설명합니다. 또한 Python을 사용하여 인쇄하는 방법도 살펴보겠습니다.
이진 트리 작업에 사용되는 용어에 대해 알아봅니다. 또한 Python 코드를 사용하여 이진 트리의 예를 살펴보겠습니다.
Python의 이진 트리
Python의 이진 트리는 사용 가능한 가장 효율적인 데이터 구조 중 하나이며 구현하기도 비교적 간단합니다. 이진 트리는 루트 노드와 두 개의 자식 노드(왼쪽 및 오른쪽)가 있는 트리와 유사한 데이터 구조입니다.
각 노드는 원하는 수의 자식 노드를 가질 수 있습니다. 이 기사에서는 Python에서 이진 트리를 만들고 순회하는 방법을 살펴봅니다.
트리와 관련된 용어를 더 잘 이해해 봅시다.
- 루트: 부모가 없는 트리의 최상위 노드. 모든 나무에는 하나의 뿌리가 있습니다.
- Edge: Edge는 부모-자식 링크입니다.
- 리프: 자식이 없는 노드. 트리의 최종 노드입니다. 트리에는 여러 리프 노드가 있습니다.
- 하위 트리: 트리는 노드를 루트로 사용합니다.
- 깊이: 깊이는 루트에서 노드까지의 거리입니다.
- 높이: 노드의 높이는 하위 트리의 가장 깊은 노드까지의 거리입니다.
- 트리 높이: 트리의 높이는 가장 높은 노드이며 루트 노드와 동일한 높이에 해당합니다.
트리의 순회 순서
트리는 루트 노드에서 시작하여 왼쪽 및 오른쪽 자식 노드를 방문하여 순회합니다. 노드를 방문하는 순서를 순회 순서라고 합니다.
순서 순회 트리
이진 트리를 순회하는 방법에는 여러 가지가 있습니다. 가장 일반적인 것은 왼쪽, 루트 및 오른쪽 하위 노드를 방문하는 순서 순회입니다.
선주문 순회 트리
또 다른 표준 순회는 루트 노드를 먼저 방문한 다음 왼쪽 자식, 마지막으로 오른쪽 자식을 방문하는 사전 순회입니다.
순서 순회는 각 노드를 한 번만 방문하기 때문에 이진 트리의 모든 노드를 방문하는 가장 효율적인 방법입니다. 선주문 순회는 루트 노드를 두 번 호출하기 때문에 약간 덜 효율적입니다.
그러나 pre-order traversal은 루트 노드를 먼저 변경한 다음 왼쪽 및 오른쪽 자식 노드를 변경하기 쉽기 때문에 순회 중에 트리를 수정하려는 경우 자주 사용됩니다.
다음은 파이썬에서 순차 순회의 구문과 간단한 구현입니다.
def inorder(node):
if node is not None:
inorder(node.left)
print(node.val)
inorder(node.right)
그래서 이것은 순회 방법을 사용하고자 할 때 우리가 코딩하는 방법입니다.
다음은 선주문 순회입니다.
def preorder(node):
if node is not None:
print(node.val)
preorder(node.left)
preorder(node.right)
사후 순회
왼쪽 자식, 오른쪽 자식, 루트 노드를 차례로 방문하는 사후 순서로 트리를 순회할 수도 있습니다. 그러나 사후 순회는 다른 두 순회보다 덜 효율적이기 때문에 덜 일반적입니다.
레벨별로 트리 수준의 노드를 방문하는 레벨 순서 순회와 같은 이진 트리를 순회하는 다른 방법이 있습니다. 그러나 이 기사에서는 순회를 다루지 않을 것입니다.
이제 이진 트리를 순회하는 방법을 살펴보았으므로 Python을 사용하여 하나의 이진 트리를 만들고 인쇄하는 방법을 살펴보겠습니다.
Python에서 이진 트리 구현
우리는 이진 트리가 무엇인지 그리고 이와 관련된 용어를 알고 있습니다. 이진 트리가 어떻게 작동하는지 더 잘 이해하기 위해 Python을 사용하여 이진 트리를 구현합니다.
-
여기서 클래스가 될 이진 트리에 대한 노드가 필요합니다. 데이터 유형을 만들 것이기 때문에 왼쪽 및 오른쪽 주소와 함께 데이터 포인트를 넣습니다.
아직 그런 데이터 유형이 없으므로 필요한 방식으로 데이터 유형을 만들 것입니다. 따라서 먼저 클래스를 생성합니다.
-
이제 클래스에 대한 생성자를 생성합니다. 그리고 필요에 따라 클래스의 생성자를 전달합니다.
또한 트리의 데이터를 저장할 매개변수 데이터도 제공합니다.
-
self를 사용하여 데이터를data매개변수로 가져올 것입니다. -
데이터가 없으면 노드를 생성할 수 없기 때문입니다. 데이터가 없으면 노드로 무엇을 할까요?
데이터가 없으면 왼쪽과 오른쪽이 없습니다. 논리적으로 우리는 데이터가 필요하고 이것이 여기서 데이터를 사용하는 이유입니다.
이제 노드가 필요합니다.
- 왼쪽 노드
- 오른쪽 노드
아래 코드로 구현해 보겠습니다.
-
이제 이진 트리를 구현했습니다(아래 코드에서). 왼쪽 및 오른쪽 노드를 생성하고
없음으로 설정했습니다.노드가 만들어지면
None과 유사해야 하기 때문입니다. 트리는 루트에서 시작하므로 왼쪽 및 오른쪽 데이터가 없습니다. 나중에 데이터를 추가하겠습니다.이제 우리는 나무에 대한 몇 가지 개체를 만들 것입니다.
binaryTreeNode클래스에 대한 개체를 생성하려면 변수를 생성하고binaryTreeNode()클래스에 할당해야 합니다. -
우리는
class binaryTreeNode에 대해 세 개의 개체를 만들었지만 이 개체는 현재 어떤 것과도 연결되어 있지 않습니다. 따라서 객체에 포함된 내용을 확인하기 위해 객체를 인쇄하면 아래에 언급된 코드를 따를 것입니다. -
이제
bnt1,bnt2및bnt3의 세 개체를 만들었으므로 루트의 왼쪽 및 오른쪽에 대한 데이터 포인트를 제공합니다. 우리는bnt1이 루트이고bnt2와bnt3이bnt1의 왼쪽과 오른쪽이라고 생각합니다. -
이 경우 이진 트리는 아래와 같습니다. 그리고 이것이 코드의 출력 방법입니다.
1 / \ / \ 2 3여기서 루트는 1입니다. 왼쪽 부분은 2이고 오른쪽 부분은 3입니다. 이제 Python을 사용하여 인쇄하여 작동 방식을 살펴보겠습니다.
-
우리는 루트를 얻은 후에 전체 트리를 인쇄하기를 원합니다. 이를 위해 메서드를 정의해야 합니다.
우리가 해야 할 일은 여기에 해당 코드를 복사하고 그 안에 새 코드를 작성하는 것입니다. 이진 트리의 일부이기 때문에 이미 작성된 코드로 새 코드를 작성해야 합니다.
예제 코드:
class binaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def printTree(root):
print(root.data)
print("L", root.left.data, end=": ")
print("R", root.right.data, end=": ")
bnt1 = binaryTreeNode(1)
bnt2 = binaryTreeNode(2)
bnt3 = binaryTreeNode(3)
bnt1.left = bnt2
bnt1.right = bnt3
bnt2.left = bnt1
bnt2.right = bnt3
bnt3.left = bnt1
bnt3.right = bnt2
def printTree(root) 메서드는 우리에게 루트를 제공합니다. 트리의 루트가 있으면 노드가 있는 전체 트리에 액세스할 수 있기 때문입니다.
메서드를 선언한 후 몇 가지 조건을 확인합니다. 위의 코드에서 def PrintTree(root) 메서드를 볼 수 있습니다.
루트 1인 bnt1을 출력하여 결과를 확인합니다.
예제 코드:
print(bnt1.printTree())
출력:
1
L 2: R 3: None
출력에는 트리에 두 개의 노드(왼쪽 노드와 오른쪽 노드)가 포함되어 있음이 표시됩니다. 왼쪽 노드의 데이터는 2이고 오른쪽 노드의 데이터는 3입니다.
bnt2 및 bnt3을 인쇄하여 포함된 데이터 포인트를 확인할 수도 있습니다.
Python을 사용하여 전체 이진 트리 인쇄
다음은 전체 이진 트리입니다. 우리는 그것을 실행할 수 있고 Python의 random 라이브러리와 함께 Python을 사용하여 이진 트리가 인쇄되는 방법에 대해 자세히 알아볼 수 있습니다.
import random
class BinaryTree:
def __init__(self, key):
self.key = key
self.right = None
self.left = None
def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BinaryTree(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BinaryTree(key)
else:
self.left.insert(key)
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = "%s" % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = "%s" % self.key
u = len(s)
first_line = (x + 1) * " " + (n - x - 1) * "_" + s
second_line = x * " " + "/" + (n - x - 1 + u) * " "
shifted_lines = [line + u * " " for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = "%s" % self.key
u = len(s)
first_line = s + x * "_" + (n - x) * " "
second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
shifted_lines = [u * " " + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = "%s" % self.key
u = len(s)
first_line = (x + 1) * " " + (n - x - 1) * "_" + s + y * "_" + (m - y) * " "
second_line = (
x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
)
if p < q:
left += [n * " "] * (q - p)
elif q < p:
right += [m * " "] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
b = BinaryTree(100)
for _ in range(100):
b.insert(random.randint(50, 150))
b.display()
출력:
코드의 출력은 실행할 때마다 계속 변경됩니다. 파이썬의 random 모듈을 사용하고 있기 때문입니다.
이 기사가 Python을 사용하여 이진 트리를 인쇄하는 방법을 이해하는 데 도움이 되기를 바랍니다.
My name is Abid Ullah, and I am a software engineer. I love writing articles on programming, and my favorite topics are Python, PHP, JavaScript, and Linux. I tend to provide solutions to people in programming problems through my articles. I believe that I can bring a lot to you with my skills, experience, and qualification in technical writing.
LinkedIn