Tree

○Tree

 ▷비선형 자료구조

 ▷선-후 관계 대신, 계층 구조를 가지는 자료구조 (부모 - 자식)

 

 ▶구성

  ▷Root: 부모가 없는 node (가장 상위의 node)

  ▷Internal node: 최소 하나의 자식을 가진 node

  ▷External node: 자식을 가지지 않은 node

  ▷Ancestors: 해당 node의 상위 node들 (부모, 부모의 부모, ...)

  ▷Depth: ancestors의 수

  ▷Height of tree: 최대 depth

  ▷Descendant: 해당 node의 하위 node들 (자식, 자식의 자식, ...)

  ▷Subtree: node와 그의 descendant로 이루어진 새로운 tree

 

 ▶ADT

  ▷각각의 abstract nodes에 대해 position을 적용함.

  ▶메소드

   ▶Generic

    ▷int size(): Tree의 크기

    ▷boolean empty(): 비어있는 Tree인가?

 

   ▶Accessor

    ▷position root(): Tree의 root의 position

    ▷list<position> positions(): 모든 노드의 positions

 

   ▶Position-based

    ▷position p.parent(): 노드의 부모

    ▷list<position> p.children(): 노드의 자식들

 

   ▶Query

    ▷boolean p.isRoot(): root인가?

    ▷boolean p.isExternal(): External node인가?

 

 

 ▶순회

  ▶Preorder Traversal (전위 순회)

   ▷방문 -> 자식 중 한명 방문 -> 자식의 자식 중 한명 방문 ...

 

  ▶Postorder Traversal (후위 순회)

   ▷자식의 자식 .. 방문 -> ... 자식 방문 -> 방문

 

 ▶구현

  ▶Linked Structure

   ▷Position ADT를 포함한다.

   ▷각 노드는 다음의 정보를 가진다.

    ▷Element (요소)

    ▷Parent node

    ▷Sequence of children nodes