Tree
22 Jun 2021트리란 그래프의 일종으로 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리의 최상위 노드는 root node 라고 불리며 각각의 노드들은 parent node와 child node의 관계로 정의된다. 이 때 자식 노드가 없는 노드를 leaf node라고 부른다. 트리는 루트는 무조건 1개이고 각각의 노드별 자식의 갯수가 정해져 있지 않다.
그 중에서 자식의 갯수를 최대 2개로 제한한 트리를 이진트리라고 부른다. 완전 이진 트리란 이진 트리 중에서도 새로운 값이 추가되면 왼쪽 아래부터 채워진 이진트리를 말한다. 트리의 구현은 링크드리스트, Array 등 방법이 다양해서 경우에 맞게 사용하는 것이 좋다. 특히 완전 이진 트리의 경우 Array로 구현을 하는 경우가 많다.
