이진트리

2. 이진 트리

2. 이진 트리의 소개 - 이진 트리의 정의 이진 트리 (binary tree) : 이진트리의 서브 트리들은 모두 이진트리여야 함 => 트리 중에서 가장 많이 쓰이는 트리 이진 트리의 정의 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의 이진 트리와 일반 트리의 차이점 이진 트리의 모든 노드는 차수가 2이하, 즉 자식 노드의 개수가 2이하지만 일반 트리는 자식 노드의 개수에 제한이 x 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있다 서브 트리간에 순서가 존재한다 (왼쪽 서브트리와 오른쪽 서브트리를 구별) - 이진 트리의 성질 n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가짐 => 이진트리에서의 노드는 루트를 제외하면 정확하게 하나..