[Algorithm] Binary tree

이진트리란 ?

모든 노드의 자식노드가 2개 이상을 넘지 않는 트리를 말한다.

왼쪽자식노드는 부모노드의 값보다 작이야 하며 오른쪽 자식노드는 부모노드의 값보다 커야한다.

 

이진트리 의 종류

 

<Full Binary Tree>

모든 레벨의 노드가 꽉 차있는 트리를 말한다. Full Binary Tree의 총 노드수는 2 ^ n -1 이다.(n은 마지막 레벨)

<완전 이진트리>

높이가 h인 트리의 경우 h-1까지는 모두 채워져있고 마지막 높이 h는 다 채워져있지는 않지만

왼쪽에서 오른쪽으로 순서대로 채워져있는 트리

 

이진트리를 순회하는 방법은 preorder, inorder, postorder가 있다.

루트 방문순서를 기준으로 이름이 붙여진것으로 이해하면 좋다  pre : 처음, in : 중간,  post : 나

 

쓰레드 이진트리란 ?

이진트리를 구성하다보면 null 포인터가 생기는데 이 널포인터를 순회할때 사용하는 구조를 쓰레드 이진트리라고 한다.

왼쪽의 널포인터는 현재노드 순회하기전에 노드를 가리키고, 오른쪽의 노드는 현재노드를 순회하고 난 다음의 노드를 가리킨다.

그리고 가장 처음 방문하는 노드의 왼쪽 널포인터, 가장 마지막에 방문하는 오른쪽 널포인트는 어느것도 가리키지 않으므로

헤드노드를 만들어서 그것을 가리키게 한다.

 

장점으로는 순회를 한후 다음 노드로 가기위해 왔던 노드들을 다시 지나가는 것을 불필요한 작업을 제거할 수 있다.

Animated Binary Tree : http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html

이진트리 코드 : http://www.cprogramming.com/tutorial/lesson18.html