[Python] 트리

트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다.

정점(node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한다.

 

 

[트리의 용어]

---

• 루트노드(root node) : 부모가 없는 최상위 노드
• 단말노드(leaf node) : 자식이 없는 노드
• 크기(size) : 트리에 포함된 모든 노드의 개수
• 깊이(depth) : 루트 노드부터의 거리
• 높이(height) : 깊이 중 최댓값
• 차수(degree) : 각 노드의 (자식 방향) 간선 개수

 

기본적으로 트리의 크기가 N일때, 전체 간선의 개수는 N-1개 이다.

 

 

 

[이진 탐색 트리]

---

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다.

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 를 만족시킨다.

 

 

 

 

[트리의 순회]

---

트리 순회 방법은 3가지가 존재한다.

 

1. 전위 순회(pre-order traverse) : 루트를 먼저 방문 (루트->왼->오)
2. 중위 순회(in-order traverse) : 왼쪽 자식을 방문한 뒤에 루트를 방문 (왼->루트->오) 
3. 후위 순회(post-order traverse) : 왼쪽과 오른쪽 자식을 방문한 뒤에 루트를 방문 (왼->오->루트)

 

 

[트리 코드]

---

from logging import root


class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

def init_tree():
    global root

    new_node = Node("A")
    root = new_node

    new_node = Node("B")
    root.left = new_node
    new_node = Node("C")
    root.right = new_node

    new_node_1 = Node("D")
    new_node_2 = Node("E")
    node = root.left
    node.left = new_node_1
    node.right = new_node_2

    new_node_1 = Node("F")
    new_node_2 = Node("G")
    node = root.right
    node.left = new_node_1
    node.right = new_node_2

def preorder_traverse(node):
    if node == None : return
    print(node.data, end='->')
    preorder_traverse(node.left)
    preorder_traverse(node.right)

def inorder_traverse(node):
    if node == None : return
    inorder_traverse(node.left)
    print(node.data, end='->')
    inorder_traverse(node.right)

def postorder_traverse(node):
    if node == None : return
    postorder_traverse(node.left)
    postorder_traverse(node.right)
    print(node.data, end='->')
    
init_tree()

if __name__ == "__main__":
    preorder_traverse(root)
    print()
    inorder_traverse(root)
    print()
    postorder_traverse(root)

 

 

 

트리 코드 출처 - https://lsjsj92.tistory.com/465