트리(tree)는 계층적인 자료를 표현하는데 적합한 자료구조 이다.
트리는 한개 이상의 노드(트리의 구성요소(로 이루어진 유한 집합이고, 루트(root) 노드와 서브트리(subtree)로 구분지을 수 있다. 트리는 값을 가진 노드와 노드 들을 연결해주는 간선 (edge)로 구성되어 있다.
루트 노트(A) : 계층 구조에서 가장 높은 곳에 있는 노드
부모 노드 - 자식노드 : D는 H의 부모노드가 되고, H는 D의 자식 노드가 된다.
형제 관계 : H 와 I, F 와 G는 각각 형제 관계 이다.
단말 노드(Leaf Node, or terminal node) : 자식 노드가 없는 노드 , 비단말 노드의 반대
차수(degree) : 자식 노드의 개수 , A의 경우 차수가 2, E의 경우 차수가 1 이다. 단말노드는 차수가 0이다.
레벨(level) : 트리의 각층에 번호를 매긴다. 루트의 레벨은 1이 되고, 한층씩 내려갈 수록 1씩 증가한다.
모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리 (binary tree)라고 한다.
모든 노드는 최대 2개까지의 자식 노드가 존재 할 수 있고, 모든 노드의 차수가 2 이하가 된다.
정의 : 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의 된다. 이진 트리의 서브 트리들은 모두 이진 트리여야 한다.
⇒ 루트를 제외하고 모두 정확히 하나의 부모노드만 갖기 때문이다.
높이가 인 이진트리는 최소 개의 노드를 가지고, 최대 개의 노드를 가진다.
개의 노드를 가지는 이진트리의 높이는 최대 이거나 최소 이 된다.
포화 이진 트리 (full binary tree)
완전 이진 트리 (complete binary tree)
기타 이진 트리
이진트리도 데이터를 저장하기 위한 자료 구조이고, 데이터는 노드의 데이터 필드를 이용하여 저장된다. 이진 트리를 순회 한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.
이진트리 순회방법은 전위, 중위, 후위 3가지 방법이 있다.
루트를 방문하는 작업을 V, 왼쪽 서브트리방문을 L, 오른쪽 서브트리 방문을 R이라 하자
전위순회(VLR) : 루트 먼저 방문 → 왼쪽 서브트리 방문 → 오른쪽 서브트리 방문
중위순회(LVR) : 왼쪽 서브트리 방문 → 루트 방문 → 오른쪽 서브트리 방문
후위순회(LRV) : 왼쪽 서브트리 방문 → 오른쪽 서브트리 방문 → 루트 방문
레벨 순회 : 각 노드를 레벨 순으로 검사하는 순회 방법 (간접적으로 큐 사용)
⌜C언어로 쉽게 풀어쓴 자료구조⌟ 개정3판, 천인국, 생능출판
https://gyoogle.dev/blog/computer-science/data-structure/Heap.html