트리의 저장 방식

1. 부모 표현법 각 노드를 배열로 관리하며, 각 요소는 데이터와 부모의 인덱스를 포함한다.

typedef struct {
    TElemType data;
    int parent;  // 부모 노드의 인덱스
} PTNode;

#define MAX_TREE_SIZE 100
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int root;      // 루트 위치
    int count;     // 총 노드 수
} PTree;

2. 자식 리스트 표현법 각 노드의 자식을 단일 연결 리스트로 저장하고, 모든 노드의 리스트 헤드를 순차 배열로 관리한다.

자식 노드 구조: | child | next |

typedef struct CTNode {
    int child;
    struct CTNode* next;
} *ChildPtr;

typedef struct {
    TElemType data;
    ChildPtr firstchild;  // 첫 번째 자식 포인터
} CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n;   // 노드 수
    int r;   // 루트 위치
} CTree;

3. 자식-형제 표현법 이진 연결 리스트를 활용하여, 각 노드는 두 개의 링크를 가진다: 첫 번째 자식과 다음 형제.

typedef struct CSNode {
    ElemType data;
    struct CSNode* firstchild;   // 첫 번째 자식
    struct CSNode* nextsibling;  // 다음 형제
} CSNode, *CSTree;

트리 ↔ 이진 트리 변환

트리 → 이진 트리

1. 선 추가: 동반자(형제) 간에 선 연결
2. 선 제거: 각 노드에서 왼쪽 자식을 제외한 다른 자식들 간의 관계 제거
3. 회전: 루트를 중심으로 시계 방향으로 45도 회전

이진 트리 → 트리

1. 선 추가: 현재 노드가 부모의 왼쪽 자식이라면, 그 오른쪽 자식과 그 하위 오른쪽 자식들을 모두 부모와 연결
2. 선 제거: 원래 이진 트리에서 부모와 오른쪽 자식 사이의 연결 제거
3. 정렬: 계층적으로 정렬하여 트리 형태로 재구성

임목과 이진 트리의 변환

임목 → 이진 트리

1. 각 트리를 별도로 이진 트리로 변환
2. 각 트리의 루트를 순서대로 연결
3. 첫 번째 트리의 루트를 전체 이진 트리의 루트로 삼고, 회전하여 구성

이진 트리 → 잣

1. 선 제거: 루트와 오른쪽 자식 간의 연결을 제거하고, 오른쪽 분지에 있는 모든 연결을 해제하여 독립된 이진 트리 집합 생성
2. 복원: 각 독립된 이진 트리를 원래의 트리로 복원

트리 및 잣의 순회 방법

트리 순회

• 전순회(루트 우선): 루트 방문 후, 각 서브트리에 대해 전순회 수행
• 후순회(루트 후순): 각 서브트리에 대해 후순회 수행 후 루트 방문
• 레벨 순회: 상위에서 하위로, 좌에서 우로 노드 순차 방문

임목 순회 임목은 세 부분으로 나뉜다:

1. 첫 번째 트리의 루트
2. 첫 번째 트리의 자식 잣
3. 나머지 트리들의 집합

• 전순회:

1. 첫 번째 트리의 루트 방문
2. 첫 번째 트리의 자식 잣에 대해 전순회
3. 나머지 트리들의 잣에 대해 전순회 → 각 트리에 대해 전순회 수행

• 중순회:

1. 첫 번째 트리의 자식 잣에 대해 중순회
2. 첫 번째 트리의 루트 방문
3. 나머지 트리들의 잣에 대해 중순회 → 각 트리에 대해 후순회 수행