재귀함수, Binary Tree 이진트리, 트리순회traversal,너비우선탐색BFS, 깊이우선탐색 DFS

재귀함수

나 자산을 또 호출하는 함수

 

반복적으로 실행함

그래서 재귀 함수 만들 때!

 

1. recurrence relation 점화식

2. base case 

꼭있어야함. 

 

점화식으로 계속 반복되고 

그 반복이 base case에 도달하면 재귀함수가 끝이 남. 

base case가 없으면 무한루프되므로 주의!

 

Tree 개념

 

노드: 트리는 보통 노트로 구현

차수degree 각노드가 갖는 자식의 수

 

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

 

Binary Tree 이진트리 

차수가 2진 이하 

이 노드들의 구성 요소:

value값 저장, left child 주소값 저장, right child wnthrkqt wjwkd

 

코드로 구현시:

1. 이렇게 구현된 노드생성 

 

2. binary Tree 구성

 

트리 순회Traversal (= 트리탐색, 완전탐색)

트리의 각 노드를 방문하는 과정을 말함

모든 노드를 한번씩 방문해야해서 순회 방법으로는 

너비우선탐색의 BFS Breadth-First Search

깊이우선탐색의 DFS Depth-First Search

 

 

BFS

root기준으로 탐색. 아래로 level 0, level1 이렇게 가까운것부터 탐색

 

순회해서 그 노드에 "방문한다"

->

그 노드에 접근하는 것은 언제든 할 수 있음.

근데 "방문"은 그노드에 접근해서 "어떤 작동을 시키는 것"

 

트리순회에서 그냥 접근하는 것과 방문하는 것은 다름!

 

 

DFS

스택 반복문으로도 만들 수 있고

재귀로도 만들 수 있음.

 

DFS는 접근 어떻게 할지 생각하고 방문 어떻게 할지 생각.

접근을 재귀로 한다. 

방문은 순회 종류에 따라 다른데

전위순회 preorder

자식노드들에게 가기 전에 일단 자기 자신 방문(기록을 하든 뭘하든..)먼저함.

중위순회 inorder

나 자신을 방문하는게 중간에 있음

후위순회 postorder

자식들 다 방문하고 나서 자기 자신 방문