[C]Binary Tree Traversal(chap_1)

Binary Tree Traversal

Traversal이란?

-트리의 각 노드를 방문하는 과정이다!

Why the TraverSal necessary?

-특정 노드의 존재여부를 조회 할 수 있다.
-삽입/삭제가 잘되었는 확인 할 수 있다.

---

그러면 어떤 방식으로 노드를 다 확인 할 수 있지?

Categorization of traversals

//Recursive를 이용하여 트리의 노드를 각각 순차적으로 순회 할 수 있으며, Recursive의 코드는 트리의 모든 부분을 쉽게 방문할 수 있게 해준다.

[트리 구조]

[출처: 박종혁 교수님 수업 자료]

Inorder traversal: LCR

[LCR 트리 구조]

[출처: 박종혁 교수님 수업 자료]

void Inorder(BTreeNode* root)
{
 if(root != NULL){
   Inorder(root->left_child);
   printf("%d ", root->item);
   Inorder(rood->right_child);
  }
}

-왼쪽 서브트리-> 루트 노드 -> 오른쪽 서브트리 순서로 방문

Preorder traversal: CLR

[CLR 트리 구조]

[출처: 박종혁 교수님 수업 자료]

void Preorder(BTreeNode* root)
{
 if(root != NULL){
   printf("%d ", root->item);
   Preorder(root->left_child);
   Preorder(rood->right_child);
  }
}

-루트 노드-> 왼쪽 서브트리-> 오른쪽 서브트리 순서로 방문

Postorder traversal: LRC

[LRC 트리 구조]

[출처: 박종혁 교수님 수업 자료]

void Postorder(BTreeNode* root)
{
 if(root != NULL){
   Postorder(root->left_child);
   Postorder(rood->right_child);
   printf("%d ", root->item);
  }
}

-왼쪽 서브트리-> 오른쪽 서브트리-> 루트 노드 순서로 방문

Level Order Traversal

-이 방법은 각 레벨의 전체 노드를 방문 순회할 수 있는 방법
//각 레벨에 대해 왼쪽에서부터 오른쪽으로 방문

Traversal a tree bt using a queue (FIFO)

-First in_ First out 방식인 큐를 이용하여 각각의 레벨의 노드를 순차적으로 순회하며 확인할 수 있다.

[Queue를 사용한 Traversal트리 구조]

[출처: 박종혁 교수님 수업 자료]

void Levelorder(BTreeNode* root){
    Queue queue;
    if(root == NULL) return;

    InitQueue(&queue);
    EnQueue(&queue,root);
    while(!IsEmpty(&queue)){
        root = Peek(&queue);
        DeQueue(&queue);

        printf("%d ",root->item);
        if(root->left_child!= NULL)
            EnQueue(&queue,root->left_child);
        if(root->right_child!= NULL)
            EnQueue(&queue,root->right_child);
    }
}

\코드에 대한 풀이를 간다하게 해보자면, 부모 노드가 첫번째로 EnQueue가 되어 큐에 저장된 후 저장된 부모 노드가 DeQueue가 되면서
그 부모노드의 Left_chlid와 right_child를 EnQueue 해주는 방식으로, 큐가 비어있을 때까지 반복하며 노드의 모든 값을 확인하며
순회할 수 있다. 이 방법은 사람이 보기에 가장 직관적이며, 이해하기 간편한 방법인거 같다.

Binary Tree Traversal(chap_1)정리

-이번 챕터의 중요한 부분은 트리를 서브 트리로 분리하여 이를 논리적으로 이해하는 부분이 중요하며, Recursive를 이용한, 각각의 노드를 방문하는 방법에 대해 잘 생각해볼 필요가 있다. 단순히 각각의 노드를 방문하는 것이 아니라 어디에서부터 어떤식으로 각 위치의 노드에 방문할 것 인지 논리적으로 고민해보자! 다음은 Expression Tree와 Threaded Binary Tree에 대해 알아보자!