3.10 나무(TREE)

1. 3.10 나무(TREE)
   1. TREE
   2. 문서에 대하여

TREE

정의
리스트와 스택 큐 자료들 처럼 선의 형태러 나열되어 있는 구조를 선형 자료구조 라고 하며 그렇지 않은걸 비선형 자료 라고 한다.
이 비선형 자료구조중에 자료들간에 계층의 형태를 가진 자료구조중의 하나가 TREE 이다.

TREE 코드를 구현 하기 위한 최소한의 용어 정의는 아래와 같다 이정도만 알고 넘어가도 코드 구현하는데 딱히 문제는 없어 보인다.

TREE용어
노드 : 트리의 구성 요소 혹은 원소
간선 : 노드를 연결하는 선
루트노드 : 트리의 시작 노드
서브트리 : 노드의 자식 노드로 구성된 트리, 자식노드들은 각각 독립하여 새로운 트리를 구성할수 있고
각 노드는 자식노드 수만큼 서브트리를 갖는다.
차수 : 한 노드가 가지는 서브트리의 수(자식노드의 수)

TREE 의 구현방법
1. 배열을 이용한 순차 자료구조 방식 : 전에도 보았겠지만 자료구조에서 배열은 대부분 그다지 좋은 선택이 되지 못한다.(메모리 낭비 부터 , 삽입 삭제 연산이 너무 비효율적)
2. 더블링크드 리스트를 이용한 연결자료구조 방식

구현 방법중에서 1의 경우에 사용되는 공식(아래 공식은 2진 트리 일겨우에만 해당된다.)

구현 방법중에서 2의 경우에 노드의 구성형태

이진트리의 순회방법

• 스택이나 큐와 같은 선형 자료구조의 경우 순회하는 방법이 제한되었지만 트리는 계층형의 구조를 지니고 있기 때문에 여러가지 순회 방법이 있을수 있다.

이진탐색트리

• 이진 트리는 트리를 효율적으로 사용하기 위해서 일정한 형태로 정의한 것이다.
• 그리고 탐색을 위한 자료구조로 이진트리를 사용하기 위해서 노드의 크기에 따라 노드의 위치를 정의한것이
• 이진탐색트리 이다.

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.
3. 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.
4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다. 

트리의 기본적인 설명은 위와 같다. 좀더 자세히 알아 보자면
트리의 삭제 삽입 연산과 삭제시 단말노드인 경우 차수가 1개일때 그리고 2개일때 서로 달라지는 알고리즘이 존재 하며
완전이진 트리 중에 노드의 키값이 가장 큰 노드나 작은 노드를 찾기 위해 만든 힙 이라는 자료구조도 있다.
이것들에 대한 설명은 뒤로 미루고 여기서는 트리의 기본적인 흐름을 알아볼수 있게 스택의 CALC 를 이용한
사칙연산 코드를 트리로 구현해 보면서 이번장을 마무리 하겠다.

문서에 대하여

• 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
• 최초작성자 : 허용운
• 최초작성일 : 2009년 2월 20일
• 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
• 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^