트리

트리의 개념

트리의 구성

"모차르트, 바흐, 베토베느 세잔, 피카소, 아인슈타인 뉴턴"

구분을 어떻게 할까? 직업, 나이, 나라 등등

기본적으로 분류를 해서 찾기에 좋다. 

 

트리의 정의

• 검색의 편리함
• 논리적 계층
• 계급적 특성

---

트리의 표현 방법

• 노드 : 트리의 항목/트리에 저장되는 데이터의 묶음
  • 부모노드 - 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드들
  • 상위 계층 - 부모노드, 하위계층 - 자식노드
• 서브트리 : 부모 노드를 삭제하면 생기는 트리들
• 잎 노드 : 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드
• 진입/진출 차수
  • 루트노드 : 진입 차수 = 0
  • 루트를 제외한 모든 노드의 진입 차수 = 1
  • 잎 노드 : 진출 차수= 0
• 내부노드와 형제
  • 내부노드 : 루트도 아니고 잎도 아닌 노드
  • 형제노드 : 같은 부모를 갖는 노드들
• 트리의 레벨
  • 노드의 레벨 : 루트로부터 그 노드까지 이어진 선(경로)의 길이

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

---

추상 자료형

트리 객체의 정의 : 루트 노드를 갖는 유한 리스트

---

이진 트리

• 모든 노드의 차수가 2 이하인 트리
• 모든 노드가 2개 이하의 자식 노드를 가지므로 일반성으로 잃지 않고 '오른쪽, 왼쪽' 이라는 방향 개념을 부여할 수 도 있음.

가득 찬 이진트리 (포화 이진트리)

완전 이진 트리

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

배열을 이용한 이진트리의 구현

트리가 완전 이진트리 또는 가득 찬 이진 트리인 경우 낭비되는 공간이 없이 효율적임

포인터를 이용한 이지 트리의 구현

---

이진 트리의 순회

이진 트리의 전위 순회

루트노드 - 왼쪽 자식노드 - 오른쪽 자식노드 순

이진 트리의 후위 순회

왼쪽 자식노드 - 오른쪽 자식노드 - 루트노드

이진 트리의 중위 순회

왼쪽 자식노드 - 루트 노드 - 오른쪽 자식 노드

---

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

• 일반 트리에 대하여 각 노드의 형제들을 연결
• 각 노드에 대하여 가장 왼쪽 링크만 남기고 나머지는 제거
• 루트 노드는 반드시 왼쪽 자식노드 하나만 갖도록 함

---

스레드 트리

스레드 : 순회 방법에 따른 방문순서를 유지하는 포인터

전위 / 후위 / 중위

스레드 구현

포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가

typedef struct tfNode{
	struct tfnode * left;
    struct tfnode * lthread;
    char data;
    struct tfnode * right;
    struct tfnode * rthread;
 }tfnode;

 

중위 순회

void inorder(tfNode* startNode){
    tfnode * ptr = startNode;
    while(ptr != null){
        printf("%s",ptr->data);
        ptr = ptr -> rthread;
    }
}

빈 포인터의 활용

---

스레드 트리 순회, 삽입, 삭제