선형/비선형 자료구조

  • 선형 자료구조
    • 리스트, 스택, 큐와 같이 데이터 집합을 한 줄로 늘어 세운 구조
  • 비선형 자료구조
    • 트리(Tree)는 데이터 집합을 여러 갈래로 나누어 세운 비선형 구조
    • 삽입, 삭제, 검색에 대해서 선형 구조보다 나은 시간적 효율을 보임


트리

  • 일반트리


  • 이진트리
    • 최대 두 개까지의 자식노드를 가질 수 있는 트리


일반트리의 이진트리 변환

  • 일반트리에서는 자식노드의 수가 몇 개가 있는지 예측 불가하여 컴퓨터로 표현하기 어려움
  • 모든 일반 트리는 이진 트리로 바꾸어 표현 가능
  • 왼쪽자식노드-오른쪽형제노드 방법



이진트리의 종류

  • 포화 이진트리
    • 리프노드를 제외한 모든 노드의 자식은 2개
  • 완전 이진트리
    • 모든 노드의 자식은 0개 또는 2개
  • skew 이진트리
    • 한 쪽으로 치우친 트리


이진트리의 저장

  • 배열
    • 완전 이진트리의 경우

    • skewed 이진트리의 경우


    • 배열의 단점
      • 배열의 이용하지 않는 저장 공간이 많다.
      • 트리의 최대 깊이를 대비하여 기억장소를 확보하기 때문에 메모리 사용량이 많고, 확보한 기억장소보다 트리를 확장할 수 없다.
  • 링크드리스트


이진트리의 순회(Traversal)


  • 전위순회(Preoder Traversal)
    • 방문 순서:  G, C, A, E, L
void PreOrder (Nptr T) {
	if (T != NULL) {
		Visit(T->Name);
 		PreOrder(T->LChild);
		PreOrder(T->RChild);
	}
}


  • 중위순회(Inoder Traversal)
    • 방문 순서:  A, C, E, G, L
void InOrder (Nptr T) {
	if (T != NULL) {
		InOrder(T->LChild); 
		Visit(T->Name);
		InOrder(T->RChild); 
	} 
}


  • 후위순회(Postorder Traversal)
    • 방문 순서:  A, E, C, L, G
void PostOrder (Nptr T) {
	if (T != NULL) {
		PostOrder(T->LChild); 
		PostOrder(T->RChild); 
		Visit(T->Name);
	} 
}


Reference


저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바