220825_TIL

자료구조 Tree

1. 코드를 살펴보자.

class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
class BinaryTree():                  # 이진 트리 선언
    def __init__(self, Node):
        self.root = Node
        
    def preorder(node):              # 전위 순회 (부모 → 左자식 → 右자식)
        if node:
            print(node.data)
            preorder(node.left)
            preorder(node.right)

	def inorder(node):               # 중위 순회 (左자식 → 부모 → 右자식)
        if node:
            inorder(node.left)
            print(node.data)
            inorder(node.right)
        
    def postorder(node):             # 후위 순회 (左자식 → 右자식 → 부모)
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

2. 순회 방식에 대해 풀어 써보자

1. 전위 순회

• 부모노드부터 왼쪽 노드로 쭉 순회하면서 출력
• 왼쪽 노드를 다 출력하고 나면, 남은 노드들에 대해 다시 전위 순회
• 오른쪽 노드들만 남은 경우, 최하단 오른쪽 리프노드부터 위로 올라가면서 하나씩 출력

2) 중위 순회

• 왼쪽 노드를 쭈욱 타고내려가 최하단 왼쪽 리프노드부터 출력
• 왼쪽 자식노드 → 부모 노드 → 오른쪽 자식노드 순서로 출력

3) 후위 순회

• 왼쪽 자식노드 → 오른쪽 자식노드 → 부모 노드 순서로 출력

3. 순회 예시를 가지고 내 나름대로 헷갈린 내용을 정리해보자.

PC로 작업하려면 오래걸릴 듯 해서 그냥 그렸음..
생각보다 빨리 작업했고, 하면서 이해도 잘 되고 정리도 잘된 듯 싶다.