[2019 동계 모각코] 4차시 - 결과

 

이진트리

이진트리 구조를 이해하고 구현하는 것을 목표로 함

 

---

이진트리를 구현하는 BinaryTree클래스를 작성했고 이 클래스는 트리 삽입 메소드, 트리 탐색 메소드, 후위순환 메소드, 트리 깊이 계산 메소드로 구성된다.

​

1) 필드 변수와 생성자

left와 right는 key를 기준으로 왼쪽, 오른쪽으로의 연결을 나타낸다.

​

2) 삽입메소드

: BinaryTree형의 포인터를 만들어 삽입할 자리에 이동해 삽입한다.

: key의 값보다 작은 수는 왼쪽에 큰수는 오른쪽에 삽입한다.

트리는 key값을 기준으로 왼쪽과 오른쪽으로 나누어져 경우를 나누는게 중요한 것을 느꼈다.

​

3) 탐색메소드

: 탐색할 값을 key값과 비교하며 포인터를 이동시켜 찾는다.

​

4) 후위순회 메소드

: 재귀를 이용하여 트리를 순회하면서 순회할 자식이 없거나 자식을 순회했을 경우 자신을 방문처리한다.

트리의 왼쪽 부분과 오른쪽 부분으로 나눠 재귀를 한다.

자식이 없을경우에 자신을 프린트한 후 메소드를 끝내고, 자식을 순회했을 경우 left.postorder();와 right.postorder(); 가 끝나고 자신을 프린트한다.

이때 프린트를 재귀 앞으로 옴기면 전위순회, 중간에 넣으면 중위순회, 마지막에 넣으면 후위순회가 된다.

​

5) 높이 계산 메소드

: 재귀를 통해 왼쪽과 오른쪽으로 나눠 높이를 계산한다.

자식이 둘다 없을 경우 0을 반환하고 자식이 둘중에 하나만 없을경우 그 높이에 1을 더해서 반환한다.

자식이 둘다 있는 마지막 경우엔 왼쪽과 오르쪽 중에서 더 큰 트리의 높이에 1을 더한값을 반환한다.

​

---

느낀점

이진트리를 구현할 때 삽입 메소드와 탐색 메소드를 작성해보면서 조건을 잘 정하는 것이 중요하다는 것을 많이 느꼈다. 이진트리 구조가 어려웠지만 연결리스트를 생각하면서 이해하는 방법이 도움이 됐다. 특히 이진트리를 하면서 디버깅을 많이 했는데 이진트리를 구현하고 이해하는데 많은 도움이 됐고 디버깅을 앞으로 잘 사용할 수 있을 것 같았다.