[8] 트리 ② 트리의 구현 : ADT

728x90

이진트리 ADT

∙ 이진트리: 각 노드가 최대 두 개의 자식을 가지는 트리이다.

∙ 이진트리의 성질: 노드 수, 외부노드 수, 내부노드 수, 트리의 높이 등의 관계를 정의한다.

중요 메서드

▶ leftChild(v): 노드 v의 왼쪽 자식을 반환합니다.

▶ rightChild(v): 노드 v의 오른쪽 자식을 반환합니다.

▶ sibling(v): 노드 v의 형제를 반환합니다.

이진트리 순회

∙ 선위순회 (Preorder): 노드를 왼쪽 및 오른쪽 자식들보다 먼저 방문한다.

∙ 후위순회 (Postorder): 노드를 왼쪽 및 오른쪽 자식들 다음에 방문한다.

∙ 중위순회 (Inorder): 노드를 왼쪽 자식들 다음에, 오른쪽 자식들보다 앞서 방문한다.

배열에 기초한 이진트리 알고리즘

배열을 이용하여 이진트리를 구현하는 방법은 간단하고 메모리 접근이 빠른 장점이 있다.

배열을 사용하면 각 노드의 부모와 자식 노드의 인덱스를 쉽게 계산할 수 있다. 이 방법은 특히 완전 이진트리에서 효율적이다.

이 방법에서는 각 노드 간의 링크를 저장할 필요가 없으며, 대신 배열의 순위를 사용하여 자식 및 부모 노드의 위치를 결정한다.

배열 기반 이진트리의 구성

1D 배열: 이진트리는 일차원 배열을 이용하여 표현한다.
노드 위치: 각 노드의 위치는 배열 인덱스로 표현한다.

배열 기반 이진트리의 인덱스 계산

왼쪽 자식의 인덱스: 2 * i
오른쪽 자식의 인덱스: 2 * i + 1
부모의 인덱스: ⌊i / 2⌋

여기서 i는 현재 노드의 인덱스이다.

배열의 순위 0 셀은 사용되지 않으며, 트리에서 비어 있는 셀은 특별한 값을 저장하여 빈 공간을 나타다. 예를 들어, 널 마커(‘#’)를 사용하거나 포인터 배열인 경우 널 포인터를 사용할 수 있다.

이 방법을 사용하면 이진트리를 단순한 배열로 표현할 수 있으며, 노드 간의 관계를 명확하게 유지하면서도 추가적인 링크 저장 공간을 절약할 수 있다.

코드 구현 : 배열

이진 트리를 배열로 구현할 때의 장점은 다음과 같다.

첫째, 배열을 사용하면 인덱스를 통해 노드에 직접 접근할 수 있어 효율적이다.

둘째, 메모리 연속성으로 인해 캐시 적중률이 높아져 성능이 향상된다.

셋째, 구조가 간단하고 포인터를 사용하지 않아 포인터 연산과 관련된 오류가 발생하지 않는다.

단점으로는, 배열의 크기를 고정해야 하므로 트리의 크기가 예측하기 어렵거나 동적으로 변할 경우 비효율적이다. 또한, 트리가 불균형할 경우 많은 빈 공간이 생길 수 있어 공간 낭비가 발생한다. 삽입 및 삭제 시 배열의 재구성이 필요할 수 있어 비효율적이며, 배열의 크기를 변경하는 것이 쉽지 않아 동적 크기 조정이 어렵다.

헤더 및 구조체 선언

#include <stdio.h>
#include <stdlib.h>

// typedef char element;
#define MAX_SIZE 100 // 배열의 최대 크기 정의

// 이진 트리 구조체 정의
typedef struct {
    int size; // 현재 트리의 크기
    int elements[MAX_SIZE]; // 트리를 저장하는 배열
} BinaryTree;

구조체 BinaryTree는 이진트리를 저장하기 위한 데이터 구조를 정의한다.

int size는 현재 트리의 크기를 저장하며, int elements [MAX_SIZE]는 트리를 저장하는 배열이다.

이 배열은 크기가 MAX_SIZE로 설정되어 있으며, 각 요소는 트리의 노드를 나타낸다.

initTree 함수 : 이진트리를 초기화

// 이진 트리 초기화 함수
void initTree(BinaryTree *tree) {
    tree->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        tree->elements[i] = -1; // -1을 사용하여 빈 노드를 표시
    }
}

1. 트리의 크기(size)를 0으로 설정한다.

2. 모든 배열 요소를 -1로 초기화하여 빈 노드를 표시한다.

makeNode 함수 : 루트 노드를 추가

// 루트 노드 추가 함수
void makeNode(BinaryTree *tree, int value) {
    if (tree->size == 0) {
        tree->elements[1] = value;
        tree->size++;
    } else {
        printf("트리가 이미 초기화되었습니다.\n");
    }
}

