블로그 이사 중입니다 >> gumgood.github.io

Tree Traversal 본문

Problem Solving/분류없음

Tree Traversal

gumgood 2017. 5. 27. 02:58

- Tree : 계층적 자료를 표현하기 위한 자료구조

- Binary tree :  모든 node에 최대 두 개의 child가 있는 tree


  Tree의 순회에 앞서 Tree의 정의와 용어에 대해 서술한다.


1. Tree의 정의와 용어

  1.1 tree의 구성요소

    - tree는 자료가 저장된 node들이 edge로 계층적으로 연결되어 잇는 자료구조를 말한다.

    - 연결된 두 node중 상위 node를 parent, 하위 node를 child라 부른다.

    - parent node들을 통틀어 ancestor라 하고, child node를 통틀어 descendant라 한다.

    - 다른 모든 node들을 child로 갖는 node를 root, child가 없는 node를 leaf node라 한다.

  1.2 tree와 node 속성

    - node 깊이 : root node에서 해당 node까지 도달하기 위해 거치는 edge의 수

    - node 높이 : 가장 깊숙히 있는 node의 높이

  1.3 tree의 재귀적 속성

    - 어떤 node t와 그 child 구성된 tree를 't를 root로 하는 subtree'라 한다.

    - 따라서 모든 tree는 root와 root 밑에 있는 subtree들의 집합니다.


2. Tree traversal

    - Preorder traversal : (root node) -> (left subtree) -> (right subtree)

    - Inorder traversal : (left subtree) -> (root node) -> (right subtree)

    - Postorder traversal : (left subtree) -> (right subtree) -> (root node)


3. Tree traversal 구현

  C++11


4. Tree traversal 시간복잡도

  각 node당 한번식 방문하므로 


'Problem Solving > 분류없음' 카테고리의 다른 글

Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tree Traversal  (0) 2017.05.27
Treap  (0) 2017.05.27
Priority Queue & Heap  (0) 2017.05.27
0 Comments
댓글쓰기 폼