트리 자료구조 c언어 ( 이진 트리 )

트리 자료구조 중에서 대표적인 트리인 이진 트리 예시

 

* 전위 순회 , 중위 순회 , 후위 순회  쉽게 구분하는 법 :  root 가 몇번째 순서에 있는지 체크하면 편하다

(전)   left   (중)   right  (후)   :   그리고  left  right  이 순서는 고정이다

 

전위 순회 :  root   left     right

중위 순회 :  left    root    right

후위 순회 :  left    right    root

 

 

---

 

 

 

 

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

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 노드 생성
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 중위 순회
void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// 전위 순회
void preorder(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// 후위 순회
void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// 트리의 높이 계산 (루트 기준)
int getHeight(Node* root) {
    if (root == NULL) return -1; // 높이를 edge 수로 계산 시 -1, 노드 수로 계산 시 0
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 특정 노드의 깊이 계산
int getDepth(Node* root, int target, int depth) {
    if (root == NULL) return -1;
    if (root->data == target) return depth;

    // 왼쪽 서브트리 탐색
    int left = getDepth(root->left, target, depth + 1);
    if (left != -1) return left;

    // 오른쪽 서브트리 탐색
    return getDepth(root->right, target, depth + 1);
}

// 메모리 해제
void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// 테스트 main 함수
int main() {
    // 트리 구성
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    /*
           1
         /   \
        2     3
       / \
      4   5
    */

    printf("Inorder: ");
    inorder(root);
    printf("\n");

    int height = getHeight(root);
    printf("트리의 높이: %d\n", height); // 2

    int target = 5;
    int depth = getDepth(root, target, 0);
    if (depth != -1)
        printf("노드 %d의 깊이: %d\n", target, depth); // 2
    else
        printf("노드 %d를 찾을 수 없습니다.\n", target);

    freeTree(root);
    return 0;
}