• 트리의 크기가 0인 경우, 루트 위치(인덱스 1)에 값을 설정하고, 트리의 크기를 1 증가시킨다.

• 그렇지 않으면 "트리가 이미 초기화되었습니다."를 출력한다.

addLeftChild 함수 : 왼쪽 자식 노드를 추가

// 왼쪽 자식 노드 추가 함수
void addLeftChild(BinaryTree *tree, int parentIndex, int value) {
    int leftChildIndex = 2 * parentIndex;
    if (leftChildIndex < MAX_SIZE && tree->elements[parentIndex] != -1) {
        tree->elements[leftChildIndex] = value;
        tree->size++;
    } else {
        printf("왼쪽 자식 노드를 추가할 수 없습니다.\n");
    }
}

1. 부모 노드의 왼쪽 자식 인덱스를 계산한다.(2 * 부모 인덱스)

2. 왼쪽 자식 인덱스가 배열 크기 내에 있고 부모 노드가 존재하면, 해당 인덱스에 값을 설정하고 트리의 크기를 1 증가한다.

3. 그렇지 않으면 "왼쪽 자식 노드를 추가할 수 없습니다."를 출력한다.

addRightChild 함수 : 오른쪽 자식 노드를 추가

// 오른쪽 자식 노드 추가 함수
void addRightChild(BinaryTree *tree, int parentIndex, int value) {
    int rightChildIndex = 2 * parentIndex + 1;
    if (rightChildIndex < MAX_SIZE && tree->elements[parentIndex] != -1) {
        tree->elements[rightChildIndex] = value;
        tree->size++;
    } else {
        printf("오른쪽 자식 노드를 추가할 수 없습니다.\n");
    }
}

1. 부모 노드의 오른쪽 자식 인덱스를 계산합니다(2 * 부모 인덱스 + 1)

2. 오른쪽 자식 인덱스가 배열 크기 내에 있고 부모 노드가 존재하면 해당 인덱스에 값을 설정하고 트리의 크기를 1 증가시킨다.

3. 그렇지 않으면 "오른쪽 자식 노드를 추가할 수 없습니다."를 출력한다.

visit 함수 : 노드 방문

• 노드 값이 -1이 아니면 값을 출력한다.

// 노드 방문 함수
void visit(int value) {
    if (value != -1) {
        printf("%d ", value);
    }
}

preOrder 함수 : 전위 순회를 수행

// 전위 순회 함수
void preOrder(BinaryTree *tree, int index) {
    if (index < MAX_SIZE && tree->elements[index] != -1) {
        visit(tree->elements[index]);
        preOrder(tree, 2 * index);
        preOrder(tree, 2 * index + 1);
    }
}

인덱스가 배열 크기 내에 있고 노드가 존재하면:

1. 노드를 방문한다.

2. 왼쪽 자식을 재귀적으로 순회한다.

3. 오른쪽 자식을 재귀적으로 순회한다.

inOrder 함수 : 중위 순회를 수행

// 중위 순회 함수
void inOrder(BinaryTree *tree, int index) {
    if (index < MAX_SIZE && tree->elements[index] != -1) {
        inOrder(tree, 2 * index);
        visit(tree->elements[index]);
        inOrder(tree, 2 * index + 1);
    }
}

인덱스가 배열 크기 내에 있고 노드가 존재하면:

1. 왼쪽 자식을 재귀적으로 순회한다.

2. 노드를 방문한다.

3. 오른쪽 자식을 재귀적으로 순회한다.

postOrder : 후위 순회를 수행

// 후위 순회 함수
void postOrder(BinaryTree *tree, int index) {
    if (index < MAX_SIZE && tree->elements[index] != -1) {
        postOrder(tree, 2 * index);
        postOrder(tree, 2 * index + 1);
        visit(tree->elements[index]);
    }
}

인덱스가 배열 크기 내에 있고 노드가 존재하면:

1. 왼쪽 자식을 재귀적으로 순회한다.

2. 오른쪽 자식을 재귀적으로 순회한다.

3. 노드를 방문한다.

element / root / isRoot

// 노드의 요소를 반환합니다.
int element(BinaryTree *tree, int v) {return tree->elements[v];}

// 루트 노드를 반환합니다.
int root(BinaryTree *tree) {return 1;}

// 노드 v가 루트인지 확인합니다.
int isRoot(int v) {return v == 1;}

• 설명: 주어진 인덱스의 배열 요소를 반환한다.

• 설명: 루트 노드의 인덱스 1을 반환한다.

• 설명: 주어진 인덱스가 1인지 확인하여 노드가 루트인지 확인한다.

