[알고리즘]트리의 정의와 이진 트리

트리

• 계층적인 구조를 나타내는 자료 구조
• 보통 뿌리(root)가 위에, 나뭇가지(branch)와 잎(leaf)이 아래로 자라는 형태로 표현
• 트리 사용 예:회사 조직도, 대학 교과 과정의 수강 트리, 파일 시스템 디렉터리 구조

트리의 구성 요소

• 노드:트리의 데이터를 저장하는 원소 단위.정점.
• 에지: 
  • 노드와 노드를 연결하는 선. 간선.
  • 트리의 에지는 부모-자식 계층 관계만을 나타냄
  • 노드의 개수가 N이면 항상 N-1개의 에지가 존재

트리 용어

• 루트(root):맨 위의 노드
• 부모(parent)-자식(child):에지로 연결되어 있는 상대적인 관계. 위의 노드가 부모, 아래의 노드가 자식
• 리프(leap):가장 아래의 노드(가장 말단)
• 내부 노드(internal node):자식노드 중 리프가 아닌 것
• 형제(sibling):같은 부모를 가지는 노드들의 관계
• 조상(ancestor)-후손(descendant):어떠한 부모 노드, 부모의 부모들을 이루는 말
• 차수(degree):자기 자신의 자식 노드의 개수
• 레벨(level):루트로부터의 거리(루트의 레벨==0)
• 높이(height):노드 또는 트리 자체의 아래에서부터의 거리.
• 서브트리(subtree):특정 노드의 자식들로 이루어진 트리의 한 부분

이진트리(binary tree)

• 모든 노드가 최대 두 개의 자식을 갖는 트리
  • 모든 노드의 차수가 2 이하인 트리
  • 모든 노드가 2개의 서브트리를 가지고 있는 트리(서브 트리는 빈 트리(empty tree) 일 수 있음)
• 각각의 자식 노드는 부모의 왼쪽 자식(left tree) 또는 오른쪽 자식(right child)으로 지정됨

이진 트리의 종류

• 정 이진 트리(proper binary tree,full binary tree)
  • 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진 트리(즉,리프 노드를 제외한 노드들은 모두 자식이 2개임)
• 포화 이진 트리(perfect binary tree)
  • 트리의 모든 레벨에서 노드가 모두 채워져 있는 이진 트리
  • 높이가 h이면 노드 개수가 2^(h+1)-1
• 완전 이진 트리(complete binary tree)
  • 마지막 레벨을 제외한 모든 레벨에는 노드가 완전히 채워져 있고, 마지막 레벨에는 노드가 왼쪽부터 채워져 있는 이진 트리
• 균형 이진 트리(balanced binary tree)
  • 모든 노드의 서브 트리 간의 높이 차이가 1 이하
• 편향 트리(skewed tree)
  • 리프 노드를 제외한 모든 노드가 하나의 자식 노드만 갖는 트리

이진 트리 구현 방법

• 배열
• 연결 리스트
  • 저장할 데이터와 왼쪽 자식과 오른쪽 자식 노드를 가리키는 포인터 2개를 갖는 구조체를 사용

struct Node
{
	char data;
	Node* left;
	Node* right;

	Node(char d) : data(d), left(nullptr), right(nullptr) {}
};

int main()
{
	/*
	    A
	 B     C
	D E     F
	*/
	Node* root = new Node('A');
	root->left = new Node('B');
	root->right = new Node('C');
	root->left->left = new Node('D');
	root->left->right = new Node('E');
	root->right->right = new Node('F');
    }