5.1.1 Terminology

  • Tree : 정보 data 가 branch 처럼 연결된 자료구조.
    1. root 라고 불리는 맨 꼭대기 node가 존재한다.
    2. 나머지 node 는 subtree를 구성함. (subtree 끼리는 중복 X)
  • 용어들
    • degree : subtree 의 갯수
    • degree of a tree : node 의 최대 degree
    • leaf / terminal node : 맨 아래 node. degree zero.
    • parent : subtree 를 가지고 있는 node
    • children : subtree의 뿌리들
    • siblings : 같은 parent 를 갖는 node들
    • ancestor : 모든 node 의 조상. root node
    • descendents : ancestor를 제외한 모든 node
    • level : root node부터 node까지 연결된 간선 수의 합
    • height / depth : node 의 maximum level

5.1.2 Representation of Trees

(A(B(E(K, L), F), C(G), D(H(M), I, J)))

  • linked list 사용 위해선, node에서 child 개수 만큼 link 만듬.

Left Child-Right Sibling Representation

  • node
    • left child
    • right sibling

글 이동

Comments

참고