이진 트리

이번 시간에는 트리를 다루어봅시다. 바로 본론으로 들어가겠습니다. 특별히 트리에서의 BFS와 DFS를 또 익힐 예정입니다. 저희는 0x16강에서 이진 검색 트리를 배우며 이미 트리라는 개념을 적당히 받아들였습니다. 당시에는 이런식으로 "꼭대기부터 아래까지 계층을 이루고 있고, 제일 꼭대기를 제외한 나머지 정점들은 위로 딱 1개와 연결이 되어있는 구조" 정도로만 받아들이고 넘어갔습니다. 그런데 이전 강의에서 배운 것도 있고 하니 잘 생각해보면 트리 또한 간선과 정점으로 이루어진 자료구조로, 그래프의 특별한 종류임을 알아차릴 수 있습니다. 이진 검색 트리 단원에서 소개했던 용어를 다시 한 번 정리하고 가겠습니다. 제일 꼭대기의 정점은 루트입니다. 간선으로 직접 연결된 상하 정점을 부모와 자식이라고 부릅니다...