1. 트리의 개념
트리란 모든 노드들이 부모와 자식 관계로 연결된 자료구조이다. 부모가 없는 노드를 루트 노드라고 하고, 자식이 없는 노드를 단말 노드라고 한다. 같은 부모를 가진 노드를 형제 노드라고 하고, 부모의 부모 이상의 노드들을 조상 노드라고 한다. 자식의 개수를 차수라고 하고, 루트노드를 0 level로 시작해서 자식관계가 거듭될수록 하나씩 올라가는데, 트리의 최대 level을 트리의 높이라고 한다. 이진트리란 모든 노드의 차수가 2 이하인 트리를 말한다.
2. 트리의 구현
트리를 구현하기 위해서는 연결 리스트를 이용한다. 이 글에서는 이진 트리를 구현하는 방법만 다룬다. 트리를 구성하는 연결 리스트의 노드 구조체는 세 개의 멤버변수를 가진다. 하나는 노드의 자료를 저장 할 변수이고, 하나는 자신의 왼쪽 자식을 가리키는 링크이고, 다른 하나는 자신의 오른쪽 자식을 가리키는 링크이다. 자식이 없다면, 링크는 NULL이다.
3. 트리의 연산
1) 삽입
트리에서 자료를 삽입할 때에는 노드들의 부모 자식 관계만 잘 맞춰주면 된다. 삽입할 위치의 부모 노드와 자식 노드들을 잘 고려해서 링크를 수정해 준다.
2) 삭제
트리에서 자료를 삭제할 때에도 노드들의 부모 자식 관계만 잘 맞춰주면 된다. 삭제한 뒤의 노드들의 부모자식 관계를 잘 고려하여 링크를 수정해 준다.