[자료구조] C++로 쉽게 풀어쓴 자료구조 : 8장, 트리

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 8장. 트리

대부분의 교제에서 가르치는 트리중 대표가 아마 이진트리 일 것 이다. 이진트리의 정의를 간략히 살펴보자!

1) 공집합이거나

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

정의 8.1 299페이지

Binary Tree 의 ADT

데이터: 노드와 간선의 집합. 노드는 공집합이거나 공집합이 아니라면 루트노드와 양쪽 서브트리로 구성된다. 모든 서브트리는 이진트리여야 한다.

 

연산:

- create(): 이진트리를 생성한다.

- isEmpty(): 이진트리가 공백 상태인지 확인한다.

- getRoot(): 이진트리의 루트 노드를 반환.

- getCount(): 이진트리의 노드의 수를 반환.

- getHeight(): 이진트리의 높이를 반환

- insertNode(n): 이진트리에 노드 n을 삽입.

- deleteNode(n): 이진트리에서 노드 n을 삭제한다.

- display(): 이진트리의 내용을 화면에 출력

 

이진트리 노드 class구현, 교제와 다르게 template화 적용

 

BinaryNode.h

#pragma once
#include <cstdio>

template <typename T>
class BinaryNode {
protected:
	T _data;
	BinaryNode<T>* _left;
	BinaryNode<T>* _right;
public:
	BinaryNode(T val = 0, BinaryNode<T>* l = nullptr, BinaryNode<T>* r = nullptr)
		: _data(val), _left(l), _right(r) {}
	void setData(T val) { _data = val; }
	void setLeft(BinaryNode<T>* l) { _left = l; }
	void setRight(BinaryNode<T>* r) { _left = r; }
	T getData() { return _data; }
	BinaryNode<T>* getLeft() { return _left; }
	BinaryNode<T>* getRight() { return _right; }
	bool isLeaf() { return _left == nullptr && _right == nullptr; }
};

 

 

BinaryTree.h

#pragma once
#include "BinaryNode.h"

template <typename U>
class BinaryTree {
	BinaryNode<U>* _root;
public:
	BinaryTree(): _root(nullptr) {}
	void setRoot(BinaryNode* node) { root = node; }
	BinaryNode<U>* getRoot() { return _root; }
	bool isEmpty() { return root == nullptr; }

	void inorder(); // 아직 미구현
	void preorder();
	void postorder();
	void levelorder();

	int getCount();
	int getHeight();
	int getLeafCount();
};

 

이진트리 순회 방법

루트 방문을 V, 왼쪽 서브트리 방문을 L, 오른쪽 서브트리 방문을 R이라고 하면 다음과 같은 3가지 방법이 있다. 의사코드를 통하여 확인해보자.

 

- 전위 순회(preorder traveral): VLR

preorder(x)

if x ≠ NULL
    then print DATA(X);
         preorder(LEFT(x));
         preorder(RIGHT(x));

 

- 중위 순회(inorder traveral): LVR

inorder(x)

if x ≠ NULL
    then preorder(LEFT(x));
         print DATA(x);
         preorder(RIGHT(x));

 

- 후위 순회(postorder traversal): LRV

postorder(x)

if x ≠ NULL
    then preorder(LEFT(x));
         preorder(RIGHT(x));
         print DATA(x);

 

이를 활용하여 위의 BinaryTree.h를 완성시켜보자.

#pragma once
#include "BinaryNode.h"

template <typename U>
class BinaryTree {
	BinaryNode<U>* _root;
public:
	BinaryTree(): _root(nullptr) {}
	void setRoot(BinaryNode<U>* node) { _root = node; }
	BinaryNode<U>* getRoot() { return _root; }
	bool isEmpty() { return _root == nullptr; }

	void inorder(BinaryNode<U>* node);
	void inorder() { std::cout << "\ninorder: "; inorder(_root); }
	
	void preorder(BinaryNode<U>* node);
	void preorder() { std::cout << "\npreorder: "; preorder(_root); }
	
	void postorder(BinaryNode<U>* node);
	void postorder() { std::cout << "\npostorder: "; postorder(_root); }

	void levelorder();

	int getCount();
	int getHeight();
	int getLeafCount();
};

