[Data Structure] Tree

ref : 윤성우 자료구조

트리란?

계층적(Hierarchical relationship) 관계를 표현하는 자료구조

트리에 대한 오해 선형 자료구조은 "데이터를 어떻게 추가하고 삭제하고, 검색하기 용이한 것" 이라고 볼 수 있지만, 트리와 같은 비선형 자료구조는 "데이터를 어떻게 표현하는지"에 관한 것

기본 용어

• node (노드)
• edge (간선)
• root node (최상위 노드)
• terminal node (= leaf, 단말노드)
• internal node (= non-terminal node, 내부 노드)
• sibling node (형제노드, 같은 레벨에 있는 노드)

이진 트리 (binary tree)

• 이진 트리란

  • 조건
    • 루트 노드가 두 개의 서브 트리를 가진다.
    • 각 서브 트리도 이진트리이다. (재귀적인 개념이므로 이진트리라는 용어를 쓰는 것을 허용한다)
  • 주의
    • 공집합(empty set) 도 이진 트리로 간주한다.

• 포화 이진 트리 (full binary tree)

  • 모든 레벨이 꽉 찬 트리

• 완전 이진 트리 (complete binary tree)

  • 모든 노드가 위에서 아래로, 왼쪽에서 오른쪽의 순서대로 빠짐없이 채워져있다 (빈칸 있을 수 있지만, 순서에 맞게 들어가야 한다)

• 이진 트리의 구현

  • 배열
    • 장점 : 링크드리스트에 비해서 탐색이 용이하고 빠르다
    • 단점 : 트리의 insert 와 delete 에 좋지 않다
    • 용도 : 힙 (완전 이진 트리)
  • 링크드리스트
    • 장점 : 트리의 insert 와 delete 가 용이하고 유연하다
    • 단점 : 배열에 비해 탐색이 느리다

binary tree의 구현

binarytree.h

//
//  binarytree.h
//  1107-1
//
//  Created by GaryNoh on 2017. 11. 7..
//  Copyright © 2017년 Macbook. All rights reserved.
//

#ifndef binarytree_h
#define binarytree_h


typedef int BTData;

/*
 구조체 정의
 */
typedef struct _bTreeNode{
    BTData data;
    struct _bTreeNode *left;
    struct _bTreeNode *right;
    
}BTreeNode;

/*
 ADT 정의
 */

BTreeNode *MakeBTreeNode(void); // 노드 하나 생성하기
BTData GetData(BTreeNode *bt); // 노드의 값 가져오기
void SetData(BTreeNode* bt, BTData data); // 노드에 값 설정하기

BTreeNode *GetLeftSubTree(BTreeNode *bt); //왼쪽 서브트리 가져오기
BTreeNode *GetRightSubTree(BTreeNode *bt); //오른쪽 서브트리 가져오기

void MakeLeftSubTree(BTreeNode *bt, BTreeNode *sub); //노드의 왼쪽에 child node 또는 sub tree 붙이기
void MakeRightSubTree(BTreeNode *bt, BTreeNode *sub); //노드의 오른쪽에 child node 또는 sub tree 붙이기


#endif /* binarytree_h */

binarytree.c

//
//  binarytree.c
//  1107-1
//
//  Created by GaryNoh on 2017. 11. 7..
//  Copyright © 2017년 Macbook. All rights reserved.
//

#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){
    //주의 : 기존에 null 이 아니라면 free (단, 노드가 하나일 때)
    //memory leak 을 방지하기 위해서는 트리 순회를 통해 모두 free 해줘야한다
    if(main->left != NULL) free(main->left);
    main->left = sub;
}


void MakeRightSubTree(BTreeNode *main, BTreeNode *sub){
    //주의 : 기존에 null 이 아니라면 free (단, 노드가 하나일 때)
    //memory leak 을 방지하기 위해서는 트리 순회를 통해 모두 free 해줘야한다 
    if(main->right != NULL) free(main->right);
    main->right = sub;
}

main.c

//
//  main.c
//  1107-1
//
//  Created by GaryNoh on 2017. 11. 7..
//  Copyright © 2017년 Macbook. All rights reserved.
//

#include <stdio.h>
#include "binarytree.h"

int main(int argc, const char * argv[]) {
    BTreeNode *bt1 = MakeBTreeNode();
    BTreeNode *bt2 = MakeBTreeNode();
    BTreeNode *bt3 = MakeBTreeNode();
    BTreeNode *bt4 = MakeBTreeNode();
    
    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);
    
    MakeLeftSubTree(bt1, bt2);
    MakeLeftSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);
    
    printf("node1 data : %d\n",GetData(bt1));
    printf("node2 data : %d\n",GetData(bt2));
    printf("node3 data : %d\n",GetData(bt3));
    printf("node4 data : %d\n",GetData(bt4));


    return 0;
}

이진 트리의 순회 (binary tree traversal)