투케이2K

106. (TWOK/STUDY) [투케이 기출] : 보기의 트리 (tree) 에서 차수 , 단말 , 부모 , 자식 , 형제 , 후손 값으로 옳은 것은 ? 본문

투케이2K 학습정리

106. (TWOK/STUDY) [투케이 기출] : 보기의 트리 (tree) 에서 차수 , 단말 , 부모 , 자식 , 형제 , 후손 값으로 옳은 것은 ?

투케이2K 2024. 12. 21. 09:44

[제 목]

[투케이 기출] : 보기의 트리 (tree) 에서 차수 , 단말 , 부모 , 자식 , 형제 , 후손 값으로 옳은 것은 ?

 

[설 명]

-----------------------------------------------------------------------------------------
[구 분]
-----------------------------------------------------------------------------------------

구분 : 투케이 기출 정리

제목 : 보기의 트리 (tree) 에서 차수 , 단말 ,  부모 , 자식 , 형제 , 후손 값으로 옳은 것은 ?

-----------------------------------------------------------------------------------------





-----------------------------------------------------------------------------------------
[설 명]
-----------------------------------------------------------------------------------------

1. 사전) 자료 구조 트리 설명 : 

  >> 자료구조에서의 트리는 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 방향 그래프입니다


2. 사전) 트리 관련 용어 설명 : 

  >> 노드(node): 트리를 구성하는 기본 원소
    - 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
    - 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
    - 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
    - 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
    - 리프 노드(leaf node/leaf): 차수가 0인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.
  >> 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
  >> 길이(length): 출발 노드에서 도착 노드까지 거치는 간선의 개수
  >> 깊이(depth): 루트 경로의 길이
  >> 레벨(level): 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합
  >> 높이(height): 가장 긴 루트 경로의 길이
  >> 차수(degree): 각 노드의 자식의 개수
  >> 크기(size): 노드의 개수
  >> 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기
  >> 내부 정점(internal vertex): 차수가 2 이상인 정점을 뜻한다.
  >> 포레스트(forest): 서로 독립인 트리들의 모임이다.
  >> 방향 트리(directed tree): 방향을 무시하고 생각했을 때 트리인 유향 그래프는 방향 트리이다. 자료구조의 트리는 방향 트리의 일종


3. 문제 : 보기의 트리 (tree) 에서 차수 , 단말 ,  부모 , 자식 , 형제 , 후손 값으로 옳은 것은 ?

  [보기]

                   A
                /  |  \
               B   C   D
             /  \  |  /  \
            E    F G H    I
           / \      /|\
          J   K    L M N



  [정답]

  차수 (가장 많은 선) : 3
  단말 (자식 없음) : J  K  F  G  L  M  N  I
  최대 레벨 (층 구분) : 4
  B 레벨 : 2
  B 부모 : A
  B 자식 : E  F 
  B 후손 : E  F  J  K 
  루트 : A 
  형제 노드 (같은 부모 가짐) : L  M  N 

-----------------------------------------------------------------------------------------





-----------------------------------------------------------------------------------------
[참고 사이트]
-----------------------------------------------------------------------------------------

https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

-----------------------------------------------------------------------------------------
 
반응형
Comments