[자료구조]이진 트리 구현

이진 트리를 배열을 이용해 먼저 구현해 보자.

위 사진을 보면 0번째 배열은 사용하지 않고 1번에 A, 2번에 B ~ 순서로 저장한다.

 

 

이번엔 이진 트리를 연결 리스트를 이용해 구현해보자.

 

 

 

연결 리스트는 위와 같이 왼쪽, 오른쪽으로 구분한다.

선형 구조에서 앞,뒤로 구분한 것과 비슷하다.

 

#include<stdio.h>
#include<stdlib.h>

typedef int BTData;

typedef struct _bTreeNode{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
}BTreeNode;

//노드 생성,노드 초기화
BTreeNode * MakeTreeNode(){
    BTreeNode * newNode=(BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

//노드에 저장된 데이터를 반환
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;
}

int main(){
    BTreeNode * bt1 = MakeTreeNode();
    BTreeNode * bt2 = MakeTreeNode();
    BTreeNode * bt3 = MakeTreeNode();
    BTreeNode * bt4 = MakeTreeNode();
    BTreeNode * bt5 = MakeTreeNode();

    SetData(bt1,1);
    SetData(bt2,2);
    SetData(bt3,3);
    SetData(bt4,4);
    SetData(bt5,5);

    MakeLeftSubTree(bt1,bt2);
    MakeRightSubTree(bt1,bt3);
    MakeLeftSubTree(bt2,bt4);
    MakeRightSubTree(bt2,bt5);

    //bt1의 왼쪽 자식 노드의 데이터 출력
    printf("%d \n",GetData(GetLeftSubTree(bt1)));

    //bt2의 오른쪽 자식 노드의 데이터 출력
    printf("%d \n",GetData(GetRightSubTree(bt2)));
}