[작성중] 완전 이진 트리 짜고 싶다...

완전 이진트리를 짜고 있다.

완전 이진트리라 함은 제일 위에 하나의 노드를 시작으로 자식놈들을

딱 2개씩만 가지고 뻗어나가는 이쁜 모양의 트리를 말한다.

물론 대충 이진트리를 짜기에는 쉽다.

트리가 좌우로 어떻게 뻗어가든 그냥 노드에 추가만 시켜주면 되니까

하지만 나는 차례대로 순서대로 하나하나 붙어져가는 완전 이진트리를 짜고 싶다.

생각보다 어렵다. 어떻게 하면 insert를 했을 때 알아서 새로운 노드가 들어가야 할 자리를

차곡 차곡 찾아가게 해야할 수 있을까..

나는 여기서 하나 생각을 했다

왼쪽:0, 오른쪽:1

0 1

00 01 10 11

000 001 010 011 100 101 110 111

. 

.

.

.

완전 이진트리가 차곡차곡 쌓여가는 규칙은 위와 같이 0을 왼쪽, 1을 오른쪽이라 대입할 때

1을 하나씩 더해가는 이진법 규칙과 동일하다.

이것만 이용하면 해결할 수 있을 것 같은데.. 왜 안될까.. 왜 안될까...

- 2017.02.10 6:33