[Data Structures] 트리 (Tree)

1. 트리는 계층적 관계를 표현하는 비선형 자료구조

• 노드 (Node) : 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소
• 간선 (Edge) : 노드와 노드를 연결하는 연결선
• 루트 노드 (Root Node) : 트리 구조에서 최상위에 존재하는 A와 같은 노드
• 단말 노드 (Terminal Node) : 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드
• 내부 노드 (Internal Node) : 단말 노드를 제외한 모든 노드로 A, B와 같은 노드

 

 

 

 

2. 이진 트리(Binary Tree)와 서브 트리(Sub Tree)

• 서브 트리 : 큰 트리에 속하는 작은 트리

출처: https://hyunyoung2.github.io/2016/03/24/Tree/

• 이진 트리 : 1. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다 2. 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다 3. 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다

출처: https://velog.io/@honeyricecake/CH-8-1-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B0%9C%EC%9A%94

• 포화 이진 트리와 완전 이진 트리

출처: https://velog.io/@honeyricecake/CH-8-1-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B0%9C%EC%9A%94

 

 

 

 

3. 배열 기반 트리와 연결 리스트 기반 트리

• 완전 이진 트리 구조를 갖는 배열 기반 트리는 힙 heap 이라는 자료구조에 주로 사용
• 연결 리스트 기반의 트리는 이해가 빠르고 쉽다

출처: https://velog.io/@honeyricecake/CH-8-2-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B5%AC%ED%98%84

 

 

 

 

4. 연결 리스트 기반 트리의 헤더 파일 정의 및 구현

• 이진 트리의 구조체 BTreeNode는 노드를 표현함과 동시에 이진 트리를 표현한 결과가 된다
• 자식 노드가 하나도 없는 노드도 그 자체로 이진 트리이다

//"BinaryTree.h"
#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
 
typedef int BTData;
typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
} BTreeNode;
 
BTreeNode * MakeBTreeNode(void);
//노드를 생성하여 주소 값 반환
BTData GetData(BTreeNode * bt);
//노드에 저장된 데이터 반환
void SetData(BTreeNode * bt, BTData data);
//노드에 데이터 저장
BTreeNode * GetLeftSubTree(BTreeNode * bt);
//왼쪽 서브 트리 주소 값 반환
BTreeNode * GetRIghtSubTree(BTreeNode * bt);
//오른쪽 서브 트리 주소 값 반환
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
//main으로 전달된 노드의 왼쪽에 sub로 전달된 노드 연결
void MakeRIghtSubTree(BTreeNode * main, BTreeNode * sub);
//main으로 전달된 노드의 오른쪽에 sub로 전달된 노드 연결
 
#endif
 
 
//"BinaryTree.c"
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
 
BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd
}
BTData GetData(BTreeNode * bt)
{
    return bt->data;
}
void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}
BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}
BTreeNode * GetRIghtSubTree(BTreeNode * bt)
{
    return bt->right;
}
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if (main->left != NULL)
        free(main->left)
    main->left = sub;
}
void MakeRIghtSubTree(BTreeNode * main, BTreeNode * sub)
{
    if (main->right != NULL)
        free(main->right)
    main->right = sub;
}

 

 

 

 

5. 이진 트리의 순회 (Traversal)

• 위의 MakeLeftSubTree에서 free로 한번의 호출을 하지만, 삭제할 서브 트리가 여러 개의 트리로 이루어져 있다면 메모리의 누수로 이어진다
• 따라서 재귀적인 순회가 필요하다
  1. 전위 순회 (Preorder Traversal) - root node를 먼저!
  2. 중위 순회 (Inorder Traversal) - root node를 중간에!
  3. 후위 순회 (Postorder Traversal) - root node를 마지막에!
   

출처: https://velog.io/@honeyricecake/CH-08-3-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%88%9C%ED%9A%8C

 

• 중위 순회 함수의 구현

출처: https://hyunyoung2.github.io/2016/03/24/Tree/

 

 

• 전위, 중위, 후위 함수 구현 

