루프노드에서 가지를 통해 리프노드로 연결된다.
각각의 노드는 위와래를 부모와 자식 노드로 분류하고
한 부모아래의 자식노드 사이를 형제 노드라고 분류한다.
트리의 길이(Length)란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다.
ex) 13에서 27까지의 길이: 3
트리의 깊이(Depth)란 루트 노드에서 특정 노드까지의 길이를 의미한다.
ex) 1의 깊이: 1
트리의 높이(Height)란 루트 노드에서 가장 깊은 노드까지의 길이이다.
이진트리
최대 2개의 자식을 가질 수 있는 트리이다.
포화 이진 트리(Full Binary Tree)는 리프 노드를 제외한 모든 노드가 두 자식을 가지는 트리이다.
완전 이진 트리(Complete Binary Tree)는 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드이다.
높이 균형 트리(Height Balanced Tree)는 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가
1이상 차이 나지 않는 트리이다.
이진트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있는 데이터 활용의 효율성이 높은 자료구조이다.
데이터 저장, 탐색 등의 다양한 목적에서 사용할 수 있다.
이진트리
포인터를 이용해서 구현하면 효과적인 데이터 관리가 가능
#include<stdio.h>
#include<stdlib.h>
typedef struct{
int data;
struct Node *leftChild;
structt Node *rightChild;
}Node;
Node *initNode(int data, Node *leftChild, Node *rightChild){
Node *node =(Node*)malloc(sizeof(Node));
node->data=data;
node->leftChild=leftChild;
node->rightChild=rightChild;
return node
}
void preorder(Node *root){
if(root){
printf("%d ",root->data);
preorder(root0>leftChild);
preorder(root->rightChild);
}
}
void indorder(Node *root){
if(root){
inorder(root->leftChild);
printf("%d ",root->data);
inorder(root->rightChild);
}
}
void postorder(Node *root){
if(root){
postorder(root->leftChild);
postorder(roo->rightChild);
printf("%d ", root->data);
}
}
int main(void){
Node *n7=initNode(50, NULL, NULL);
Node *n6=initNode(37, NULL, NULL);
Node *n5=initNode(23, NULL, NULL);
Node *n4=initNode(5, NULL, NULL);
Node *n3=initNode(48, n6, n7);
Node *n2=initNode(17, n4, n5);
Node *n1=initNode(30, n2, n3);
preorder(n1);
printf("\n");
inorder(n1);
printf("\n");
postorder(n1);
system("pause");
return 0;
}
이진트리의 전위 순회
1) 자기 자신을 출력
2) 왼쪽 자식을 방문
3) 오른쪽 자식을 방문
이진트리의 중위 순회
1) 왼쪽 자식을 방문
2) 자기 자신을 출력
3) 오른쪽 자식을 방문
이진트리의 후위 순회
1) 왼쪽 자식을 방문
2) 오른쪽 자식을 방문
3) 자기 자신을 출력