template <typename U>
void BinaryTree<U>::inorder(BinaryNode<U>* node)
{
	if (node != nullptr) {
		inorder(node->getLeft());
		std::cout << node->getData() << " ";
		inorder(node->getRight());
	}
}

template <typename U>
void BinaryTree<U>::preorder(BinaryNode<U>* node)
{
	if (node != nullptr) {
		std::cout << node->getData() << " ";
		preorder(node->getLeft());
		preorder(node->getRight());
	}
}

template <typename U>
void BinaryTree<U>::postorder(BinaryNode<U>* node) 
{
	if (node != nullptr) {
		postorder(node->getLeft());
		postorder(node->getRight());
		std::cout << node->getData() << " ";
	}
}

 

main.cpp

#include <iostream>
#include "BinaryTree.h"
using namespace std;

int main()
{
    BinaryTree<char> tree;
    BinaryNode<char>* d = new BinaryNode<char>('D', nullptr, nullptr);
    BinaryNode<char>* e = new BinaryNode<char>('E', nullptr, nullptr);
    BinaryNode<char>* b = new BinaryNode<char>('B', d, e);
    BinaryNode<char>* f = new BinaryNode<char>('F', nullptr, nullptr);
    BinaryNode<char>* c = new BinaryNode<char>('C', f, nullptr);
    BinaryNode<char>* a = new BinaryNode<char>('A', b, c);
    tree.setRoot(a);

    tree.inorder();
    tree.preorder();
    tree.postorder();
    
    cout << endl;

    return 0;
}

 

결과는 다음과 같다.

노도 클래스에서 순회를 구현할수도 있다. 실제 중위 순회를 tree class가 아닌 node class 내부에 멤버함수로 구현할수 있다.

template <typename T>
void BinaryNode<T>::inorder() {
	if (_left != nullptr) _left->inorder();
	std::cout << _data << " ";
	if (_right != nullptr) _right->inorder();
}

 

이를 사용하면 노드는 자신을 기준으로 순회연산을 처리할수 있다. 트리에서는 이와같이 노드 클래스에서 처리할 수 있는 연산이 많은데, 이는 모든 노드를 그 노드를 root로 하는 하나의 트리로 생각할 수 있기 때문이다.

 

따라서 더이상 tree class에서 inorder 함수는 필요가 없고, 인터페이스함수만 남기면 된다. 인터페이스 inorder함수는 수정되야 한다.

	void inorder() { 
		std::cout << "\ninorder: "; 
		if (!isEmpty()) root->inorder();
	}

 

 

레벨 순회

레벨 순회는 각 노드를 레벨 순으로 검사하는 방식이다. 우선 level1 의 노드를 검사후 level1 그다음 leve2, level3... 이런 방식으로 순회한다. 앞의 3가지 순회는 순환을 사용하니 stack이 상요되었지만, 레벨 순회의 경우 queue를 사용한다.

Level_order()

initialize queue;
queue.enqueue(root);
while queue.isEmpty() ≠ TRUE do
    x <- queue.dequeue();
    if(x ≠ NULL) then
        print DATA(x);
        queue.enqueue(LEFT(x));
        queue.enqueue(RIGHT(x));

 

 

이진트리 노드 수 구하기

getCount(x)

if x = NULL
    then return 0;
    else return 1 + getCount(LEFT(x)) + getCount(RIGHT(x));

 

 

단말노드 수 구하기

getLeafCount(x)

if x = NULL then return 0;
if LEFT(x) = NULL and RIGHT(x) = NULL
    then return 1;
    else return getLeafCount(LEFT(x)) + getLeafCount(RIGHT(x));

 

 

높이 구하는 알고리즘

getHeight(x)

if x = NULL
    then return 0;
    else return 1 + max(getHeight(LEFT(x), getHeight(RIGHT(x));

 

 

수식 트리 계산 알고리즘

evaluate(exp)

if exp = NULL
    then return 0;
    else x<-evaluate(LEFT(x));
         y<-evaluate(RIGHT(x));
         op<-DATA(exp);
         return (x op y);

 

---

2) 나의 현황

◆ Effective C++을 주문하였다. 이책도 하루에 2단원 정도씩 정리해서 올려볼까? 란 생각과 동시에, 너무 유명한 책이라 이미 정리된 블로그 글들이 많은데 그냥 내용공부에 치중해야겠다는 생각이 동시에 든다. 일단 빨리 읽고싶다!