출처: https://hyunyoung2.github.io/2016/03/24/Tree/

 

• 노드의 방문 이유를 printf("%d \n", bt->data) 말고도 함수 포인터를 전달하여 다양하게 데이터를 처리할 수 있다

//"BinaryTree.h"
typedef void VisitFuncPtr(BTData data);
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
void IreorderTraverse(BTreeNode * bt, VisitFuncPtr action);
 
//"BinaryTree.c"
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
    if(bt==NULL)
        return;
    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}
 
//"BinaryTreeMain.c"
void ShowIntData(int data);
int main(void)
{ ...PreorderTraverse(bt1, ShowIntData); }
void ShowIntData(int data)
{
    printf("%d ", data);
}

 

 

 

 

 

6. 수식 트리 (Expression Tree)의 구현

• 이진 트리를 이용해 수식을 표현해 놓은 것
• 루트 노드에 저장된 연산자의 연산을 하되, 두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 한다
• 중위 표기법의 수식을 바로 연산하는 것은 쉽지 않기때문에, 후위 표기법으로 변환 후 계산한다

출처: https://hyunyoung2.github.io/2016/03/28/Expression_Tree/

• 수식 트리 구성 방법
  1. 피연산자를 만나면 무조건 스택으로 옮긴다
  2. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내어 자식 노드로 연결한다 (이때, 먼저 꺼내진 피연산자가 오른쪽 자식노드, 그 다음에 꺼내진 피연산자가 왼쪽 자식노드가 된다)
  3. 자식 노드를 연결해서 만들어진 트리는 다시 스택으로 옮긴다
    
•  

 

 

• 수식 트리 구현에 필요한 헤더파일과 구현
  1. 이진 트리를 정의한 BinaryTree.h, BinaryTree.c
  2. 연결리스트 기반 스택 ListBaseStack.h, ListBaseStack.c
  3. ExpressionTree.h

  //"ExpressionTree.h"
  #ifndef __EXPRESSION_TREE_H__
  #define __EXPRESSION_TREE_H__
  #include "BinaryTree.h"
   
  BTreeNode * MakeExpTree(char exp[]);     // 수식 트리 구성
  int EvaluateExpTree(BTreeNode * bt);     // 수식 트리 계산
  void ShowPrefixTypeExp(BTreeNode * bt);    // 전위 표기법 기반 출력
  void ShowInfixTypeExp(BTreeNode * bt);    // 중위 표기법 기반 출력
  void ShowPostfixTypeExp(BTreeNode * bt);    //후위 표기법 기반 출력
  #endif
   
   
  //"ExpressionTree.c"
  #include "ListBaseStack.h"
  #include "BinaryTree.h"
   
  //수식 트리 만들기
  BTreeNode * MakeExpTree(char exp[])
  {
      BTreeNode * pnode;
      Stack stack;
   
      int expLen = strlen(exp);
      int i;
      StackInit(&stack);
      
      for(i=0; i<expLen; i++)
      {
          pnode = MakeBTreeNode();
          
          if(isdigit(exp[i]))
          {    
              SetData(pnode, exp[i]-'0')
          }
          else
          {
              MakeRightSubTree(pnode, SPop(&stack));
              MakeLeftSubStree(pnode, SPop(&stack));
              SetData(pnode, exp[i]);
          }
          SPush(&stack, pnode);
      }
      
      return SPop(&stack);
  }
   
  //수식 트리의 계산
  int EvaluateExpTree(BTreeNode * bt)
  {
      int op1, op2;
      if (GetLeftSubTree(bt)==NULL && GetRightSubTree(bt)==NULL) //단말 노드라면
          return GetData(bt);
   
      op1 = EvaluateExpTree(GetLeftSubTree(bt));
      op2 = EvaluateExpTree(GetRightSubTree(bt));
      
      switch(GetData(bt))
      {
      case '+':
          return op1+op2;
      case '-':
          return op1-op2;
      case '*':
          return op1*op2;
      case '/':
          return op1/op2;
      }
      return 0;
  }