공부하는 퓨퓨

트리의 정의

트리는 그래프의 특수한 형태로써 노드와 가지를 이용하여 사이클을 이루지 않도록 구성한 자료 구조이다.

(사이클이란 처음과 마지막 정점이 같은 경로인 것을 말한다.)

트리 관련 용어

• 노드 (Node) 트리의 기본 구성 요소이다.
• 근노드 (Root Node): 가장 상위에 위치한 노드이다.
• 레벨 (Level): 근노드를 기준으로 특정 노드까지의 경로 길이를 말한다.
• 조상 노드 (Ancestors Node): 어떤 노드에서부터 근노드에 이르는 경로상의 모든 노드이다.
• 부모 노드 (Parent Node): 어떤 노드에 연결된 이전 레벨의 노드이다.
• 자식 노드 (Child Node): 어떤 노드에 연결된 다음 레벨의 노드이다.
• 형제 노드 (Brother Node): 같은 부모를 가진 노드이다.
• 깊이 (Depth): 트리의 최대 레벨이다.
• 차수 (Degree): 어떤 노드에 연결된 자식 노드의 수이다.
• 단말 노드 (Terminal Node): 트리의 제일 마지막에 위치한 노드이다. (차수가 0인 것을 의미한다.)
• 트리의 차수 (Degree): 트리의 노드 중 가장 큰 차수이다.

이진 트리 (Binary Tree)

• 차수(연결된 자식 노드의 수가)가 2이하인 노드들로만 구성이 된 트리이다.
• 이 트리의 레벨 K에서 최대 노드의 수를 구하는 공식은 2^K-1이다. (깊이, 레벨이 5인 트리의 최대 노드수는 2^5-1이므로 31이다.)

이진 트리의 구조

• 정이진 트리: 첫 번째 레벨부터 마지막 레벨까지 모두 2개씩 채워진 트리이다.
• 전이진 트리: 정이진 트리에서 한쪽 방향 노드가 아예 존재하지 않는 트리를 말한다.
• 사향 이진 트리: 근노드로부터 한쪽 방향으로만 기울어진 트리를 말한다.

이진 트리의 운행법

전위(Preorder) 운행의 순서: Root → Left → Right

중위(Inorder) 운행의 순서: Left → Root →Right

후위(Postorder) 운행의 순서: Left → Right → Root

8진수에서 16진수로 변환할 수 있는 방법은 없다.

먼저 8진수를 2진수로 바꿔준 뒤에 16진수로 바꿔야 한다.

8진수 156을 16진수로  변환해보자.

156은 총 세자리로 이루어진다.

각각 한자리씩 2진수로 변환시켜준다.

이렇게 나온 156의 2진수인 001101110을 뒤에서 부터 4자리로 끊어준다.

(4자리인 이유는 우리가 변환해야 하는 16진수는 2⁴의 값이다, 즉 2의 4승에 대응되기 때문에 4자리씩 끊어서 계산해주는 것이다.)

4자리로 끊어준 값에 2진수의 가중치를 뒤에서부터 넣어준다.

넣은 가중치를 계산해준다.

10진수 14는 16진수에서 E로 표기된다.