트리 Tree

트리

- 서로 연결된 Node 의 계층형 자료구조

- root 와 부모-자식 관계의 subtree로 구성

 

Tree 관련 개념

- 노드(Node) : 트리를 노드로 구현

- 간선(Edge) : 노드간에 연결된 선

- 루트 노드(Root) : 트리는 항상 루트 노드에서 시작

- 리프 노드(Leaf) :더이상 뻗어나갈 수 없는 마지막 노드

- 자식 노드(Child), 부모노드(Parent), 형제 노드(Sibling)

- 차수(degree) : 각 노드가 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라고 한다.

- 조상(ancestor): 위쪽으로 간선을 따라 올라가면 만나는 모든 노드

- 자손(descendant): 아래쪽으로 간선을 따라가면 만나는 모든 노드

- 높이(height) : 루트노드에서 리프노드까지의 거리( 리프노드중에 최대 레발 값)

- 서브트리(subtree): 트리의 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리를 subtree라고 한다.

 

Binary tree(이진트리)

- 모든 차수가 2 이하인 트리

- 각 Node는 value, left child, right child로 구성

- 완전이진트리 LEAF 트리를 제외한 모든 노드의 차수가 2

 

트리구현

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


class BinaryTree:
    def __init__(self) :
        self.root = None

트리 순회

- 트리의 각 노드를 모두 방문하는 과정

- 완전탐색이라고도 불린다.

- 너비 우선 탐색(BFS - 가까운 레벨부터 탐색), 깊이 우선 탐색(DFS - 자식 노드 부터 탐색[스택과 재귀로 구현 가능])

 

BFS 구현

from collections import deque

bt = BinaryTree()
bt.root = Node(value=1)
bt.root.left = Node(value=2)
bt.root.right = Node(value=3)
bt.root.left.left = Node(value=4)
bt.root.left.right = Node(value=5)
bt.root.right.left = Node(value=6)
bt.root.right.right = Node(value=7)


# BFS

def bfs(root):
    visited = [] #순회하면서 방문하는 노드를 여기에 추가한다.
    if root is None:# root 노드가 없으면 0 반환
        return 0
    q = deque()#방문해야 하는 다음 노드들을 담는곳
    q.append(root)# root 노드부터 시작
    while q:#방문해야 할 다음노드가 없을때까지 반복
        cur_node = q.popleft()#방문해야할 노드르르 cur_node 변수에 담고 방문해야할 노드 목록인 q에서 빠진다.
        visited.append(cur_node.value) # 방문한 노드를 visited에 담아줌
        
        #이진 트리 left와 right에 방문할 노드가 있으면 q에 추가해줌
        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    #모든 노드를 너비 우선 탐색으로 visited에 담아준거를 return
    return visited


print(bfs(bt.root))# [1, 2, 3, 4, 5, 6, 7]

DFS 구현

# DFS(재귀사용)
def dfs(cur_node):
    if cur_node is None:  # 노드가 없으면 return
        return
    dfs(cur_node.left)
    dfs(cur_node.right)

# 전위순회 - preorder
def preorder(cur_node):
    if cur_node is None:
        return
    # 먼저 자신을 방문 > 왼쪽 또는 오른쪽 > 왼쪽 또는 오른쪽
    print(cur_node.value)
    preorder(cur_node.left)
    preorder(cur_node.right)

# 중위순회 - inorder
def inorder(cur_node):
    if cur_node is None:
        return
    # 먼저 왼쪽 또는 오른쪽을 방문하고 > 자신 방문  > 나머지 방문
    inorder(cur_node.left)
    print(cur_node.value)
    inorder(cur_node.right)


# 후위순회 - postorder
def postorder(cur_node):
    if cur_node is None:
        return
    # 먼저 왼쪽 또는 오른쪽을 방문하고 > 왼쪽 또는 오른쪽을 방문 > 자신 방문
    postorder(cur_node.left)
    postorder(cur_node.right)
    print(cur_node.value)