parent 함수 : 노드의 부모를 반환

// 노드 v의 부모를 반환합니다.
int parent(int v) {
    if (v == 1) return -1; // 루트 노드는 부모가 없음
    return v / 2;
}

1. 주어진 인덱스가 1이면:부모가 없음을 의미하는 -1을 반환한다.

2. 그렇지 않으면: 부모 노드의 인덱스를 반환한다.(인덱스 / 2).

leftChild / rightChild

// 노드 v의 왼쪽 자식을 반환합니다.
int leftChild(int v) {return 2 * v;}

// 노드 v의 오른쪽 자식을 반환합니다.
int rightChild(int v) {return 2 * v + 1;}

•설명: 노드의 왼쪽 자식의 인덱스를 반환한다.(2 * 인덱스).

•설명: 노드의 오른쪽 자식의 인덱스를 반환한다.(2 * 인덱스 + 1).

sibling 함수 : 노드의 형제를 반환

// 노드 v의 형제를 반환합니다.
int sibling(int v) {
    if (v == 1) return -1; // 루트 노드는 형제가 없음
    if (v % 2 == 0) return v + 1; // 왼쪽 자식인 경우
    return v - 1; // 오른쪽 자식인 경우
}

1. 주어진 인덱스가 1이면: 형제가 없음을 의미하는 -1을 반환한다.

2. 주어진 인덱스가 짝수이면: 오른쪽 자식의 인덱스를 반환한다.(인덱스 + 1).

3. 그렇지 않으면: 왼쪽 자식의 인덱스를 반환한다.(인덱스 - 1).

isInternal / isExternal / setElement

// 노드 v가 내부노드인지 확인합니다.
int isInternal(BinaryTree *tree, int v) {return tree->elements[v] != -1 && (tree->elements[2 * v] != -1 || tree->elements[2 * v + 1] != -1);}

// 노드 v가 외부노드인지 확인합니다.
int isExternal(BinaryTree *tree, int v) {return tree->elements[v] != -1 && tree->elements[2 * v] == -1 && tree->elements[2 * v + 1] == -1;}

// 노드 v의 요소를 e로 설정합니다.
void setElement(BinaryTree *tree, int v, int e) {
    tree->elements[v] = e;
}

•설명: 노드가 내부 노드인지 확인한다. 노드가 존재하고 왼쪽 또는 오른쪽 자식이 존재하면 내부 노드이다

•설명: 노드가 외부 노드인지 확인한다. 노드가 존재하고 왼쪽과 오른쪽 자식이 모두 존재하지 않으면 외부 노드이다.

•설명: 노드의 요소를 주어진 인덱스의 배열 요소를 주어진 값으로 설정한다.

swapElements 함수 : 두 노드의 요소를 교환

// 노드 v와 w의 요소를 교환합니다.
void swapElements(BinaryTree *tree, int v, int w) {
    int temp = tree->elements[v];
    tree->elements[v] = tree->elements[w];
    tree->elements[w] = temp;
}

전체 코드

아래 [더 보기] 란의 접은 글의 코드 블록을 확인한다.

#include <stdio.h>
#include <stdlib.h>

// typedef char element;
#define MAX_SIZE 100 // 배열의 최대 크기 정의

// 이진 트리 구조체 정의
typedef struct {
    int size; // 현재 트리의 크기
    int elements[MAX_SIZE]; // 트리를 저장하는 배열
} BinaryTree;

// 이진 트리 초기화 함수
void initTree(BinaryTree *tree) {
    tree->size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        tree->elements[i] = -1; // -1을 사용하여 빈 노드를 표시
    }
}

// 루트 노드 추가 함수
void makeNode(BinaryTree *tree, int value) {
    if (tree->size == 0) {
        tree->elements[1] = value;
        tree->size++;
    } else {
        printf("트리가 이미 초기화되었습니다.\n");
    }
}

// 왼쪽 자식 노드 추가 함수
void addLeftChild(BinaryTree *tree, int parentIndex, int value) {
    int leftChildIndex = 2 * parentIndex;
    if (leftChildIndex < MAX_SIZE && tree->elements[parentIndex] != -1) {
        tree->elements[leftChildIndex] = value;
        tree->size++;
    } else {
        printf("왼쪽 자식 노드를 추가할 수 없습니다.\n");
    }
}

// 오른쪽 자식 노드 추가 함수
void addRightChild(BinaryTree *tree, int parentIndex, int value) {
    int rightChildIndex = 2 * parentIndex + 1;
    if (rightChildIndex < MAX_SIZE && tree->elements[parentIndex] != -1) {
        tree->elements[rightChildIndex] = value;
        tree->size++;
    } else {
        printf("오른쪽 자식 노드를 추가할 수 없습니다.\n");
    }
}

