Binary Tree1 [자료구조] Binary Tree(이진 트리) - CS면접 대비 이번 글에서는 컴퓨터 프로그래밍에서 자주 사용되는 자료구조 중 하나인 이진 트리에 관한 내용을 정리해보고자 한다. 1. 이진 트리의 정의 및 성질 먼저, 이진 트리(binary tree)는 공백이거나 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리라고 하는 2개의 분리된 이진 트리로 구성된 노드의 유한 집합이다. 이진 트리와 일반적인 트리의 주요한 차이점은 다음과 같다. 일반 트리의 경우 0개의 노드를 가질 수 없으나, 공백 이진 트리는 존재함 일반 트리는 자식의 순서를 구분하지 않으나, 이진 트리는 왼쪽 자식과 오른쪽 자식을 구별함 또한, 이진 트리는 노드의 수와 관련하여 다음과 같은 성질을 갖는다. 레벨 i 에서의 최대 노드 수는 2^(i -1) → 예) 레벨 3에서 최대 노드의 수는 4개 깊이.. 2021. 11. 16. 이전 1 다음 반응형
