9. 트리

트리

안녕하세요. 오랜만입니다 이번에는 트리에 대해서 알아보도록 합시다

 

트리 ADT란? 

위의 그림처럼 각 트리 원소는 부모원소와 0개 이상의 자식을 가지고 이러한 것을 트리라고 부릅니다. 

 

이러한 트리 ADT에는 다양한 용어가 있습니다

• 루트 : 부모가 없는 노드 
• 내부노드 : 적어도 한 개의 자식을 가진 노드 
• 외부노드('리프'라고도 부름) : 자식이 없는 노드 
• 형제 : 같은 부모를 가진 노드들 
• 노드의 조상
• 노드의 자손 
• 부트리 : 노드와 그 노드의 자손들로 구성된 트리 
• 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스 
• 경로길이 : 경로내 간선의 수 
• 노드의 깊이 : 루트로부터 노드에 이르는 유일한 경로의 길이 
• 노드의 높이 : 노드로부터 외부노드에 이르는 가장 긴 경로의 길이 
• 트리의 높이 : 루트의 높이 

 

이러한 트리 ADT를 응용한다면? 

• 직접 응용 
  • 조직구성도
  • 파일시스템
  • 프로그래밍 환경 
• 간접 응용 
  • 보조 데이터구조

 

트리 ADT는 여기까지 살펴보고 이진트리에 대해서 좀 더 알아보는 것이 좋을 것 같습니다. 

이진트리 ADT 

적정이진트리로 구현하는데 이는 트리의 각 내부노드가 두 개의 자식을 가집니다. 그러나 좌우 자식노드 중에 하나가 비어 있더라도 적정이진트리로 볼 수 있습니다. 

이진트리의 성질

• n 노드 수
• e 외부노드 수
• i 내부노드 수
• h 트리의 높이
• e = i + 1
• n = i + e
• h ≤ i
• h ≤ (n - 1)/2

이진트리 ADT 함수

• 깊이
• 높이
• 선위순회
• 후위순회
  • 수식 평가
• 중위순회 - O(n)
  • 이진트리 그리기
  • 수식 인쇄
• 오일러 투어 순회
  • 이진트리에 대한 일반순회
  • 각 노드 세 번 방문
  • 선위, 중위, 후위 모두 포함
  • 이진트리내 각 부트리의 노드 수 계산

배열에 기초한 이진트리

• 1D 배열
• 랭크i에 대해
  • 왼쪽 자식 2i
  • 오른쪽 자식 2i + 1
  • 부모 [i/2]
• 링크 저장 불필요
• 순위 0은 미사용
• 비어 있는 셀은 특별값 저장 - # or 널포인터
• 최선의 경우 N = n | 완전이진트리
• 최악의 경우 N = 2^n - 1 | 부적정이진트리

연결리스트에 기초한 이진트리

• 노드 저장내용
  • 원소
  • 부모노드 (필요 시)
  • 왼쪽 자식노드
  • 오른쪽 자식노드