// 노드 방문 함수
void visit(int value) {
    if (value != -1) {
        printf("%d ", value);
    }
}

// 전위 순회 함수
void preOrder(BinaryTree *tree, int index) {
    if (index < MAX_SIZE && tree->elements[index] != -1) {
        visit(tree->elements[index]);
        preOrder(tree, 2 * index);
        preOrder(tree, 2 * index + 1);
    }
}

// 중위 순회 함수
void inOrder(BinaryTree *tree, int index) {
    if (index < MAX_SIZE && tree->elements[index] != -1) {
        inOrder(tree, 2 * index);
        visit(tree->elements[index]);
        inOrder(tree, 2 * index + 1);
    }
}

// 후위 순회 함수
void postOrder(BinaryTree *tree, int index) {
    if (index < MAX_SIZE && tree->elements[index] != -1) {
        postOrder(tree, 2 * index);
        postOrder(tree, 2 * index + 1);
        visit(tree->elements[index]);
    }
}

// 노드의 요소를 반환합니다.
int element(BinaryTree *tree, int v) {return tree->elements[v];}

// 루트 노드를 반환합니다.
int root(BinaryTree *tree) {return 1;}

// 노드 v가 루트인지 확인합니다.
int isRoot(int v) {return v == 1;}

// 노드 v의 부모를 반환합니다.
int parent(int v) {
    if (v == 1) return -1; // 루트 노드는 부모가 없음
    return v / 2;
}

// 노드 v의 왼쪽 자식을 반환합니다.
int leftChild(int v) {return 2 * v;}

// 노드 v의 오른쪽 자식을 반환합니다.
int rightChild(int v) {return 2 * v + 1;}

// 노드 v의 형제를 반환합니다.
int sibling(int v) {
    if (v == 1) return -1; // 루트 노드는 형제가 없음
    if (v % 2 == 0) return v + 1; // 왼쪽 자식인 경우
    return v - 1; // 오른쪽 자식인 경우
}

// 노드 v가 내부노드인지 확인합니다.
int isInternal(BinaryTree *tree, int v) {return tree->elements[v] != -1 && (tree->elements[2 * v] != -1 || tree->elements[2 * v + 1] != -1);}

// 노드 v가 외부노드인지 확인합니다.
int isExternal(BinaryTree *tree, int v) {return tree->elements[v] != -1 && tree->elements[2 * v] == -1 && tree->elements[2 * v + 1] == -1;}

// 노드 v의 요소를 e로 설정합니다.
void setElement(BinaryTree *tree, int v, int e) {
    tree->elements[v] = e;
}

// 노드 v와 w의 요소를 교환합니다.
void swapElements(BinaryTree *tree, int v, int w) {
    int temp = tree->elements[v];
    tree->elements[v] = tree->elements[w];
    tree->elements[w] = temp;
}

int main() {
    BinaryTree tree;
    initTree(&tree);

    makeNode(&tree, 1); // 루트 노드 추가
    addLeftChild(&tree, 1, 2); // 루트의 왼쪽 자식 추가
    addRightChild(&tree, 1, 3); // 루트의 오른쪽 자식 추가
    addLeftChild(&tree, 2, 4); // 2의 왼쪽 자식 추가
    addRightChild(&tree, 2, 5); // 2의 오른쪽 자식 추가
    addLeftChild(&tree, 3, 6); // 3의 왼쪽 자식 추가
    addRightChild(&tree, 3, 7); // 3의 오른쪽 자식 추가

    printf("Preorder Traversal: ");
    preOrder(&tree, 1);
    printf("\n");

    printf("Inorder Traversal: ");
    inOrder(&tree, 1);
    printf("\n");

    printf("Postorder Traversal: ");
    postOrder(&tree, 1);
    printf("\n");

    // 테스트 코드
    printf("Element at 1: %d\n", element(&tree, 1));
    printf("Root: %d\n", root(&tree));
    printf("Is 1 root? %d\n", isRoot(1));
    printf("Parent of 2: %d\n", parent(2));
    printf("Left child of 2: %d\n", leftChild(2));
    printf("Right child of 2: %d\n", rightChild(2));
    printf("Sibling of 2: %d\n", sibling(2));
    printf("Is 1 internal? %d\n", isInternal(&tree, 1));
    printf("Is 4 external? %d\n", isExternal(&tree, 4));
    setElement(&tree, 1, 10);
    printf("New element at 1: %d\n", element(&tree, 1));
    swapElements(&tree, 1, 2);
    printf("After swap, element at 1: %d, element at 2: %d\n", element(&tree, 1), element(&tree, 2));

    return 0;
}

코드 구현 : 연결리스트

