자료구조 :: 트리(1) "이진트리, 이진트리 순회"

# 이진 트리

BinaryTree.cpp

이진트리의 정의
공집합이거나 루트와 왼쪽 서브트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다.
이진트리의 서브트리들은 모두 이진트리여야 한다.

이진트리의 성질
(1) n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다.
(2) 높이가 n인 이진 트리의 경우, 최소 n개의 노드를 가지며 최대2ⁿ-1 개의 노드를 가진다.
(3) n개의 노드를 가지는 이진 트리의 높이는 최대n이거나 최소 log₂(n+1)이 된다.

이진트리의 분류
(1) 포화이진트리 : 각 레벨에 노드가 꽉 차있는 이진트리
(2) 완전이진트리 : 높이가 k일때 레벨1부터 k-1까지 노드가 모두 채워져있고 마지막 레벨k에서는 왼쪽에서
                                 오른쪽으로 노드가 순서대로 채워져있는 이진 트리
(3) 기타이진트리 : 위 분류에 포함되지 않은 이진트리(사향이진트리)

이진트리의 순회 (V : 루트, L : 왼쪽, R : 오른쪽)
(1) 전위순회 : 루트,왼쪽 서브트리,오른쪽 서브트리 순으로 방문하는 방법(VLR)
(2) 중위순회 : 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문하는 방법(LVR)
(3) 후위순회 : 왼쪽쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문하는방법(LRV)
(4) 레벨순회 : 큐(Queue)를 이용하여 각 노드를 레벨 순으로 검사하는 순회방법

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

typedefstruct TreeNode 
{ 
int data; 
    TreeNode *left,*right; 
}TreeNode; 

void PreOrder(TreeNode *node) // 전위 순회 V(루트) -> L(왼쪽) -> R(오른쪽) 
{ 
if(node) 
    { 
        printf("%d->",node->data); 
        PreOrder(node->left); 
        PreOrder(node->right); 
    } 
} 

void InOrder(TreeNode *node) // 중위 순회 L(왼쪽) -> V(루트) -> R(오른쪽)
{ 
if(node) 
    { 
        InOrder(node->left); 
        printf("%d->",node->data); 
        InOrder(node->right); 
    } 
} 

void PostOrder(TreeNode *node) // 후위 순회 L(왼쪽) -> R(오른쪽) -> V(루트)
{ 
if(node) 
    { 
        PostOrder(node->left); 
        PostOrder(node->right); 
        printf("%d->",node->data);         
    } 
} 

int main() 
{ 
    TreeNode *root,*n1,*n2,*n3,*n4; 
    root=(TreeNode*)malloc(sizeof(TreeNode)); 
    n1=(TreeNode*)malloc(sizeof(TreeNode)); 
    n2=(TreeNode*)malloc(sizeof(TreeNode)); 
    n3=(TreeNode*)malloc(sizeof(TreeNode)); 
    n4=(TreeNode*)malloc(sizeof(TreeNode)); 

    root->data=1; 
    root->left=n1; 
    root->right=n2; 
    n1->data=2; 
    n1->left=n3; 
    n1->right=n4; 
    n2->data=3; 
    n2->left=n2->right=NULL; 
    n3->data=4; 
    n3->left=n3->right=NULL; 
    n4->data=5; 
    n4->left=n4->right=NULL; 
/* 트리구조 
　 　1 
　　/ ＼ 
　　2　 3 
　　/＼ 
 　4　 5 
*/

    PreOrder(root);  printf(" // 전위순회\n"); // 1->2->4->5->3
    InOrder(root);   printf(" // 중위순회\n"); // 4->2->5->1->3
    PostOrder(root); printf(" // 후위순회\n"); // 4->5->2->3->1

return0; 
}