트리(Tree)
1개 이상의 유한한 개수의 노드의 집합
루트 노드와 0개 이상의 겹치지 않는 아휘 나무 구조들의 집합으로 이루어짐
용어 정리
노드(node) 와 엣지(edge)
트리 는 전체적으로 노드(node) 와 엣지(edge) 또는 링크(link) 로 표현된다.
A, B, C, D, E, F, G 라는 특정 정보가 들어있는 것을 노드라고 한다.
선으로 연결되어있는 것을 엣지라고 부르며 정보들간의 관계를 나타낸다.
따라서, 트리는 기본적으로 노드와 엣지로 구성되어있다.
path
엣지에 의해 연결된 노드들의 집합을 말한다.
root node
최상위 노드를 말한다.
parent, children, siblin, grandparent, ancestor
자기 자신의 노드를 기준으로 아래와 같이 구분할 수 있다.
위의 부모 노드를 parent
아래의 자식 노드를 children
옆의 형제 노드를 siblin
부모 노드의 부모 노드를 grandparent
직계 상위 노드들을 ancestor
leaf
자식이 없는 노드를 말한다.
subtree
큰 트리에 속한 작은 트리를 말한다.
degree
하위 서브 트리의 개수를 말한다.
level
루트 노드부터 최하위 노드까지의 중첩되지 않은 path 의 노드 개수를 말한다.
트리의 종류
이진 트리 (Binary Tree)
모든 노드들이 둘 이하의 자식노드를 갖는 나무를 말한다.
노드가 하나도 없는 공집합이거나 루트 노드를 기준으로 왼쪽 이진 트리, 오른쪽 이진 트리로 이루어진 집합
완전 이진 트리 (Complete Binary Tree)
가장 마지막 level 을 제외한 모든 노드들이 가득 차있고
마지막 level 은 왼쪽부터 마지막 노드까지 빈칸이 없는 트리를 말한다.
포화 이진 트리 (Full Binary Tree)
마지막 level 까지 완전히 가득 차있는 이진 트리를 말한다.
순회 (Tree Traverse)
전위 순회 (Preorder Traverse)
뿌리의 루트를 먼저 방문한다.ROOT → LEFT → RIGHT
중위 순회 (Inorder Traverse)
왼쪽 하위 트리를 방문 후 루트를 방문한다.LEFT → ROOT → RIGHT
후위 순회 (Postorder Traverse)
하위 트리 모두 방문 후 루트를 방문한다.LEFT → RIGHT → ROOT
층별 순회 (Level Order Traverse)
위쪽 노드들부터 아래 방향으로 차례대로 방문한다.