이진 트리를 연결 리스트로 구현할 때의 장점은 다음과 같다. 트리의 크기가 동적으로 변할 수 있어 메모리를 효율적으로 사용할 수 있다. 삽입 및 삭제 연산이 배열보다 간단하며, 노드 간의 재구성이 필요하지 않다. 트리가 불균형해도 공간 낭비가 발생하지 않는다. 각 노드가 개별적으로 존재하므로, 특정 노드에 직접 접근할 수 있다.

단점으로는, 각 노드가 부모, 왼쪽 자식, 오른쪽 자식을 가리키는 포인터를 가지고 있어 메모리 사용량이 증가한다. 포인터 연산과 관련된 오류가 발생할 가능성이 있다. 인덱스를 통한 직접 접근이 불가능해, 특정 노드를 찾기 위해 트리를 순회해야 하므로 시간 복잡도가 증가할 수 있다. 메모리 할당과 해제를 반복하면서 성능이 저하될 수 있다.

TreeNode 구조체 정의

#include <stdio.h>
#include <stdlib.h>

typedef char element;

// 노드 구조체 정의
typedef struct TreeNode {
    element key;               // 노드의 데이터
    struct TreeNode* parent;   // 부모 노드를 가리키는 포인터
    struct TreeNode* left;     // 왼쪽 자식 노드를 가리키는 포인터
    struct TreeNode* right;    // 오른쪽 자식 노드를 가리키는 포인터
} TreeNode;

이 구조체는 이진트리의 노드를 표현한다. 각 노드는 다음의 네 가지 요소를 가진다:

key: 노드가 저장하는 데이터.
parent: 부모 노드를 가리키는 포인터.
left: 왼쪽 자식 노드를 가리키는 포인터.
right: 오른쪽 자식 노드를 가리키는 포인터.

makeNode 함수

이 함수는 새로운 트리 노드를 생성하고 초기화한다.

// 노드 생성 함수
TreeNode* makeNode(element key, TreeNode *parent, TreeNode *left, TreeNode *right) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        fprintf(stderr, "메모리 할당 실패\n");
        exit(1);
    }
    node->key = key;
    node->parent = parent;
    node->left = left;
    node->right = right;

    return node;
}

인자 설명

∙ element key: 노드가 저장할 데이터 값.

∙ TreeNode *parent: 부모 노드를 가리키는 포인터.

∙ TreeNode *left: 왼쪽 자식 노드를 가리키는 포인터.

∙ TreeNode *right: 오른쪽 자식 노드를 가리키는 포인터.

메모리 할당

- malloc 함수를 사용하여 TreeNode 구조체 크기만큼 메모리를 동적으로 할당한다.

- 새로운 TreeNode를 생성하기 위해 필요한 메모리 공간을 요청한다.

- 할당된 메모리의 시작 주소가 node 포인터에 저장된다.

메모리 할당 실패 확인:

- 할당된 메모리의 주소가 NULL인지 확인한다.

- 동적 할당이 실패하면 NULL 포인터를 반환한다. 이를 통해 메모리 할당 실패 여부를 확인한다.

노드 초기화: 할당된 노드의 key 필드를 전달된 key 값으로 초기화한다.

부모 노드 포인터 설정: 할당된 노드의 parent 필드를 전달된 parent 값으로 초기화한다.

왼쪽 자식 노드 포인터 설정: 할당된 노드의 left 필드를 전달된 left 값으로 초기화한다.

오른쪽 자식 노드 포인터 설정: 할당된 노드의 right 필드를 전달된 right 값으로 초기화한다.

노드 반환

- 초기화된 노드의 포인터를 반환한다.

- 이 포인터는 새로운 노드를 가리키며, 호출자가 이 노드를 사용할 수 있게 된다.

preOrder 함수

// 전위 순회 함수
//노드를 자손들보다 먼저 방문하는 순회 방법
void preOrder(TreeNode* node) {
    if (node != NULL) {
        printf("%c ", node->key); // 현재 노드 방문 
        preOrder(node->left); // 왼쪽 서브트리 방문
        preOrder(node->right); // 오른쪽 서브트리 방문
    }
}

이 함수는 전위 순회 방식으로 트리를 탐색합니다. 알고리즘은 다음과 같다:

현재 노드가 NULL이 아닌 경우에만 수행한다.
현재 노드의 데이터를 출력한다.
왼쪽 자식 노드를 대상으로 재귀적으로 preOrder를 호출한다.
오른쪽 자식 노드를 대상으로 재귀적으로 preOrder를 호출한다.

inOrder 함수

// 중위 순회 함수
//노드를 왼쪽 자식들 다음에, 오른쪽 자식들보다 앞서 방문
void inOrder(TreeNode* node) {
    if (node != NULL) {
        inOrder(node->left); // 왼쪽 서브트리 방문
        printf("%c ", node->key); // 현재 노드 방문
        inOrder(node->right); // 오른쪽 서브트리 방문
    }
}

