자료구조 8 이진트리

일반적인 트리의 문제는 자식 노드의 갯수가 통제가 되지 않는다는 점이다. 

따라서, 데이터를 조회하는 데 드는 시간을 제어하기 어렵다.

 

이진 트리는 자식 노드의 갯수를 2개로 제한한다. 

하나의 기준을 가지고 이분하여 노드를 구성하기 때문에

조회에 있어서 탁월한 성능을 가질 수 밖에 없다

마치, 미분에서 뉴턴 메서드 처럼 말이다

 

---

이진트리의 순회 방법에는 총 3가지가 있다.

1. 전위 순회: 뿌리노드부터 시작 -> 왼쪽 자식노드 -> 오른쪽 자식노드 

2. 중위 순회: 왼쪽 하위 자식 노드 부터 왼쪽 트리-> 뿌리노드 -> 오른쪽 하위 자식 노드부터 하위 트리   

3. 후위 순회 : 왼쪽 하위 자식 노드 -> 오른쪽 하위 자식노드 -> 뿌리노드 

 

그리고 이는 링크르 리스트 스택에서 배웠던, 수식에도 똑같이 대응해 볼 수 있다. 

중위 순회를 돌 경우, 중위 표기식이

후위 순회를 돌 경우, 후위 표기식이 나오게 되는 것이다. 

 

트리를 파괴할 때도 후위순회를 사용할 수 있다.

자식노드에 동적으로 할당된 메모리부터 해제해야하므로

후위 순회 알고리즘을 사용해야한다. 

 

 

GitHub - Sukmin-LanternK/Tree

---

수식 트리를 구현할 수도 있다.

후위 순회 알고리즘은 후위표기식을 연산하는데 사용가능하다. 

후위 표기식을 트리에 입력하는 함수와

후위 표기식을 읽는 함수 -> 연산하는 함수로 변경만 하면 된다.