7. 트리

서브트리: 부모노드를 삭제하면 생기는 트리들

잎 노드: 트리의 맨 바닥에 있으면서 자신의 서브트리,자식을 갖지 않는 노드

 

진입차수: 나한테 들어온 길

루트노드는 진입차수 0

루트를 제외한 모든 노드의 진입차수는 1

진출차수: 나가는 길

잎노드는 진출차수가 0

 

노드의 레벨: 루트로부터 그 노드까지 이어진 경로의 길

루트노드는 레벨0

 

깊이는 레벨+1

깊이: 트리의 레벨에서 가장 큰 값에 1을 더한 것

이진트리 : 

모든 노드의 차수가 2이하인 트리(진출 차수가2 이하)

 

Q.모든노드의 진입차수는 1이다 ?

  => x  루트노드는 0 

 

 

가득찬 이진트리(포화이진트리) : 이진트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리

 

 

완전이진트리 :높이가 k인 이진트리가 0 레벨부터 k-2 까지 다 채우고 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노드들이 차례대로 채워진 이진트리.

 

우측하단 노드가 없어져도 완전이진트리이지만 포화이진트리는 아님

 

 

이진트리의 순회 : 노드를 다 방문하는 순서

전위순회  : 루트-왼쪽자식-오른쪽자식

중위순회 : 왼쪽자식-루트노드-오른쪽자식

후위순회 : 왼쪽자식- 오른쪽자식- 루트노드

 

일반트리를 이진트리로 변환방법

1,일반트리에 대하여 각 노드의 형제들을 연결

2.각 노드에 대하여 가장 왼쪽 링크만 남기고 모두 제거

3. 루트노드는 반드시 왼쪽 자식노드 하나만 갖도록