이 함수는 중위 순회 방식으로 트리를 탐색합니다. 알고리즘은 다음과 같다:

현재 노드가 NULL이 아닌 경우에만 수행한다.
왼쪽 자식 노드를 대상으로 재귀적으로 inOrder를 호출한다.
현재 노드의 데이터를 출력한다.
오른쪽 자식 노드를 대상으로 재귀적으로 inOrder를 호출한다.

postOrder 함수

// 후위 순회 함수
void postOrder(TreeNode* node) {
    if (node != NULL) {
        postOrder(node->left); // 왼쪽 서브트리 방문
        postOrder(node->right); // 오른쪽 서브트리 방문
        printf("%c ", node->key); // 현재 노드 방문
    }
}

이 함수는 후위 순회 방식으로 트리를 탐색합니다. 알고리즘은 다음과 같다:

현재 노드가 NULL이 아닌 경우에만 수행한다.
왼쪽 자식 노드를 대상으로 재귀적으로 postOrder를 호출한다.
오른쪽 자식 노드를 대상으로 재귀적으로 postOrder를 호출한다.
현재 노드의 데이터를 출력한다.

메서드 추가

▶ element(v): 노드 v의 요소를 반환합니다.
▶ root(): 루트 노드를 반환합니다.
▶ isRoot(v): 노드 v가 루트인지 확인합니다.
▶ parent(v): 노드 v의 부모를 반환합니다.
▶ leftChild(v): 노드 v의 왼쪽 자식을 반환합니다.
▶ rightChild(v): 노드 v의 오른쪽 자식을 반환합니다.
▶ sibling(v): 노드 v의 형제를 반환합니다.
▶ isInternal(v): 노드 v가 내부노드인지 확인합니다.
▶ isExternal(v): 노드 v가 외부노드인지 확인합니다.
▶ setElement(v, e): 노드 v의 요소를 e로 설정합니다.
▶ swapElements(v, w): 노드 v와 w의 요소를 교환합니다.

element(v) 함수 : 노드 v의 요소(데이터)를 반환

// 노드의 요소를 반환
element elementNode(TreeNode* v) {return v->key;}

설명: 노드 v의 요소(데이터)를 반환한다.
알고리즘: v가 가리키는 노드의 key 값을 반환한다.

root() 함수 : 루트 노드를 반환

// 루트 노드를 반환
TreeNode* root(TreeNode* node) {
    while (node->parent != NULL) {
        node = node->parent;
    }
    return node;
}

설명: 루트 노드를 반환한다.
알고리즘: 현재 노드가 루트 노드가 될 때까지 부모 노드로 이동한다. 부모가 없는 노드가 루트 노드이다.

isRoot(v) 함수 :

// 노드 v가 루트인지 확인
int isRoot(TreeNode* v) {return v->parent == NULL;}

설명: 노드 v가 루트인지 확인한다.
알고리즘: 노드 v의 부모가 NULL인지 확인한다. 부모가 NULL이면 v는 루트 노드이다.

parent(v) 함수 : v의 부모 노드를 반환

// 노드 v의 부모를 반환
TreeNode* parent(TreeNode* v) {return v->parent;}

설명: 노드 v의 부모 노드를 반환한다.
알고리즘: 노드 v의 parent 포인터를 반환한다.

leftChild(v) 함수 : v의 왼쪽 자식 노드를 반환

// 노드 v의 왼쪽 자식을 반환
TreeNode* leftChild(TreeNode* v) {return v->left;}

설명: 노드 v의 왼쪽 자식 노드를 반환한다.
알고리즘: 노드 v의 left 포인터를 반환한다.

rightChild(v) 함수 : v의 오른쪽 자식 노드를 반환

// 노드 v의 오른쪽 자식을 반환
TreeNode* rightChild(TreeNode* v) {return v->right;}

설명: 노드 v의 오른쪽 자식 노드를 반환한다.
알고리즘: 노드 v의 right 포인터를 반환한다.

sibling(v) 함수 : v의 형제 노드를 반환

// 노드 v의 형제를 반환
TreeNode* sibling(TreeNode* v) {
    if (v->parent == NULL) return NULL;
    if (v->parent->left == v) return v->parent->right;
    else return v->parent->left;
}

설명: 노드 v의 형제 노드를 반환한다.
알고리즘:
1. 노드 v의 부모가 NULL이면 NULL을 반환한다.
2. 노드 v가 부모의 왼쪽 자식이면, 부모의 오른쪽 자식을 반환한다.
3. 노드 v가 부모의 오른쪽 자식이면, 부모의 왼쪽 자식을 반환한다.

