트리 (Tree)

 

트리 종류

이진트리 : 각 노드가 최대 두 개의 자식을 갖는 트리

이진 탐색 트리 : '모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들'의 속성을 갖는 이진트리

완전 이진트리 : 모든 높이에서 노드가 꽉 차 있는 이진 트리, 마지막 단계는 왼쪽에서 오른쪽으로 채워져야 한다.

전 이진 트리 : 모든 노드의 자식이 없거나 정확히 두 개 있는 트리.

포화 이진 트리 : 전 이진트리이면서 완전 이진트리인 경우를 말한다.

균형 트리 : 트리의 왼쪽과 오른쪽 부분이 어느 정도 균형이 잡혀있는 트리 (레드-블랙 트리, AVL 트리)

 

트리 순회

중위 순회 : 왼쪽 가지, 현재 노드, 오른쪽 가지 순서로 방문

전위 순회 : 현재 노드, 왼쪽 가지, 오른쪽 가지 순서로 방문

후위 순회 : 왼쪽 가지, 오른쪽 가지, 현재 노드 순서로 방문

 

/*
	코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

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

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

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