[자료구조] 이진 트리 특징과 순회 방식 분석, 구현 및 활용

이진 트리 정의 : 공집합 또는 루트와 왼쪽/오른쪽 서브트리로 구성된 유한집합(서브트리는 이진트리) 모든 노드가 2개의 서브트리를 가지고 있는 트리 서브트리는 공집할 수 있음 특징 각 노드에는 최대 2개까지의 자식 노드가 존재 각 노드의 차수 ≤ 2 → 구현하기가 편리 서브트리간 순서 존재 ( L → R ) 성질 노드의 개수가 n개이면 간선의 개수는 n-1개 높이가 h인 이진 트리인 경우 최소 h개의 노드 최대 \(2^h-1\)개의 노드 n개의 노드를 가지는 이진 트리의 높이 최대 n 최소 \(log_2(n+1)\)(올림) 이진 트리의 분류 포화 이진 트리 트리의 각 레벨에 노드가 꽉 차있는 이진 트리 완전 이진 트리 높이가 h일때, 레벨 1부터 h-1까지는 노드가 모두 채워져 있음 마지막 레벨 h는 왼..

원문링크 : [자료구조] 이진 트리 특징과 순회 방식 분석, 구현 및 활용