23. 이진탐색트리

이진트리

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리구조이다.

 

이진탐색트리

이진트리 중에서 특정한 규칙을 가진 트리이다.

 1. 모든 노드는 유일한 키 값을 가진다.

 2. 왼쪽 서브트리에 있는 노드들의 키 값은 현재 노드의 키 값보다 작다.

 3. 오른쪽 서브트리에 있는 노드들의 키 값은 현재 노드의 키 값보다 크다.

---

이진탐색트리 구조체

typedef struct Node *Nodepointer;
typedef struct Node{
    int key;
    Nodepointer l_child;
    Nodepointer r_child;
}Node;

---

이진탐색트리 삽입

아래는 이진탐색트리에 데이터를 삽입하는 함수이다.

삽입하려는 데이터가 현재 노드보다 작다면 왼쪽 자식, 크다면 오른쪽 자식에 삽입한다.

Nodepointer createNode(int key){
    Nodepointer new_Node = (Nodepointer)malloc(sizeof(Node));
    
    new_Node->key = key;
    new_Node->l_child = NULL;
    new_Node->r_child = NULL;
    return new_Node;
}

Nodepointer Insert(Nodepointer root, int key){
    if(root == NULL) root = createNode(key);
    else if(key < root->key) root->l_child = Insert(root->l_child, key);
    else root->r_child = Insert(root->r_child, key);
    return root;
}