[Study] Tree

Tree란?

Tree란 비선형 자료구조로 노드(node)와 노드를 연결하는 간선(edge)들로 이루어져있다.

 

- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
- 트리에는 사이클(cycle)이 존재할 수 없다.

 

 

Tree의 순회 방법

전위 순회

자신 -> 왼쪽 트리 -> 오른쪽 트리

 

중위 순회

왼쪽 트리 -> 자신 -> 오른쪽 트리

 

후위 순회

왼쪽 트리 -> 오른쪽 트리 -> 자신 

 

 

DFS와 BFS

DFS
깊이 우선 탐색
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 사용, 재귀 함수 사용

def dfs(graph,v,visited):
   visited[v] = True

   for i in graph[v]:
      if not visited[i]:
         dfs(graph,i,visited)

dfs(graph,1,visited)

 

BFS
너비 우선 탐색
가까운 노드부터 탐색하는 알고리즘
큐 사용 -> 수행시간이 DFS보다 좋음 (시간복잡도 O(N))

from collections import deque

def bfs(graph,start,visited):
   queue = deque([start])
   visited[start] = True

   while queue:
      v = queue.popleft()
      for i in graph[v]:
         if not visited[i]:
            queue.append(i)
            visited[i] = True
   
bfs(graph,1,visited)

CT-Study/PART 2/Chapter 5, DFS&BFS.md at master · JeongEunJi1127/CT-Study

 

 

행동 트리(Behaviour Tree)란?