[자료구조] Binary Tree

자료구조 중 이진트리를 공부하자.

 

---

∨ 개념

이진트리는 모든 노드의 차수(=자식노드 수)가 2개 이하인 트리이다.

 

 

 

∨ 특징

노드 N개짜리 이진트리의 간선은 N-1개다

- 노드 하나는 무조건 부모노드 하나랑 연결되어있음 AND 루트노드는 부모가 없음 

- 따라서 N-1개

 

노드 개수와 트리 높이간의 관련성

Let : 트리 높이를 H라고 하자 (유의: 루트부터 어떤 노드까지 다다르는 간선의 수가 높이다!)

Then : 노드의 개수는 최소 H+1개 ~ 최대 2^(H+1)-1개

 

Why? 그림으로 보자

 

ㄴ> 잠시만! 이진트리의 노드는 '왼쪽자식노드' or '오른쪽자식노드'를 갖는다.

ㄴ> 위 좌측 그림에서는 내가 일자로 그렸는데.. 엄밀히는 왼or오 자식 노드를 갖는 상태임을 유의!

 

 

 

 

∨ 이진트리 종류

- 포화이진트리 : 모든 노드가 자식노드를 2개(left&right)씩 꽉꽉 채워서 가지는 상태

- 완전이진트리 : 상단좌측=>하단우측 방향 우선으로 쭈루룩 꽉꽉 채워나간 이진트리

- 편향이진트리 : 노드의 개수는 최소개수인 H+1개 AND 자식을 한방향으로만 가짐

                           (즉 자식노드가 모두 left거나, 모두right거나)

 

 

 

 

 

∨ 이진트리 구현

일단 아래와 같이 생각을 쭉 해보자 :

 

- 이진트리의 구조는 1차원 배열에 저장할 수 있겠다. 인덱스를 노드번호 삼아서!

- 그런데 이진트리에 자식노드는 자유롭게 배치할 수 있다. 즉 비어있는 인덱스가 생긴다.

  이는 메모리 낭비일 수 있다.

 

- 그렇다면 순차배열인 ArrayList같은 것보다는 LinkedList처럼 연결연결되는 구조가 효율적이겠다.

- 그러고보니 노드의 추가/삭제에도 LinkedList가 유리하네! 이진트리에는 연결 리스트가 좋겠구나!

 

 

 

아하 그러면 이진트리는 LinkedList로 잘 구현하면 되는 거구나~

 

11/30일 이전에 구현해보자 만약 29일이 지났는데 글 수정 안하면

나는.. OTL........