2진트리의 구조에 따라 full binary tree, complete binary tree, perfect binary tree라는 이름을 붙이더라구

 

요. 한국말로 전이진트리, 완전이진트리, 포화이진트리 근데 저게 찾아보니까 사이트 마다 다르더라구요.

 

1. 첫번째는, 애초애 full binary tree, complete binary tree 2가지 분류해서 full binary tree를 포화트리로

 

칭하며, perfect binary tree라는 개념은 아예 사용하지 않더군요.

 

단말노드 즉 leaves를 제외한 모든 노드가 2개의 자식을 가지는 동시에 leaves는 같은 레벨에 위치해 있

 

다. => 즉 트리가 완전히 꽉채워진 구조이죠. 그리고  complete binary tree 를 완전트리라고 칭하여

 

height가 n인경우 n-1까지는 위에말한 full binary tree의 구조를 가지며 n번째에서는 좌측부터 우측순으로

 

채워진 형태, 즉 complete binary tree에 레벨 순으로 번호를 매칭하였을때 그 번호가 끊어지지 않고 연속

 

되는 경우이죠. 그런데 여기서도 또 말이 다른게 어떤데서는 완전트리도 단말노드를 제외한 모든 노드가 2

 

개의 자식을 가져야 된다는 곳도 있고 그렇지 않은 곳도 있네요

 

예를 들어,

 

           1

       ↙  ↘

     2        3   => 이와 같은 형태를 완전트리라고 하는 곳도 있고 3번째 노드가 2개의 자식을 갖지 않고

  ↙↘    ↙         1개의 자식노드를 가지기 때문에 완전 트리가 아니라고 하는 곳도 있네요.

4     5   6            뭐가 맞는 거죠?

 

 

2. 두번째는 perfect binary tree(포화이진트리), full binary tree(전이진트리), complete binary tree(완전

 

이진트리) 라고 사용하는데 여기서 perfect binary tree를 포화이진트리라고 하여 위에서 말한 모든 노드가

 

꽉차있는 상태를 말하고, full binary tree는 전이진트리라하여 단말노드를 제외한 모든 노드가 2개의 자식

 

노드를 가진 트리로 정의하더군요. 즉 모든 노드가 꽉차있을 필요는 없다는 거죠. 예를 들어,

 

           1

       ↙  ↘

     2        3   => 레벨 3의 노드 2자리가 비어있지만 단말노드를 제외한 모든 노드가 2개의 자식노드를

  ↙↘               가지므로 full binary tree(전이진트리)라고 하더군요.

4     5                

 

마지막으로 완전트리는 위 1번에서 말한 것과 똑같이 처리를 하더군요. 하지만 여기서도 위와 같이

          1

       ↙  ↘

     2        3   => 이와 같은 형태를 완전트리라고 하느냐 안하느냐에 대한 것이 궁금합니다.

  ↙↘    ↙        

4     5   6