[자료구조] [8] 트리

트리

-트리의 개념

선형 자료 구조: 스택, 큐, 리스트 -> 자료들이 일렬로 나열된 형태

트리는 계층적인 자료를 표현하는데 이용되는 자료구조.

예) 회사 조직도, 컴퓨터 폴더 구조, 인공지능의 결정 트리..

A,B,C,D,E,F,G,H,I,J는 노드(node)
트리는 한 개 이상의 노드로 이루어지고, 계층적 구조에서 가장 높은 곳에 있는 노드는 루트(root) 노드
나머지 노드들은 서브 트리(subtree). -> 루트의 다음 레벨에 있는 노드들은 서브 트리들의 루트가 된다.
루트와 서브트리를 연결하는 선은 간선/에지
A는 B의 부모 노드. B는 A의 자식 노드. B,C,D는 형제.
자손 노드 : 임의의 노드 하위에 연결된 모든 노드들. 즉 어떤 노드의 서브 트리에 속하는 모든 노드들은 자손노드.
단말노드 : 자식 노드가 없는 노드 / 그렇지 않으면 비단말 노드
차수(degree) : 어떤 노드가 갖고있는 자식의 수. -> 그림에서 루트노드는 자식 노드가 3개이므로 차수가 3. 트리의 차수는 트리가 갖고 있는 노드의 차수 중 가장 큰 값=3.
레벨 : 트리의 각층에 번호 매기는 것. -> 그림에서 A의 레벨은 1, B,C,D의 레벨은 2.
트리의 높이 : 트리가 갖고있는 최대 레벨.

트리를 표현하는 가장 일반적인 방법은 노드 구조를 이용하는 것.

*노드 : 데이터 필드, 링크 필드

실제로는 두 개의 자식 노드를 사용하는 이진트리(binary tree)가 많이 사용됨.

부모는 왼쪽과 오른쪽 자식에 바로 접근 가능.

- 이진트리의 노드 구조 : 데이터 필드, 링크 필드(링크1:왼쪽 자식,링크2: 오른쪽 자식)

이진 트리

모든 노드가 2개의 서브트리를 갖는 트리. 서브 트리는 공집합일 수도 있다.

최대 2개까지의 자식 노드를 가질 수 있는데, 자식들 사이에도 순서가 존재해 왼쪽 자식과 오른쪽 자식은 반드시 구별.

공집합이거나
루트와 왼쪽 서브트리, 오른쪽 서브 트리로 구성된 노드들의 유한집합으로 정의. 이진트리의 서브 트리들은 모두 이진트리여야 한다.

- 이진트리의 분류

포화 이진트리 : 트리의 각 레벨에 노드가 꽉 차있는 이진트리. 레벨 단위로 각 노드에 왼쪽에서 오른쪽으로 순서대로 번호를 붙일 수 있다. 이 번호는 항상 일정한데, 루트 노드의 오른쪽 자식 노드의 번호는 항상 3.

2. 완전 이진트리 : 마지막 레벨 전까지는 노드가 모두 채워져 있고, 마지막 레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리.

마지막 레벨에서는 노드가 꽉차있지 않아도 되지만, 중간에 빈 곳이 있으면 안됨. 오른쪽 그림은 왼쪽 서브트리의 노드에 빈 곳이 있으므로 완전 이진트리 X.

링크 표현법을 이용한 이진트리 구현

링크 표현법 : 포인터를 이용해 노드와 노드를 연결.

데이터 저장 필드, 두개의 포인터 변수는 각각 왼쪽 자식 노드 / 오른쪽 자식 노드를 가리킴.

- 이진트리의 순회

트리 순회 : 트리에 속하는 모든 노드를 한 번씩 방문하여 노드의 데이터를 목적에 맞게 처리.

예) 트리의 모든 항목들 출력

이진트리의 표준 순회에는 전위, 중위, 후위 3가지 방법이 있다.

루트와 왼쪽 서브트리, 오른쪽 서브트리를 각가 어떤 순서로 방문하느냐로 구분.

V: 루트방문 / L: 왼쪽 서브트리 방문 / R: 오른쪽 서브트리 방문

전위 순회(preorder traversal) : VLR
중위 순회(inorder traversal) : LVR
후위 순회(preorder traversal) : LRV

*루트 방문이 어디에 있느냐로 기억하면 될듯. 중위는 루트 방문이 중간 순서.

이진트리의 각각의 서브트리도 이진트리라서 각 서브트리의 노드들도 동일한 순회 방법이 적용.

- 전위 순회

전위 순회에서 루트노드의 방문을 마치고, 왼쪽 서브트리를 방문할 차례일 때

