Binary-tree

저장법

1. Linked List

예시)

struct __TREENODE{

  __TREENODE *left;

  __TREENODE *right;

};

2. Array

root를 Array내의 0번째 node라고 가정한다.

left child의 경우 parent node를 i라고 했을때 2i + 1

right child의 경우 parent node를 i라고 했을때 2i + 2...

 

순환법

1. Pre-Order Traversal (Depth-first traversal)

parent -> L-node -> R-node 순으로 접근하여 모든 subtrees에 방문하는방법

 

order(NODE* node){

   //자기 노드에 접근

  order(node->left);

  order(node->right);
}

 

2. In-Order Traversal (Symmetric traversal)

L-node -> parent -> R-node 순으로 접근하여 모든 subtrees에 방문하는 방법

 

order(NODE* node){

  order(node->left);

//자기 노드에 접근

  order(node->right);
}

 

3. Post-Order Traversal

L-node -> R-node -> parent 순으로 접근하여 모든 subtrees에 방문하는 방법

 

order(NODE* node){

  order(node->left);

  order(node->right);

//자기 노드에 접근
}

 

4. Level-Order Traversal (Breadth-first traversal)

Root Node를 시작으로 인접한 모든 Node를 순서대로 방문한다.

Level이 낮은 순서부터 Level이 깊은 순서대로 순차적으로 방문

 

기본적으로 Search를 위한 접근법이라 설계법은 생략(치졸한 변명이지만 못하겠다는건 아니고..)

 

과제기계로 활동하던 중에 정리해보았음.