[자료구조](12)[이진트리의 구현 1]

연결리스트로 구현

이진트리 ADT

• 데이터 <element, left_pointer, right_pointer>
  연결 리스트로 구현할거라 포인터 필요
• root: 트리의 맨 위를 가리키는 포인터
• 연산
  find(): 트리에 있는 데이터 찾기 (이 트리에서는 중복이 없다고 가정한다.)
  insert_l(): 노드 왼쪽에 데이터 넣기
  insert_r(): 노드 오른쪽에 데이터 넣기
  delete(): 트리에 데이터 제거하기

기본 골조

이거는 포인터가 2개인 것 빼곤 다를 바 없다.

typedef struct Treenode {
    int data; //int형 데이터 담음
    struct Treenode* left; //node를 가리키는 포인터 선언
    struct Treenode* right;
} TreeNode;

TreeNode* makeTreeNode(int data){
    Node* newNode = (Node*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;  
    newNode->right = NULL; 
    return newNode;
}

find

재귀호출을 통해 특정 값을 갖는 노드의 포인터를 반환

TreeNode* find(TreeNode* root, int target) {
    if (root == nullptr) return nullptr;

    if (root->value == target) return root;

    TreeNode* leftResult = find(root->left, target);
    if (leftResult != nullptr) return leftResult;

    return find(root->right, target);
}

insert_l / insert_r

find로 찾은 노드의 왼쪽/오른쪽에 노드 삽입

void insert_l(int target, int data){
    TreeNode* root = find(target);
    root->left = makeTreeNode(data);
}

void insert_r(int target, int data){
    TreeNode* root = find(target);
    root->rigjt = makeTreeNode(data);
}

 

배열로 구현

완전 포화 이진트리, 완전 이진트리, 편향 이진트리는 특히 배열로 구현하기 좋다.
    왜냐하면 각 데이터의 위치가 다른 이진트리에 비해 경직되었기 때문!
    예를 들어 완전 이진트리는 맨 아래 레벨 전까지는 다 채워져 있고 마지막 레벨은 왼쪽부터 채워나가므로

    경우의 수가 1가지 밖에 없다!
그 중 자주 쓰는 완전 이진트리를 배열로 구현해 보겠다.

• 인덱스가 0부터 시작하는 경우
  위 트리는 배열로 보면 [1, 2, 3, 4, 5, 6, 7]처럼 배열될 것이다.
  이때 부모 인덱스를 p, 자식 인덱스를 c로 두고 부모 자식간 관계를 보면,

    자식의 인덱스 = 2p+1, 2p+2
    부모의 인덱스 = floor(c/2)-1

• 인덱스가 1부터 시작하는 경우
  부모-자식간 관계 계산을 좀 더 간단히 하기 위해 인덱스를 1부터 사용하기도 한다.
  부모 자식간 관계를 보면,

    자식의 인덱스 = 2p, 2p+1
    부모의 인덱스 = floor(c/2)

-> 연결 리스트처럼 탐색 때마다 포인털 접근하는게 아닌 인덱스로 바로 접근 가능해 효율적!