왼쪽 서브트리도 하나의 이진트리이기 때문에 똑같은 방식으로 방문하면 된다.

즉, 왼쪽 서브트리의 루트를 먼저 방문하고 왼쪽 서브트리의 왼쪽 서브트리를 방문, 마지막으로 왼쪽 서브트리의 오른쪽 서브트리를 방문.

void preorder(TNode* n) // 이진트리 전위 순회 함수 
{
	if( n!= nullptr )
    {
    	printf("[%c]",n->data); // 1. 루트 노드 처리
        preorder(n->left); // 2. 왼쪽 서브트리 방문
        preorder(n->right); // 3. 오른쪽 서브트리 방문
     }
}

- 중위 순회

void inorder(TNode* n) // 이진트리 중위 순회 함수 
{
	if( n!= nullptr )
    {
        inorder(n->left); // 1. 왼쪽 서브트리 방문
        printf("[%c]",n->data); // 2. 루트 노드 처리
        inorder(n->right); // 3. 오른쪽 서브트리 방문
     }
}

- 후위 순회

void postorder(TNode* n) // 이진트리 후위 순회 함수 
{
	if( n!= nullptr )
    {
        postorder(n->left); // 1. 왼쪽 서브트리 방문
        postorder(n->right); // 2. 오른쪽 서브트리 방문
        printf("[%c]",n->data); // 3. 루트 노드 처리
     }
}

- 순회 방법 선택

순서가 중요하지 않고 노드를 전부 방문하기만 하면 된다면 -> 3가지 방법 중 어떤 것이든 상관 X

예) 트리의 모든 노드 값 순서와 상관없이 출력

자식 노드 처리한 다음 부모 노드 처리해야 하는 문제 -> 후위 순회

예) 컴퓨터에서 각 폴더의 용량 계산 -> 하위 폴더의 용량이 계산되어야 이를 이용해 현재 폴더 용량 계산 가능

부모 노드 처리한 다음 자식 노드 처리해야 하는 문재 -> 전위 순회

예) 모든 노드에서 레벨 계산 -> 루트 노드의 레벨이 1, 모든 노드들은 부모 노드의 레벨보다 1이 크기 때문

- 연산들

- 노드 개수 구하기

이진트리 전체 노드의 개수를 세기 위해서는 모든 노드들의 순회가 필요.

왼쪽 서브트리의 노드 개수와 오른쪽 서브트리의 노드 개수에 루트 노드를 더하면 된다. -> 후위 순회 방식 사용

int count_node(TNode* n) // 이진트리 전체 노드 개수 구하는 순환 함수
	{
		if (n == nullptr)
			return 0;
		return 1 + count_node(n->left) + count_node(n->right); // 루트 + 왼쪽 서브트리 개수 + 오른쪽 서브트리 개수
	}

- 단말 노드 개수 구하기

왼쪽 자식과 오른쪽 자식이 동시에 NULL이면 단말노드이고 1을 반환.

아니면 비단말 노드이므로 각각의 서브트리에 대하여 순환 호출해 반환되는 두 값을 더해 반환하면 된다.

int count_leaf(TNode* n) // 이진트리 단말 노드 개수 구하는 순환 함수
	{
		if (n == nullptr)
			return 0;
		if (n->left == nullptr && n->right == nullptr)
			return 1;
		else return count_leaf(n->left) + count_leaf(n->right); // 비단말 노드면 각각의 서브트리에 대해 순환호출 해 반환되는 두값을 더해 반환.
	}

- 트리 높이 구하기

왼쪽 서브트리와 오른쪽 서브트리 중에서 더 높은 트리를 먼저 찾고, 이 트리의 높이에 1을 더한 값. -> 후위 순회

int calc_height(TNode* n)
	{
		if (n == nullptr)
			return 0;
		int hLeft = calc_height(n->left); // 왼쪽 서브트리 높이 계산해 저장
		int hRight = calc_height(n->right); // 오른쪽 서브트리 높이 계산해 저장
		return (hLeft > hRight) ? hLeft + 1 : hRight + 1; // 두 높이 중 더 높은 값에 1 더해서 반환
	}

* C++ 삼항(조건)연산자

'조건' : 'A' ? 'B' => 조건이 참이면 A를 반환하고 조건이 거짓이면 B를 반환합니다.

- 이진 트리 구현 코드

#include <iostream>

using namespace std;

typedef char TElement;

typedef struct BinTrNode {
	TElement data;
	BinTrNode* left; // 왼쪽 자식 노드
	BinTrNode* right; // 오른쪽 자식 노드
} TNode;