isInternal(v) 함수 : v가 내부 노드인지 확인

// 노드 v가 내부노드인지 확인
int isInternal(TreeNode* v) {return v->left != NULL || v->right != NULL;

설명: 노드 v가 내부 노드인지 확인한다.
알고리즘: 노드 v가 왼쪽 자식이나 오른쪽 자식을 가지고 있으면 내부 노드이다.

isExternal(v) 함수 : v가 외부 노드인지 확인

// 노드 v가 외부노드인지 확인
int isExternal(TreeNode* v) {return v->left == NULL && v->right == NULL;

설명: 노드 v가 외부 노드인지 확인한다.
알고리즘: 노드 v가 왼쪽 자식과 오른쪽 자식이 모두 없으면 외부 노드이다.

setElement(v, e) 함수 : v의 요소를 e로 설정

// 노드 v의 요소를 e로 설정
void setElement(TreeNode* v, element e) {v->key = e;}

설명: 노드 v의 요소를 e로 설정한다.
알고리즘: 노드 v의 key 값을 e로 설정한다.

swapElements(v, w) 함수 : 노드 v와 노드 w의 요소를 교환

// 노드 v와 w의 요소를 교환
void swapElements(TreeNode* v, TreeNode* w) {
    element temp = v->key;
    v->key = w->key;
    w->key = temp;
}

설명: 노드 v와 노드 w의 요소를 교환한다.
알고리즘:
1. 노드 v의 key 값을 임시 변수에 저장한다.
2. 노드 v의 key 값을 노드 w의 key 값으로 설정한다.
3. 노드 w의 key 값을 임시 변수에 저장된 값으로 설정한다.

전체 코드

#include <stdio.h>
#include <stdlib.h>

typedef char element;

// 노드 구조체 정의
typedef struct TreeNode {
    element key;               // 노드의 데이터
    struct TreeNode* parent;   // 부모 노드를 가리키는 포인터
    struct TreeNode* left;     // 왼쪽 자식 노드를 가리키는 포인터
    struct TreeNode* right;    // 오른쪽 자식 노드를 가리키는 포인터
} TreeNode;

// 노드 생성 함수
TreeNode* makeNode(element key, TreeNode *parent, TreeNode *left, TreeNode *right) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node == NULL) {
        fprintf(stderr, "메모리 할당 실패\n");
        exit(1);
    }
    node->key = key;
    node->parent = parent;
    node->left = left;
    node->right = right;

    return node;
}

// 전위 순회 함수
void preOrder(TreeNode* node) {
    if (node != NULL) {
        printf("%c ", node->key); // 현재 노드 방문 
        preOrder(node->left); // 왼쪽 서브트리 방문
        preOrder(node->right); // 오른쪽 서브트리 방문
    }
}

// 중위 순회 함수
void inOrder(TreeNode* node) {
    if (node != NULL) {
        inOrder(node->left); // 왼쪽 서브트리 방문
        printf("%c ", node->key); // 현재 노드 방문
        inOrder(node->right); // 오른쪽 서브트리 방문
    }
}

// 후위 순회 함수
void postOrder(TreeNode* node) {
    if (node != NULL) {
        postOrder(node->left); // 왼쪽 서브트리 방문
        postOrder(node->right); // 오른쪽 서브트리 방문
        printf("%c ", node->key); // 현재 노드 방문
    }
}

// 노드의 요소를 반환
element elementNode(TreeNode* v) {return v->key;}

// 루트 노드를 반환
TreeNode* root(TreeNode* node) {
    while (node->parent != NULL) {
        node = node->parent;
    }
    return node;
}

// 노드 v가 루트인지 확인
int isRoot(TreeNode* v) {return v->parent == NULL;}

// 노드 v의 부모를 반환
TreeNode* parent(TreeNode* v) {return v->parent;}

// 노드 v의 왼쪽 자식을 반환
TreeNode* leftChild(TreeNode* v) {return v->left;}

// 노드 v의 오른쪽 자식을 반환
TreeNode* rightChild(TreeNode* v) {return v->right;}

// 노드 v의 형제를 반환
TreeNode* sibling(TreeNode* v) {
    if (v->parent == NULL) return NULL;
    if (v->parent->left == v) return v->parent->right;
    else return v->parent->left;
}

// 노드 v가 내부노드인지 확인
int isInternal(TreeNode* v) {return v->left != NULL || v->right != NULL;}

// 노드 v가 외부노드인지 확인
int isExternal(TreeNode* v) {return v->left == NULL && v->right == NULL;}

// 노드 v의 요소를 e로 설정
void setElement(TreeNode* v, element e) {v->key = e;}

