Data Structure - 3

트리 (Tree)

트리란? 노드들이 나무 가지처럼 연결된 형태이다.

높이는 어떤 관점에서 보냐에 따라 0부터 시작하거나 1부터 시작할 수 있습니다.
⚠️ : 간선의 수 기준 → 0, 노드의 수 기준 → 1

위에 사진으로 예시를 들면 간선 기준으로는 높이가 3이 되고, 노드 기준으로 보면 높이는 4가 됩니다.

그리고 구현 단계와 이해의 단계는 항상 다르기에 코드적인 관점에서의 그림을 구현할 때 이해를 돕기 위해 넣어보았습니다.

• 이진트리 (Binary Tree)

  • 완전이진트리

    

    완전이진트리를 충족하기 위해서는 2가지 조건이 충족해야 합니다.

    1. 마지막 레벨을 제외하고 모든 노드가 채워져있어야 한다.

    2. 노드는 왼쪽에서 오른쪽 방향으로 채워져야 합니다.

       다음은 완전이진트리를 설립하지 않는 예시 입니다.

       

       완전이진트리 구현 - C

       #include <stdio.h>
       #include <stdlib.h>
       
       #define MAX_SIZE 100
       
       typedef struct {
           int data[MAX_SIZE];
           int size;
       } CompleteBinaryTree;
       
       // 초기화
       void initTree(CompleteBinaryTree* tree) {
           tree->size = 0;
       }
       
       // 트리에 값 삽입
       void insert(CompleteBinaryTree* tree, int value) {
           if (tree->size >= MAX_SIZE) {
               printf("트리가 가득 찼습니다.\n");
               return;
           }
           tree->data[++(tree->size)] = value;  // 인덱스 1부터 시작
       }
       
       // 중위 순회 (왼쪽 - 루트 - 오른쪽)
       void inorderTraversal(CompleteBinaryTree* tree, int index) {
           if (index > tree->size) return;
       
           inorderTraversal(tree, 2 * index);         // 왼쪽 자식
           printf("%d ", tree->data[index]);          // 현재 노드
           inorderTraversal(tree, 2 * index + 1);     // 오른쪽 자식
       }
       
       // 전위 순회 (루트 - 왼쪽 - 오른쪽)
       void preorderTraversal(CompleteBinaryTree* tree, int index) {
           if (index > tree->size) return;
       
           printf("%d ", tree->data[index]);         // 현재 노드
           preorderTraversal(tree, 2 * index);       // 왼쪽 자식
           preorderTraversal(tree, 2 * index + 1);   // 오른쪽 자식
       }
       
       // 후위 순회 (왼쪽 - 오른쪽 - 루트)
       void postorderTraversal(CompleteBinaryTree* tree, int index) {
           if (index > tree->size) return;
       
           postorderTraversal(tree, 2 * index);       // 왼쪽 자식
           postorderTraversal(tree, 2 * index + 1);   // 오른쪽 자식
           printf("%d ", tree->data[index]);          // 현재 노드
       }
       
       // 직접 구현
       int main() {
           
       }

  • 포화이진트리

    

    포화이진트리를 충족하기 위해서는 2가지 조건이 충족해야 합니다.

    1. 모든 노드가 2개의 자식을 가지고 한다. (노드의 갯수 : $2^{k+1}-1$, k : 트리의 레벨)

    2. leaf노드가 모두 같은 레벨이여야 한다.

       포화이진트리 구현 - C

       #include <stdio.h>
       #include <stdlib.h>
       #include <math.h>
       
       // 노드 구조체 정의
       typedef struct Node {
           int data;
           struct Node* left;
           struct Node* right;
       } Node;
       
       // 새 노드 생성 함수
       Node* createNode(int data) {
           Node* newNode = (Node*)malloc(sizeof(Node));
           if (!newNode) {
               printf("메모리 할당 실패\n");
               exit(1);
           }
           newNode->data = data;
           newNode->left = NULL;
           newNode->right = NULL;
           return newNode;
       }
       
       // 포화 이진 트리 생성 함수
       Node* buildFullBinaryTree(int currentLevel, int maxLevel, int* value) {
           if (currentLevel > maxLevel)
               return NULL;
       
           Node* root = createNode((*value)++);
           root->left = buildFullBinaryTree(currentLevel + 1, maxLevel, value);
           root->right = buildFullBinaryTree(currentLevel + 1, maxLevel, value);
           return root;
       }
       
       // 중위 순회(In-order Traversal)
       void inorderTraversal(Node* root) {
           if (root == NULL)
               return;
       
           inorderTraversal(root->left);
           printf("%d ", root->data);
           inorderTraversal(root->right);
       }
       
       // 트리 메모리 해제
       void freeTree(Node* root) {
           if (root == NULL)
               return;
       
           freeTree(root->left);
           freeTree(root->right);
           free(root);
       }
       
       // 직접 구현
       int main() {
           
       }

  • 편향이진트리

    

    편향이진트리를 충족하기 위해서는 2가지 조건이 충족해야 합니다.

    1. 루트노드를 제외한 모든 노드들은 각 레벨에 왼쪽 또는 오른쪽으로만 형성되어야 한다.

    2. 각 레벨에 노드는 1개만 있다.

       편향이진트리 구현 - C

       #include <stdio.h>
       #include <stdlib.h>
       
       // 트리 노드 구조체
       typedef struct Node {
           int data;
           struct Node* left;
           struct Node* right;
       } Node;
       
       // 노드 생성 함수
       Node* createNode(int data) {
           Node* newNode = (Node*) malloc(sizeof(Node));
           if (!newNode) {
               printf("메모리 할당 실패\n");
               exit(1);
           }
           newNode->data = data;
           newNode->left = NULL;
           newNode->right = NULL;
           return newNode;
       }
       
       // 오른쪽 편향 이진 트리 삽입
       Node* insertRightSkewed(Node* root, int data) {
           if (root == NULL) {
               return createNode(data);
           }
           Node* current = root;
           while (current->right != NULL) {
               current = current->right;
           }
           current->right = createNode(data);
           return root;
       }
       
       // 왼쪽 편향 이진 트리 삽입
       Node* insertLeftSkewed(Node* root, int data) {
           if (root == NULL) {
               return createNode(data);
           }
           Node* current = root;
           while (current->left != NULL) {
               current = current->left;
           }
           current->left = createNode(data);
           return root;
       }
       
       // 중위 순회
       void inorderTraversal(Node* root) {
           if (root == NULL) return;
           inorderTraversal(root->left);
           printf("%d ", root->data);
           inorderTraversal(root->right);
       }
       
       // 메모리 해제
       void freeTree(Node* root) {
           if (root == NULL) return;
           freeTree(root->left);
           freeTree(root->right);
           free(root);
       }
       
       	// 직접 구현
       int main() {
           
       }