트리 : 계층적 구조를 갖는 자료들을 표현하기 위한 자료구조 탐색형 트리 자료 구조 - 예: 이진 검색 트리

트리 구성 요소 :

트리는 자료가 저장된 노드들이 간선으로 서로 연결되어 있는 자료 구조 상위노드 : 부모 하위노드 : 자식 부모 노드가 같은 두 노드 : 형제 노드 부모 노드와 그의 부모들을 통틀어 : 선조 자식 노드와 그의 자식들을 통틀어 :자손 트리에서 노드는 여러개의 자식을 가질 수 있어도 부모는 딱 하나 모든 노드들을 자손으로 가지는 1개의 노드 = 뿌리 노드 혹은 root 자식이 하나도 없는 노드 : 리프(leaf)

트리와 노드의 속성 :

루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 해당 노드의 깊이(depth) 가장 깊숙히 있는 노드의 깊이를 해당 트리의 높이(height)

트리의 재귀적 속성 :

트리에서 한노드와 그의 자손들을 모두 모으면 그들도 하나의 트리가 됨 어떤 노드 t와 그 자손들로 구성된 트리를 t를 루트로 하는 서브트리(subtree) 모든 트리는 루트와 루트 밑에 있는 서브트리들의 집합

트리의 표현 :

일반적인 형태는 각 노드를 하나의 객체로 표현하고, 자신의 부모와 모든 자손들에 대한 포인터를 가진다.

트리의 순회

트리의 재귀적 속성을 이용해서 모든 자료를 순회한다 트리의 루트가 주어질 때, 루트를 방문한 뒤, 각 서브트리를 재귀적으로 방문하는 함수로 순회 서브트리의 개념으로 트리의 높이도 구할 수 있음, 루트의 각 자신들을 루트로 하는 서브트리의 높이를 각각 재귀호출로 구하고, 최대치에 1을 더한다.