// 노드 v와 w의 요소를 교환
void swapElements(TreeNode* v, TreeNode* w) {
    element temp = v->key;
    v->key = w->key;
    w->key = temp;
}

int main(){
    TreeNode *n11 = makeNode('I',NULL,NULL,NULL);
    TreeNode *n10 = makeNode('H',NULL,NULL,NULL);
    TreeNode *n7 = makeNode('G',NULL,NULL,NULL);
    TreeNode *n6 = makeNode('F',NULL,NULL,NULL);
    TreeNode *n5 = makeNode('E',NULL,n10,n11);
    TreeNode *n4 = makeNode('D',NULL,NULL,NULL);
    TreeNode *n3 = makeNode('C',NULL,n6,n7);
    TreeNode *n2 = makeNode('B',NULL,n4,n5);
    TreeNode *n1 = makeNode('A',NULL,n2,n3);

    n10->parent = n11->parent = n5;
    n6->parent = n7->parent = n3;
    n4->parent = n5->parent = n2;    
    n2->parent = n3->parent = n1;

    printf("Pre : "); preOrder(n1);printf("\n");
    printf("In : "); inOrder(n1);printf("\n");
    printf("Post : "); postOrder(n1);printf("\n");

    // 메서드 테스트
    printf("Element of n1: %c\n", elementNode(n1));
    printf("Root of n1: %c\n", elementNode(root(n1)));
    printf("n1 is root: %d\n", isRoot(n1));
    printf("Parent of n3: %c\n", elementNode(parent(n3)));
    printf("Left child of n2: %c\n", elementNode(leftChild(n2)));
    printf("Right child of n2: %c\n", elementNode(rightChild(n2)));
    printf("Sibling of n2: %c\n", elementNode(sibling(n2)));
    printf("n1 is internal: %d\n", isInternal(n1));
    printf("n11 is external: %d\n", isExternal(n11));
    setElement(n1, 'Z');
    printf("New element of n1: %c\n", elementNode(n1));
    swapElements(n1, n2);
    printf("After swap, element of n1: %c, element of n2: %c\n", elementNode(n1), elementNode(n2));

    return 0;
}

728x90

저작자표시

'Datastructure > [8] 트리' 카테고리의 다른 글

[8] 트리 ⑥ 응용 (1) : 연결리스트를 이용한 트리 구현 (1)	2024.06.05
[8] 트리 ⑤ 스택을 이용한 이진 트리 (1)	2024.06.04
[8] 트리 ④ 레벨 순회 : 원형 큐 이용 (0)	2024.06.03
[8] 트리 ③ 원형 큐 (0)	2024.06.03
[8] 트리 ① 트리의 정의 (1)	2024.05.29

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

[8] 트리 ② 트리의 구현 : ADT

이진트리 ADT

중요 메서드

이진트리 순회

배열에 기초한 이진트리 알고리즘

배열 기반 이진트리의 구성

배열 기반 이진트리의 인덱스 계산

코드 구현 : 배열

헤더 및 구조체 선언

initTree 함수 : 이진트리를 초기화

makeNode 함수 : 루트 노드를 추가

addLeftChild 함수 : 왼쪽 자식 노드를 추가

addRightChild 함수 : 오른쪽 자식 노드를 추가

visit 함수 : 노드 방문

preOrder 함수 : 전위 순회를 수행

inOrder 함수 : 중위 순회를 수행

postOrder : 후위 순회를 수행

element / root / isRoot

parent 함수 : 노드의 부모를 반환

leftChild / rightChild

sibling 함수 : 노드의 형제를 반환

isInternal / isExternal / setElement

swapElements 함수 : 두 노드의 요소를 교환

전체 코드

코드 구현 : 연결리스트

TreeNode 구조체 정의

makeNode 함수

preOrder 함수

inOrder 함수

postOrder 함수

메서드 추가

element(v) 함수 : 노드 v의 요소(데이터)를 반환

root() 함수 : 루트 노드를 반환

isRoot(v) 함수 :

parent(v) 함수 : v의 부모 노드를 반환

leftChild(v) 함수 : v의 왼쪽 자식 노드를 반환

rightChild(v) 함수 : v의 오른쪽 자식 노드를 반환

sibling(v) 함수 : v의 형제 노드를 반환

isInternal(v) 함수 : v가 내부 노드인지 확인

isExternal(v) 함수 : v가 외부 노드인지 확인

setElement(v, e) 함수 : v의 요소를 e로 설정

swapElements(v, w) 함수 : 노드 v와 노드 w의 요소를 교환

전체 코드

'Datastructure > [8] 트리' 카테고리의 다른 글

'Datastructure/[8] 트리' 관련글

티스토리툴바

makeNode 함수 : 루트 노드를 추가