[C] 트리 : 이진트리

앞에서의 스택, 큐, 연결리스트는 선형 자료구조였다.

선형 자료구조란 자료들이 선형으로 나열되어있는 구조이다.

 

트리는 자료가 계층적인 구조로 이루어져있다.

예를 들면 가족의 가계도, 컴퓨터의 디렉토리 구조 등이 있다.

 

그래프와 트리의 차이점은,

사이클이 존재하면 그래프이고

사이클이 없고 상하관계가 존재하면 트리이다.

 

-트리의 용어

루트 : 가장 높은 곳에 존재하는 노드

서브트리 : 루트가 아닌 나머지 노드들

간선 : 노드들을 연결하는 연결선 = edge

관계 : 부모, 자식, 형제, 조상, 자손 관계가 존재

(개념은 인간 관계랑 같음!)

단말노드 : 자식이 없는 노드

비단말노드 : 단말노드의 반대

차수 : 한 노드가 가지고 있는 자식 노드의 개수

레벨 : 트리의 각 층에 번호를 매긴 것

(루트는 레벨 1, 루트의 자식노드는 레벨 2)

높이 : 트리가 가진 최대 레벨

---

이진트리의 정의

(1) 공집합이거나

(2) 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합으로 정의된다.

이진트리의 서브트리들은 모두 이진트리여야 한다.

 

쉽게 말해 이진트리란, 차수가 2인 트리이다.

(자식 노드의 갯수가 2개인 트리)

 

n개의 노드를 가진 이진트리는 n-1개의 간선을 가진다

높이가 h인 이진트리의 경우,

최소 h개의 노드부터 ~ 최대 2의h승에서 하나 뺀 개수의 노드를 가진다.

 

완전 이진트리란

위에서 부터 빈 곳 없이 노드가 다 차있고

제일 아래 레벨에서는 왼쪽부터 오른쪽으로

노드가 순서대로 채워져있는 이진트리를 말한다.

---

연결리스트에서 쓰인 링크를 이용해 이진트리를 구현해보자.

왼쪽 자식노드와 오른쪽 자식노드를 링크를 이용해 표현한다.

 

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

typedef struct TreeNode {
	struct TreeNode* left; //왼쪽 자식노드
	int data;
	struct TreeNode* right; //오른쪽 자식노드
}TreeNode;

//		n1
//		/\
//	n2		n3

int main() {
	TreeNode* n1, * n2, * n3;
	n1 = (TreeNode*)malloc(sizeof(TreeNode));
	n2 = (TreeNode*)malloc(sizeof(TreeNode));
	n3 = (TreeNode*)malloc(sizeof(TreeNode));
	n1->data = 10; n2->data = 20; n3->data = 30;
	n1->left = n2; n1->right = n3;
	n2->left = NULL; n2->right = NULL;
	n3->left = NULL; n3->right = NULL;

	free(n1); free(n2); free(n3);
}

 

이렇게 하면

        n1(10) 

      /          \

n2(20)      n3(30)

 

이런 모양의 트리가 생성된다.

다음 포스팅은 트리의 순회방법에 대해 할 예정이다 ^^*

 

 

 

 

[참고자료] C언어로 쉽게 풀어 쓴 자료구조, 생능출판, 천인국 공용해 하상호 지음