자료구조의 기초

자료구조

: 프로그램에서 사용된 데이터를 얼마나 잘 정리한 것이냐를 나타냄 

>자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 "자료의 추상화"가 필요함
> 자료구조(data structure) : 추상화를 통해 자료의 논리적 관계를 구조화한 것
=> 자료나 소프트웨어가 복잡해질수록 자료구조의 중료성이 강조됨 

*추상화란? 
공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것 (수식, 프로그램 언어 등)
ex) 지하철 노선도, 화재 발생 대피도, 놀이공원 시설 배치도 등
*자료(데이터)의 추상화
: 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 "데이터의 구조에 대해서 공통의 특징만을 뽑아 정의"한 것

트리용어 
선형구조는 a:b:c 즉, 1:1 관계
비선형은 1:n 즉, 하나가 관계 있는 애가 두 개가 될 수 있음
계층적인 관계성, 노드(node)-가지(branch)
노드 : 정보 항목 
루트는 빈 트리가 아닐 때, 맨 꼭대기에 있는 1개의 노드 
차수 : 각 노드에 있는 가지의 수


*레벨은 간석의 측면이 크고, 깊이나 높이는 노드에 집중 
노드의 길이는 단말 노드의 레벨에 1을 더한 것
서브트리, 루트노트 아래 연결된 구조의 트리 
숲 : n개 서브트리에서 루트 노드 제거해서 얻을 수 있는 분리된 서브 트리 집합

이진 트리 
차수가 2인 트리 모든 차수가 2를 넘지 않고 최대 2개의 서브트리를 가짐
왼쪽노드와 오른쪽노드에 '순서'의 의미를 부여함

이진 트리 순회 연산
- 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문 하는 것

1) DLR (Data Left Right; 전위 순회; preorder)
: 루트 노드 방문
-> 왼쪽 서브트리 방문
-> 오른쪽 서브트리 방문

2) LDR (Left Data Right; 중위 순회; inorder)
: 왼쪽 서브트리 방문
-> 루트 노드 방문
-> 오른쪽 서브트리 방문
전체 순서를 각 서브트리에 적용한다 .  왼1 뤁2 오3 

3) LRD (Left Right Data; 후위 순회; postorder)
:왼쪽 서브트리 방문
-> 오른쪽 서브 트리 방문
-> 루트 노드 방문