트리는 말 그대로 나무의 가지모양을 닮은 자료구조입니다. 나무가지를 뒤집어 놓고 생각해보면 부모 줄기에서 자식 가지가 갈라지고, 그 자식 가지는 또 다른 자식 가지들로 갈라집니다. 이렇게 하나의 부모와 여러개의 자식의 연결을 모델링한 것을 트리(Tree)라고 합니다.트리는 실제 생활에서도 흔히 볼 수 있는 데이터 구조입니다. 가족관계, 조직도, 행정구역 등이 모두 트리로 모델링될 수 있습니다.
트리는 지금까지 배워온 연결리스트, 배열, 스택, 큐와 달리 비선형 자료구조입니다. 즉 앞과 뒤만으로 설명할 수 없는 고차원의 자료구조입니다. 따라서 비선형 구조만의 독특한 동작과 개념들이 있습니다. 대표적으로 트리의 노드 순서를 매기는 순회(Traversal)를 들 수 있습니다.
이번 장에서는 트리의 기본적인 개념, 그리고 트리를 어떻게 구현할 수 있는지를 알아보고, 트리 중에서도 가장 단순한 형태인 이진 트리를 이용하여 수식을 모델링하는 방법을 알아 봅니다.
강의 파일
강의 동영상
7.0 트리 - 시작 : 연결리스트의 확장 개념이라 할 수 있는 트리에 대해 배워봅니다. 어떤 내용을 배울지 확인합니다.
7.1 트리의 개념 : 트리가 무엇인지 예를 통해 알아보고, 트리에서 사용되는 용어들에 대해 알아봅니다.
7.2 이진 트리의 개념 : 트리 중에서 자식이 최대 두개인 트리를 이진트리라고 합니다. 이진트리는 트리 중에서 가장 많이 쓰입니다. 이 이진트리의 속성에 대해 배워봅니다.
7.3 이진 트리의 구현 : 연결리스트를 이용하여 트리를 구현하는 방법을 자세히 알아봅니다.
7.4 트리의 순회 : 트리는 비선형구조여서 노드를 나열하는 순서가 여러가지일 수 있습니다. 트리의 노드를 빠짐없이 방문하는 여러가지 방법을 알아보고 이들을 구현하고 실제로 돌려봅니다.
7.5 수식 트리 : 수식의 연산자는 두개의 항을 가지기 때문에 이진트리로 모델링할 수 있습니다. 수식을 트리로 모델링하면 순회 방법에 따라 수식의 표기법을 쉽게 변경하거나 연산을 할 수 있습니다. 이에 대해 알아봅니다.
7.6 수식 트리의 구현 : 앞서 수식트리의 개념에 대해 살펴 보았으니, 이제 실제로 C++로 구현하고 돌려봅니다.
7.9 트리 - 결론 : 지금까지 배워 온 트리에 대해 정리하는 시간을 가져 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 이진트리의 종류에 대하여 (오류 수정)
- 6장 : 스택과 큐
- 8장 : 재귀 호출
