이진트리(Binary Tree)

---

이진트리. (Binary Tree)

이진트리란 ? 

자식노드를 최대 2개를 갖는 트리를 이진트리라고 한다.

트리란 : 싸이클이 존재 하지 않고, 수직적인 구조를 가지고 있다. 가족관계도 라고 생각하면 편한데, 위로 혹은 아래로 간다고 생각하면된다.

참고 : https://ko.wikipedia.org/wiki/트리_구조

이진트리는 트리중에 자식노드를 최대 2개밖에 갖지 않는다. 

그렇기 때문에 다양한 곳에 응용 할 수 있다. Heap도 이진트리를 사용하고 있고, 나중에 설명할 IndexTree 역시도 이진트리를 사용하고 있다.

이진트리의 장점이 무엇인가? 자식 노드가 두개밖에 없기때문에 자식노드중 하나를 선택할때 굉장히 효율적으로 할 수 있다. 

운동경기 처럼 1:1 대결만 존재하기 때문에 이진 트리로 표현하기 굉장히 편하고,

이상형 월드컵(?) 같은 것을 할 때, 둘중 한명만 이기고 한명은 지는 선택을 할 때 굉장히 편하기 때문이다.

이진트리가 아니라 자식노드가 3개 있을 때, 이들이 정확히 대소가 존재하는 숫자가 아니라 "가위 바위 보" 같이 

한명씩 가위, 바위, 보를 하고 있다면 누가 이겼는지, 셋중에 누가 강자인지 판단 하기가 굉장히 애매하기 때문이다. 

---

이진 트리의 표현

이진트리를 표현할 때 Linked List를 사용해서 표현 할 수 도 있지만 배열로 간단하게 표현할 수 있다.

l[1] 이 최상위 투트로 잡고, 각 i 노드에 대해 왼쪽 노드를 i * 2 라 하고, 오른쪽 노드를 i * 2 + 1 이라고 할 수 있다.

이를 표현해보면 

이런식으로 각노드의 이름을 정하고 그 위치 배열에 적용한다면 배열로 표현하기 편하다.

왜냐하면 자신의 위치만 알면 자기 자식노드의 위치를 한번에 접근하거나,

원하는 위치를 쉽게 접근할 수 있고, 따로 자식노드에 뭐가있는지 부모노드에 뭐가있는지 저장하지 않아도 된다는 장점이 있습니다. 

하지만, 이러한 표현방식을 이용하면 포화 이진 트리일 경우에는 상관없지만

만약 트리가 일직선으로 쭉 퍼져있는경우 메모리 낭비가 심각해질 수 있습니다.

아니면, Map을 이용해서 key-value로 이런식으로 효율적으로 만들 수 있을것 같습니다.

---

이진트리의 탐색

이진트리는 크게 4가지 탐색 방법이 있고, 각 탐색 방법의 순서를 적자면.

Pre-Order: 자신 - 왼쪽 노드 - 오른쪽 노드

In-Order: 왼쪽 노드 - 자신 - 오른쪽 노드

Post-Order: 왼쪽 노드 - 오른쪽 노드 - 자신

Level-Order: 1레벨 (맨 윗층) - 2레벨 (두번째 층) - 각 level ( 높이 ) 마다.

위의 그래프를 예시로 설명해보자면

---

Pre-Order

자신 - 왼쪽노드 - 오른쪽 노드

A 노드에서 부터 시작한다면

일단

Step	현재노드	출력 결과
자신을 출력한다.	A	A
왼쪽 노드로 들어간다.	B	A
자신을 출력한다.	B	AB
왼쪽 노드로 들어간다.	C	AB
자신을 출력한다	C	ABC
왼쪽 노드로 들어간다. 없다. 오른쪽으로 들어간다. 없다. 나온다.	B	ABC
왼쪽 노드는 방문했으니 오른쪽으로 들어간다.	D	ABC
자신을 출력한다.	D	ABCD
왼쪽 노드로 들어간다.	E	ABCD
자신을 출력한다.	E	ABCDE

 이런식으로, 노드를 처음 방문하게되면 자신을 출력하고, 왼쪽 노드를 방문한뒤 왼쪽 Subtree의 모든점을 방문하고 나왔을 때, 자신의 오른쪽 노드를 방문시켜 오른쪽 Subtree의 모든점을 방문하고 나오게된다.

