데이터 구조의 이진 트리 ADT

<시간/>

기본 개념

이진 트리는 노드가 두 개 이상의 자식을 가질 수 없는 트리로 정의됩니다. 모든 노드의 최고 차수는 2입니다. 이것은 이진 트리의 차수가 0 또는 1 또는 2임을 나타냅니다.

데이터 구조의 이진 트리 ADT

위의 그림에서 이진 트리는 루트와 두 개의 하위 트리 TreeLeft와 TreeRight로 구성됩니다. 이진 트리의 왼쪽에 있는 모든 노드를 왼쪽 하위 트리라고 하고 이진 트리의 오른쪽에 있는 모든 노드를 오른쪽 하위 트리라고 합니다.

이진 트리에는 최대 두 개의 자식이 있습니다. 우리는 그들에게 직접적인 포인터를 할당할 수 있습니다. 트리 노드의 선언은 이중 연결 리스트와 구조적으로 동일하며, 노드는 키 정보와 다른 노드에 대한 두 개의 포인터(좌우)를 포함하는 구조입니다.

typedef struct tree_node *tree_ptr;
struct tree_node
{
   element_type element1;
   tree_ptr left1; tree_ptr right1;
};
typedef tree_ptr TREE;

엄격한 이진 트리

엄밀히 말하면 이진 트리는 모든 노드에 0 또는 2개의 자식이 있는 이진 트리로 정의됩니다. 어떤 노드에도 하나의 자식을 포함하지 않습니다.

기울기 트리

스큐 트리는 리프를 제외한 모든 노드에 하나의 자식 노드만 있는 이진 트리로 정의됩니다. 스큐 트리에는 왼쪽 스큐 이진 트리와 오른쪽 스큐 이진 트리의 두 가지 유형이 있습니다.

왼쪽으로 치우친 이진 트리

왼쪽 스큐 트리에는 왼쪽 자식에만 연결된 노드가 있습니다. 왼쪽 하위 트리만 포함하는 이진 트리입니다.

오른쪽으로 치우친 이진 트리

오른쪽 스큐 트리에는 오른쪽 자식에만 연결된 노드가 있습니다. 오른쪽 하위 트리만 포함하는 이진 트리입니다.

전체 이진 트리 또는 적절한 이진 트리

이진 트리는 모든 잎이 동일한 수준에 있고 모든 잎이 아닌 노드에 정확히 두 개의 자식이 있고 모든 수준에서 가능한 가장 많은 수의 노드로 구성되어야 하는 경우 전체 이진 트리로 정의됩니다. 높이 h의 전체 이진 트리에는 최대 2h+1 – 1개의 노드가 있습니다.

완전한 이진 트리

모든 잎이 아닌 노드에는 정확히 두 개의 자식이 있지만 모든 잎이 같은 수준에 속할 필요는 없습니다. 완전한 이진 트리는 모든 레벨이 마지막 레벨을 제외하고 가장 많은 수의 노드를 갖는 트리로 정의됩니다. 마지막 레벨 요소는 왼쪽에서 오른쪽 방향으로 채워야 합니다.

거의 완전한 이진 트리

거의 완전한 이진 트리는 오른쪽 자식이 있는 각 노드에도 왼쪽 자식이 있는 트리로 정의됩니다. 왼쪽 자식이 있다고 해서 오른쪽 자식이 있는 노드는 필요하지 않습니다.

일반 트리와 이진 트리의 차이점

이진 트리

나무의 적용