[Data Structure] 연결 리스트 : 트리

트리는 연결리스트를 기반으로 한 새로운 데이터 구조다.

연결 리스트에서 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은

2차원적으로 구성되어있다고 볼 수 있다.

 

각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다.

 

이진 트리 검색

가장 높은 층에서 트리가 시작되는 노드를 '루트' 라고 한다.

루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 '자식 노드' 라고 한다.

 

위의 그림을 살펴보자,

뭔가 규칙을 찾았는가?

 

왼쪽이 자식 노드는 자신의 값보다 작고 

오른쪽 자식 노드는 자신의 값보다 크다.

 

따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다.

 

#include <stdio.h>
#include <stdbool.h>
//이진 검색 트리의 노드 구조체
typedef struct node
{
    //노드의 값
    int number;

    //왼쪽 자식 노드 
    struct node *left;

    //오른쪽 자식 노드
    struct node *right;
}node;

//이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    //트리가 비어있는 경우 'false'를 반환하고 함수 종료
    if(tree == NULL)
    {
        return false;
    }

    //현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if(50 < tree -> number)
    {
        return serach(tree -> left);
    }
    //현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if(50 > tree -> number)
    {
        return search(tree->right);
    }
    //위 모든 조건이 만족하지 않으면 노드의 값이 50 이므로 'true' 반환
    else
    {
        return true;

    }
    
}

 

 

**====>>> 이진 트리 순회 코드 : junecode.tistory.com/50