위의 예제를 다 실행시킨후 출력 결과는 : ABCDEFGHI

<C++>

// // l[i] 은 2진트리를 가지고있는 배열. -1의 값을 가지고 잇으면 빈곳이다. void Preorder(int now){      if(l[now] == -1)return;      printf("%d",l[now]); // 자신 노드를 찍고      Preorder(now * 2); // 왼쪽 노드로 들어가고      Preorder(now * 2 + 1); // 오른쪽 노드로 들어간다. }

---

In-Order

왼쪽노드 - 자신 - 오른쪽 노드

A 노드에서 부터 시작한다면

일단

Step	현재노드	출력 결과
왼쪽 노드로 들어간다.	B
왼쪽 노드로 들어간다.	C
왼쪽노드로 들어갈 수 없으니, 자신을 출력한다.	C	C
오른쪽 노드가 없으니 나온다.	B	C
자신을 출력한다.	B	CB
오른쪽 노드로 들어간다.	D	CB
왼쪽 노드로 들어간다.	E	CB
왼쪽 노드로 들어갈 수 없으니, 자신을 출력한다.	E	CBE
오른쪽 노드가 없으니 나온다.	D	CBE
자신을 출력한다.	D	CBED
오른쪽 노드로 들어간다.	F	CBED

 이런식으로, 노드를 처음 방문하게되면 왼쪽 sub트리로 들어가고, 다돌고 나오게되면, 자신을 출력하고, 오른쪽 sub트리로 들어가는 수행을 반복한다.

위의 예제를 다 실행시킨후 출력 결과는 : CBEDFAGIH

// 이 정보로 알수 있는점은 X 노드의 왼쪽 subtree중 한 노드 Y는 출력결과에서, Y가 X보다 앞에 존재하고 ( 예로 D와 A를 들면 D가 A보다 먼저나온다. )

// X 노드의 오른쪽 subtree중 한 노드 Y는 출력결과에서, X가 Y보다 먼저 존재한다.

<C++>
// // l[i] 은 2진트리를 가지고있는 배열. -1의 값을 가지고 잇으면 빈곳이다. void Preorder(int now){      if(l[now] == -1)return;      Preorder(now * 2); // 왼쪽 노드로 들어가고      printf("%d",l[now]); // 자신 노드를 찍고      Preorder(now * 2 + 1); // 오른쪽 노드로 들어간다. }

---

Post-Order

왼쪽노드 -  오른쪽 노드 - 자신

A 노드에서 부터 시작한다면

일단

Step	현재노드	출력 결과
왼쪽 노드로 들어간다.	B
왼쪽 노드로 들어간다.	C
왼쪽이 없고, 오른쪽도 없고, 자신을 출력한다.	C	C
자신을 출력했으니 나온다.	B	C
오른쪽 노드로 들어간다.	D	C
왼쪽 노드로 들어간다.	E	C
왼쪽이 없고, 오른쪽도 없고, 자신을 출력한다.	E	CE
자신을 출력했으니 나온다.	D	CE
오른쪽 노드로 들어간다.	F	CE
왼쪽도 없고 오른쪽도 없고, 자신을 출력한다.	F	CEF
자신을 출력했으니 나온다.	D	CEF
왼쪽 오른쪽 들렸으니, 자신을 출력한다.	D	CEFD

 이런식으로, 노드를 처음 방문하게되면 왼쪽 sub트리로 들어가고, 다돌고 나오게되면, 자신을 출력하고, 오른쪽 sub트리로 들어가는 수행을 반복한다.

위의 예제를 다 실행시킨후 출력 결과는 : CEFDBIHGA

// 이 정보로 알수 있는점은 X 노드의 왼쪽이나 오른쪽 subtree중 한 노드 Y는 출력결과에서, Y가 X보다 앞에 존재한다.

 ( 예로 D와 A를 들면 D가 A보다 먼저나온다. )

<C++>
// // l[i] 은 2진트리를 가지고있는 배열. -1의 값을 가지고 잇으면 빈곳이다. void Preorder(int now){      if(l[now] == -1)return;      Preorder(now * 2); // 왼쪽 노드로 들어가고      Preorder(now * 2 + 1); // 오른쪽 노드로 들어간다.      printf("%d",l[now]); // 자신 노드를 찍고 }