| sitelink1 | |
|---|---|
| sitelink2 | |
| sitelink3 | |
| sitelink4 | |
| sitelink5 | |
| extra_vars6 |
http://blog.naver.com/simtwolove?Redirect=Log&logNo=30022013436
자료구조가 무엇인지는 본 블로그의 "자료구조알고리즘" 항목의
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part8 트리 - 이진트리의 기본.
--------------------------------------
트리 - 이진트리의 강의 입니다.
선린 인터넷 고등학교 20420 전호근.
--------------------------------------
트리의 노드의 차수에는 제한이 없으므로 임의의 개수의 자식을 가질 수 있다.
즉, 하나의 노드가 자식을 1개던, 2개던, 50개던 상관이 없다.
이런 노드를 표현하려면 다음과 같은 구조체를 선언해야 한다.
struct Node
{
int data; - 데이타 들어갈 곳
Node *link; - 연결하는 포인터
};
트리역시 노드의 집합체라 할 수 있으므로 연결리스트와 상당히 비슷하다.
data는 이 노드가 저장할 실제 데이터이며 필요에 따라 얼마든지 더 많은 멤버들을 포함할 수 있다.
(역시 연결리스트와 마찬가지)
link는 자식 노드들로 연결되는 링크의 배열이며 자식의 개수만큼 동적으로 할당된다.
또는 최대 차수를 미리 알 수 있다면 정적 배열로도 선언할 수 있다.
이런 노드들이 서로를 가리킴으로써 트리를 구성한다.
자식의 개수가 정해져 있지 않기 때문에(몇개인지 모름) 노드의 차수에 따라 링크의 개수가 가변적이다.
동적 할당해서 만드는 노드의 멤버가 또 동적 할당을 한다면 관리하기 무척 번거롭고 불편해진다.
그렇다고 해서 최대 차수만큼의 정적 배열을 할당하면 적은양의 자식만 가지는 노드는 나머지 미사용 링크의 낭비가 심해지고, 또 최대차수 이상의 자식을 가지지 못하는 단점이 있다.
그래서 임의 차수를 지원하는 트리는 잘 사용되지 않으며 차수의 최대값을 일정한 크기로 제한한다.
이진 트리(Binary Tree)는 모든 노드의 차수가 2이하인 트리이며 구조가 단순하기 때문에 현실적으로 가장 많이 사용된다.
즉, 이진트리⊂트리 의 식이 성립되는 트리의 일종이라 할 수 있다.
이진 트리의 노드는 자식을 최대 2개까지만 가질 수 있으므로 다음과 같은 구조체로 간단하게 표현할 수 있다.
struct Node
{
int data;
Node *left; - 왼쪽자식을 가리킴
Node *right; - 오른쪽자식을 가리킴
};
노드에 저장되는 데이터와 좌우 두 개의 링크를 가진다.
left가 왼쪽 자식을 가리키며 right가 오른쪽 자식을 가리킨다.
물론 양쪽 자식이 모두 존재할 필요는 없으며 자식이 없는 잎(Leaf) 노드일 경우 링크는 모두 NULL값을 가질 것이다.
이진트리의 종류는 다음과 같다.
포화 이진 트리(Full Binary Tree) :
트리의 높이까지 모든 노드가 가득찬 트리이다.
높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며 높이가 2이면 루트와 양쪽 자식을 합쳐 세 개의 노드가 존재한다.
높이가 3이면 7개, 4이면 15개이며 일반적으로 높이가 n인 포화 이진 트리의 노드 개수는 2n-1개이다.
첫 번째 트리의 높이는 3인데 노드의 개수가 7(23-1)개이므로 이 트리는 포화 이진 트리이다.
보다시피 빈틈없이 모든 노드가 가득 차 있으며 잎 노드를 제외하고는 모두 차수가 2이다.
완전 이진 트리(Complete Binary Tree) :
포화 이진 트리의 노드를 좌에서 우로, 위에서 아래로 번호를 붙였을 때 번호가 큰 뒤쪽 노드만 생략된 트리이다. 같은 높이의 포화 이진 트리와 대응되는 노드의 순서값이 일치한다.
다음 그림을 통해 두 이진 트리를 구분해 보자.
포화 이진 트리에서 7, 6, 5 를 차례대로 생략할 때 이 트리를 완전 이진 트리라고 한다.
그러나 아래쪽은 순서값이 빠른 노드가 먼저 생략되어 포화 이진 트리의 노드 순서값과 같지 않으므로 완전 이진 트리는 아니다.
쉽게 설명하자면,
완전 이진 트리는 위에서 아래로, 왼쪽에서 오른쪽으로 순서를 부여할 때, 중간에 빠진 게 없는 이진 트리 이다.
<->
즉, 위 그림에서 분홍색 동그라미는 없는 노드라 생각할 때, 먼저 부여될 3이 삭제 된 노드이기 때문에
완전 이진트리는 아니다.
그에 비해
<->
그러나 이 그림은 순서값이 느린 노드가 생략되어 완전 이진트리가 맞다.
삭제된 노드보다 순서가 빠른 노드는 모두 살아있다는 소리이다.
정의가 조금 복잡하지만 쉽게 말하자면 포화 이진 트리에서 중간에 빠진 노드가 없는 트리를 완전 이진 트리라고 한다.
높이가 n인 완전 이진 트리의 노드 개수는 2n-1보다 크거나 같고 2n-1보다 작거나 같다.
포화 이진 트리는 물론 완전 이진 트리의 일종이다.
이하 이진트리의 사용법은 트리와 유사하며 다음강의는 트리의 순회에 대해 알아보자.
-----------------------------------------
WinAPI의 글을 초보자가 더 쉽게 공부할 수 있도록
추가, 삭제 및 재구성 한 글 입니다.
첫번째 글에 자료구조에 대한 설명이 대략 있음을 알린다.
Part8 트리 - 이진트리의 기본.
--------------------------------------
트리 - 이진트리의 강의 입니다.
선린 인터넷 고등학교 20420 전호근.
--------------------------------------
트리의 노드의 차수에는 제한이 없으므로 임의의 개수의 자식을 가질 수 있다.
즉, 하나의 노드가 자식을 1개던, 2개던, 50개던 상관이 없다.
이런 노드를 표현하려면 다음과 같은 구조체를 선언해야 한다.
struct Node
{
int data; - 데이타 들어갈 곳
Node *link; - 연결하는 포인터
};
트리역시 노드의 집합체라 할 수 있으므로 연결리스트와 상당히 비슷하다.
data는 이 노드가 저장할 실제 데이터이며 필요에 따라 얼마든지 더 많은 멤버들을 포함할 수 있다.
(역시 연결리스트와 마찬가지)
link는 자식 노드들로 연결되는 링크의 배열이며 자식의 개수만큼 동적으로 할당된다.
또는 최대 차수를 미리 알 수 있다면 정적 배열로도 선언할 수 있다.
이런 노드들이 서로를 가리킴으로써 트리를 구성한다.
자식의 개수가 정해져 있지 않기 때문에(몇개인지 모름) 노드의 차수에 따라 링크의 개수가 가변적이다.
동적 할당해서 만드는 노드의 멤버가 또 동적 할당을 한다면 관리하기 무척 번거롭고 불편해진다.
그렇다고 해서 최대 차수만큼의 정적 배열을 할당하면 적은양의 자식만 가지는 노드는 나머지 미사용 링크의 낭비가 심해지고, 또 최대차수 이상의 자식을 가지지 못하는 단점이 있다.
그래서 임의 차수를 지원하는 트리는 잘 사용되지 않으며 차수의 최대값을 일정한 크기로 제한한다.
이진 트리(Binary Tree)는 모든 노드의 차수가 2이하인 트리이며 구조가 단순하기 때문에 현실적으로 가장 많이 사용된다.
즉, 이진트리⊂트리 의 식이 성립되는 트리의 일종이라 할 수 있다.
이진 트리의 노드는 자식을 최대 2개까지만 가질 수 있으므로 다음과 같은 구조체로 간단하게 표현할 수 있다.
struct Node
{
int data;
Node *left; - 왼쪽자식을 가리킴
Node *right; - 오른쪽자식을 가리킴
};
노드에 저장되는 데이터와 좌우 두 개의 링크를 가진다.
left가 왼쪽 자식을 가리키며 right가 오른쪽 자식을 가리킨다.
물론 양쪽 자식이 모두 존재할 필요는 없으며 자식이 없는 잎(Leaf) 노드일 경우 링크는 모두 NULL값을 가질 것이다.
이진트리의 종류는 다음과 같다.
포화 이진 트리(Full Binary Tree) :
트리의 높이까지 모든 노드가 가득찬 트리이다.
높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며 높이가 2이면 루트와 양쪽 자식을 합쳐 세 개의 노드가 존재한다.
높이가 3이면 7개, 4이면 15개이며 일반적으로 높이가 n인 포화 이진 트리의 노드 개수는 2n-1개이다.
첫 번째 트리의 높이는 3인데 노드의 개수가 7(23-1)개이므로 이 트리는 포화 이진 트리이다.
보다시피 빈틈없이 모든 노드가 가득 차 있으며 잎 노드를 제외하고는 모두 차수가 2이다.
완전 이진 트리(Complete Binary Tree) :
포화 이진 트리의 노드를 좌에서 우로, 위에서 아래로 번호를 붙였을 때 번호가 큰 뒤쪽 노드만 생략된 트리이다. 같은 높이의 포화 이진 트리와 대응되는 노드의 순서값이 일치한다.
다음 그림을 통해 두 이진 트리를 구분해 보자.
포화 이진 트리에서 7, 6, 5 를 차례대로 생략할 때 이 트리를 완전 이진 트리라고 한다.
그러나 아래쪽은 순서값이 빠른 노드가 먼저 생략되어 포화 이진 트리의 노드 순서값과 같지 않으므로 완전 이진 트리는 아니다.
쉽게 설명하자면,
완전 이진 트리는 위에서 아래로, 왼쪽에서 오른쪽으로 순서를 부여할 때, 중간에 빠진 게 없는 이진 트리 이다.
<->즉, 위 그림에서 분홍색 동그라미는 없는 노드라 생각할 때, 먼저 부여될 3이 삭제 된 노드이기 때문에
완전 이진트리는 아니다.
그에 비해
<->그러나 이 그림은 순서값이 느린 노드가 생략되어 완전 이진트리가 맞다.
삭제된 노드보다 순서가 빠른 노드는 모두 살아있다는 소리이다.
정의가 조금 복잡하지만 쉽게 말하자면 포화 이진 트리에서 중간에 빠진 노드가 없는 트리를 완전 이진 트리라고 한다.
높이가 n인 완전 이진 트리의 노드 개수는 2n-1보다 크거나 같고 2n-1보다 작거나 같다.
포화 이진 트리는 물론 완전 이진 트리의 일종이다.
이하 이진트리의 사용법은 트리와 유사하며 다음강의는 트리의 순회에 대해 알아보자.
-----------------------------------------
WinAPI의 글을 초보자가 더 쉽게 공부할 수 있도록
추가, 삭제 및 재구성 한 글 입니다.