class CBinTree {
public:
	void init_tree() { root = nullptr; }
	bool is_empty() { return root == nullptr; }
	TNode* get_root() { return root; }
	void set_root(TNode* n) { root = n; }
	TNode* create_tree(TElement val, TNode* l, TNode* r) 
	{
		TNode* node = new TNode;
		node->data = val;
		node->left = l;
		node->right = r;
		return node;
	}
	void preorder(TNode* n) // 이진트리 전위 순회 함수 
	{
		if (n != nullptr)
		{
			printf("[%c]", n->data); // 1. 루트 노드 처리
			preorder(n->left); // 2. 왼쪽 서브트리 방문
			preorder(n->right); // 3. 오른쪽 서브트리 방문
		}
	}
	void inorder(TNode* n) // 이진트리 중위 순회 함수 
	{
		if (n != nullptr)
		{
			inorder(n->left); // 1. 왼쪽 서브트리 방문
			printf("[%c]", n->data); // 2. 루트 노드 처리
			inorder(n->right); // 3. 오른쪽 서브트리 방문
		}
	}
	void postorder(TNode* n) // 이진트리 후위 순회 함수 
	{
		if (n != nullptr)
		{
			postorder(n->left); // 1. 왼쪽 서브트리 방문
			postorder(n->right); // 2. 오른쪽 서브트리 방문
			printf("[%c]", n->data); // 3. 루트 노드 처리
		}
	}
	int count_node(TNode* n) // 이진트리 전체 노드 개수 구하는 순환 함수
	{
		if (n == nullptr)
			return 0;
		return 1 + count_node(n->left) + count_node(n->right); // 루트 + 왼쪽 서브트리 개수 + 오른쪽 서브트리 개수
	}
	int count_leaf(TNode* n) // 이진트리 단말 노드 개수 구하는 순환 함수
	{
		if (n == nullptr)
			return 0;
		if (n->left == nullptr && n->right == nullptr)
			return 1;
		else return count_leaf(n->left) + count_leaf(n->right); // 비단말 노드면 각각의 서브트리에 대해 순환호출 해 반환되는 두값을 더해 반환.
	}
	int calc_height(TNode* n)
	{
		if (n == nullptr)
			return 0;
		int hLeft = calc_height(n->left); // 왼쪽 서브트리 높이 계산해 저장
		int hRight = calc_height(n->right); // 오른쪽 서브트리 높이 계산해 저장
		return (hLeft > hRight) ? hLeft + 1 : hRight + 1; // 두 높이 중 더 높은 값에 1 더해서 반환
	}
private:
	TNode* root;
};


void main() {
	CBinTree binTr;
	TNode *b, *c, *d, *e, *f;
	d = binTr.create_tree('D', nullptr, nullptr);
	e = binTr.create_tree('E', nullptr, nullptr);
	b = binTr.create_tree('B', d, e);
	f = binTr.create_tree('F', nullptr, nullptr);
	c = binTr.create_tree('C', f, nullptr);
	binTr.set_root(binTr.create_tree('A', b, c));

	// 트리 테스트
	printf("\n In-Order(중위순회) : "); binTr.inorder(binTr.get_root());
	printf("\n Pre-Order(전위순회) : "); binTr.preorder(binTr.get_root());
	printf("\n Post-Order(후위순회) : "); binTr.postorder(binTr.get_root());

	printf("\n 노드의 개수 = %d\n ", binTr.count_node(binTr.get_root()));
	printf("\n 단말노드의 개수 = %d\n ", binTr.count_leaf(binTr.get_root())); 
	printf("\n 트리의 높이 = %d\n ", binTr.calc_height(binTr.get_root()));


}

'코딩테스트 및 개인공부 > 자료구조' 카테고리의 다른 글

[자료구조] [10] 우선순위 큐 (0)	2022.01.08
[자료구조] [9] 이진탐색트리 (0)	2021.12.30
[자료구조] [7] 순환 (0)	2021.12.29
[자료구조] [6] 리스트 (0)	2021.12.09
[자료구조] [5] 포인터, 연결리스트 (0)	2021.12.08

징구의 개발로그

[자료구조] [8] 트리

트리

-트리의 개념

이진 트리

- 이진트리의 분류

링크 표현법을 이용한 이진트리 구현

- 이진트리의 순회

- 연산들

'코딩테스트 및 개인공부 > 자료구조' 카테고리의 다른 글

티스토리툴바

[자료구조] [8] 트리

트리

-트리의 개념

이진 트리

- 이진트리의 분류

링크 표현법을 이용한 이진트리 구현

- 이진트리의 순회

- 연산들

'코딩테스트 및 개인공부 > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바