[자료구조 트리] What is Binary Tree? / 이진 트리란?

이진 트리(Tree)에 대해 알아보자

 

이진 트리(Tree)

    - 자식 노드가 두 개씩 달린 트리

    - 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고,

    - 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다

 

    다음은 이진트리의 예시이다

출처) 윤성우의 열혈 자료구조

    다음과 같이 이진 트리에 두 개의 자식 노드가 있지 않더라도 EMPTY 노드가 존재한다고 판단한다

 

출처) 윤성우의 열혈 자료구조

    다음의 두 이진 트리는 각각 다른 이진트리로 구분하여야 한다

출처) 숙명여대 박영호 교수님 데이터구조 강의자료

이진트리의 특성

    - 이진트리의 level i에 있는 node의 최대 개수는 2**(i-1)이다 (i >= 1)

    - 깊이(depth) k의 이진트리에 있는 node의 최대 개수는 2**k - 1이다 (k >= 1)

    - degree가 2인 어떤 노트와 leaf 노드의 개수 간의 관계

        - Non-empty binary tree T에 대해서

        ★ n(0) = n(2) + 1      [n(0) : leaf 노드 개수, n(2) : degree 2인 노트 개수]

 

 

포화 이진 트리(Full Binary Tree)

    - 모든 레벨이 꽉 찬 이진 트리

출처) 윤성우의 열혈 자료구조

 

완전 이진 트리(Complete Binary Tree)

    - 모든 레벨이 꽉찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리

 

출처) 윤성우의 열혈 자료구조

    - 좌측부터 노드가 삽입되어 다음과 같은 트리고 완전 이진 트리이다

출처) 윤성우의 열혈 자료구조

 

이진 트리 ADT

출처) fundamentals of data structures in c - horowitz

 

이진 트리 구현

    - 배열로 표현하는 방법

        - 편의상 첫 배열은 비워놓는다

        - 다음과 같이 구현한다

출처) fundamentals of data structures in c - horowitz

    - 연결 리스트로 표현하는 방법

        - 연결 리스트로 표현하기 위해 다음과 같은 구조체를 선언한다

 

출처) fundamentals of data structures in c - horowitz

        - 다음과 같이 구현한다

 

출처) fundamentals of data structures in c - horowitz