9 - 1 트리구조

 

트리 

데이터 사이의 계층관계를 표현

루트

트리의 가장 위쪽에 있는 노드

트리 하나에 1개만 존재

 

리프 = 단말 노드 = 외부 노드

가장 아래쪽에 있는 노드

가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다 >> 자식x

 

비단말 노드 = 내부 노드

리프를 제외한 노드

 

자식

어떤 노드와 가지가 연결괴엇을 때 아래쪽 노드

 

형제

부모가 같은 노드

 

조상

어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드

 

자손

어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드

 

레벨

루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것

가지가 하나씩 아래로 뻗어 내려갈 때마다 레벨이 1씩 증가

 

차수

각 노드가 갖는 자식의 수

모든 노드의 차수가 n이하인 트리를 'n진 트리'라 한다.

 

높이

루트에서 가장 멀리 있는 리프까지의 거리. 리프레벨의 최댓값

 

서브트리

어떤 노드를 루트로 하고 그 자손으로 구성된 트리

 

빈 트리 = 널 트리

노드와 가지가 전혀 없는 트리

 

순서 트리

형제 노드의 순서관계가 있는 트리

 

무순서 트리

형제 노드의 순서관계가 없는 트리

 

 

1.너비 우선 검색(breadth - first - search) = 폭 우선 검색 = 가로 검색 = 수평 검색

낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법 (가까운 노드부터 우선적으로 탐색하는 알고리즘)

큐 자료구조를 이용하며, 구체적인 동작과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

0. 그래프 준비(방문기준 : 번호가 낮은 인접 노드부터) - 시작노드 : 1

1. 시작 노드인 1을 큐에 삽입하고 방문처리

2. 큐에서 노드 1을 꺼내 방문하지 않은 인접 노드 2,3,8을 큐에 삽입하고 방문 처리

3. 큐에서 노드 2를 꺼내 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문처리

4. 큐에서 노드 3을 꺼내 방문하지 않은 인접 노드 4,5를 큐에 삽입하고 방문처리

5. 큐에서 노드 8을 꺼내 방문하지 않은 인접 노드가 없으므로 무시

 

# bfs
from collections import deque

# 각 노드가 연결괸 정보를 표현(2차원 리스트)
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [], 
    [2,3,8],  # 1번 노드
    [1,7],    # 2번 노드
    [1,4,5],  # 3번 노드
    [3,5],    # 4번 노드
    [3,4],    # 5번 노드
    [7],      # 6번 노드
    [2,6,8],  # 7번 노드
    [1,7]     # 8번 노드
] 

# bfs 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때 까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기 
        v = queue.popleft()
        print(v, end = " ")
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9   # 1~8까지 노드번호로 이용된 숫자이므로 9 이용


# 정의된 bfs 함수 호출
bfs(graph, 1, visited)

 

2.깊이 우선 검색(depth - first - search) = 세로 검색 = 수직 검색

리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것 (깊은 부분을 우선적으로 탐색)

리프에 도달해서 더 이상 검색할 곳이 없으면 부모노드로 돌아가고 그 뒤 다시 자식노드로 내려감

스택 자료구조 또는 재귀함수를 이용하며, 구체적인 동작과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

1.시작 노드인 1을 스택에 삽입하고 방문처리

2.스택의 최상단 노드인 1에 방문하지 않은 인접노드 2,3,8 중 가장 작은 노드인 2를 스택에 넣고 방문처리

3.스택의 최상단 노드인 2에 방문하지 않은 인접노드 7을 스택에 넣고 방문처리

4.스택의 최상단 노드인 7에 방문하지 않은 인접노드 6,8 중 가장 작은 노드인 6을 스택에 넣고 방문처리

5.스택의 최상단 노드인 6에 방문하지 않은 인접노드가 없다. 따라서 스택에서 6번 노드를 꺼낸다.

6.스택의 최상단 노드인 7에 방문하지 않은 인접노드 8 이 있다. 8번 노드를 스택에 넣고 방문처리

전체 노드의 탐색 순서 : 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5

 

# dfs

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
    [], 
    [2,3,8],  # 1번 노드
    [1,7],    # 2번 노드
    [1,4,5],  # 3번 노드
    [3,5],    # 4번 노드
    [3,4],    # 5번 노드
    [7],      # 6번 노드
    [2,6,8],  # 7번 노드
    [1,7]     # 8번 노드
] 


def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = " ")

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i ,visited)


# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9  # 1~8까지 노드번호로 이용된 숫자이므로 9 이용

# 정의된 dfs함수 호출
dfs(graph, 1, visited)

 

 

 

 

2-1.전위순회

노드방문 > 왼쪽자식 > 오른쪽자식

 

2-2.중위순회

왼쪽자식 > 노드 방문 > 오른쪽자식

 

2-3.후위순회

왼쪽자식 > 오른쪽자식 > 노드방문

 

지나가는 것과 방문하는 것은 다른 개념이다!