/ C

자료구조 정복하기 with C++ (7)Tree 트리

자료구조 정복하기 with C++ (7)Tree 트리

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.

Tree 트리

트리는 하나 이상의 노드로 이루어진 유한집합으로 다음과 같이 표현하는 자료구조입니다.

Tree 용어

  • 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  • 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
  • 내부(internal) 노드: 단말 노드가 아닌 노드
  • 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
  • 형제(sibling): 같은 부모를 가지는 노드
  • 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
  • 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
  • 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
  • 트리의 차수(degree of tree): 트리의 최대 차수
  • 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

Tree 트리 기능

트리에 있는 노드를 순회 하는 방법에는 3가지가 있습니다.

  • LVR: 중위(Inorder) 순회 => 왼쪽 이동 -> 노드가 없으면 출력 -> 오른쪽 이동
  • VLR: 전위(Preorder) 순회 => 출력 -> 왼쪽 이동 -> 오른쪽 이동
  • LRV: 후위(Preorder) 순회 => 왼쪽 이동 -> 오른쪽 이동 -> 출력

트리의 기능은 다음과 같습니다.

  1. 노드 삽입
  2. 방문 노드 출력
  3. 중위, 전위, 후위 순회 후 출력
  4. 트리 복사
  5. 트리 비교(== operator 이용)

Tree

Tree.h

Tree의 헤더파일

#pragma once
#include <iostream>
#include <stddef.h>

using namespace std;
template <class T> class Tree;

template <class T>
class TreeNode
{
    friend class Tree<T>;

public:
    TreeNode();
    TreeNode(T data, TreeNode<T>* leftChild, TreeNode<T>* rightChild);
private:
    T data;
    TreeNode<T>* leftChild;
    TreeNode<T>* rightChild;
};

template <class T>
class Tree {
public:
    Tree();
    Tree(const Tree<T>& s);							//트리 생성자
    void Visit(TreeNode<T>* t);						//방문 노드 출력
    void Insert(T data);							//노드 삽입
    void Inorder();									//중위 순회
    void Inorder(TreeNode<T>* currentNode);
    void Preorder();								//전위 순회
    void Preorder(TreeNode<T>* currentNode);
    void Postorder();								//후위 순회
    void Postorder(TreeNode<T>* currentNode);
    TreeNode<T>* Copy(TreeNode<T>* origNode);		//트리 복사
    bool Equal(TreeNode<T>* a, TreeNode<T>* b);		//트리 비교
    bool operator== (const Tree& t) const;			//비교 연산자 재정의
private:
    TreeNode<T>* root;
};

Tree.cpp

Tree 소스코드

#include "Tree.h"
#include <iostream>

using namespace std;

template <class T>
TreeNode<T>::TreeNode() {
    this->data = 0;
    this->leftChild = NULL;
    this->rightChild = NULL;
}

template <class T>
TreeNode<T>::TreeNode(T data, TreeNode<T>* leftChild, TreeNode<T>* rightChild) {
    this->data = data;
    this->leftChild = leftChild;
    this->rightChild = rightChild;
}


template <class T>
Tree<T>::Tree() {
    root = new TreeNode<T>();
}


template <class T>
Tree<T>::Tree(const Tree<T>& s) {
    root = Copy(s.root);
}

template <class T>
void Tree<T>::Visit(TreeNode<T>* t) {
    cout << t->data << " ";
}


template <class T>
void Tree<T>::Insert(T data) {
    TreeNode<T>* node = new TreeNode<T>();
    node = root;

    while (node->leftChild != NULL) {
        node = node->leftChild;
    }
    if (node->data == 0) {
        node->data = data;
        return;
    }

    if (node->leftChild == NULL) {
        node->leftChild = new TreeNode<T>();
        node->leftChild->data = data;
    } else {
        node->rightChild = new TreeNode<T>();
        node->rightChild->data = data;
    }
}


template <class T>
void Tree<T>::Inorder() {
    Inorder(root);
}

template <class T>
void Tree<T>::Inorder(TreeNode<T>* currentNode) {
    if (currentNode) {
        Inorder(currentNode->leftChild);
        Visit(currentNode);
        Inorder(currentNode->rightChild);
    }
}

template <class T>
void Tree<T>::Preorder() {
    Preorder(root);
}

template <class T>
void Tree<T>::Preorder(TreeNode<T>* currentNode) {
    if (currentNode) {
        Visit(currentNode);
        Preorder(currentNode->leftChild);
        Preorder(currentNode->rightChild);
    }
}


template <class T>
void Tree<T>::Postorder() {
    Postorder(root);
}

template <class T>
void Tree<T>::Postorder(TreeNode<T>* currentNode) {
    if (currentNode) {
        Postorder(currentNode->leftChild);
        Postorder(currentNode->rightChild);
        Visit(currentNode);
    }
}

template <class T>
TreeNode<T>* Tree<T>::Copy(TreeNode<T>* origNode)
{
    if (!origNode) return 0;
    return new TreeNode<T>(origNode->data, Copy(origNode->leftChild), Copy(origNode->rightChild));
}

template <class T>
bool Tree<T>::Equal(TreeNode<T>* a, TreeNode<T>* b)
{// Workhorse.
    if ((!a) && (!b)) return true;  // both a and b are 0
    return (a && b                // both a and b are non-zero
        && (a->data == b->data)  // data is the same
        && Equal(a->leftChild, b->leftChild) // left subtrees equal
        && Equal(a->rightChild, b->rightChild)); // right subtrees equal
}

template <class T>
bool Tree<T>::operator== (const Tree& t) const {
    return Equal(root, t.root);
}

결과

main.cpp

#include "Tree.h"
#include <iostream>

using namespace std;

int main() {
	Tree<char> tree;
	Tree<char>* ptree = &tree;

	tree.Insert('+');
	tree.Insert('E');
	tree.Insert('*');
	tree.Insert('D');
	tree.Insert('*');
	tree.Insert('C');
	tree.Insert('*');
	tree.Insert('/');
	tree.Insert('B');
	tree.Insert('A');

	//Inorder
	tree.Inorder();
	cout << endl;
	cout << endl;

	//Preorder
	tree.Preorder();
	cout << endl;
	cout << endl;

	//Postorder
	tree.Postorder();
	cout << endl;
	cout << endl;

	//Copy
	Tree<char> copy(tree);
	Tree<char>* newTree = &copy;
	//Inorder 확인
	copy.Inorder();
	cout << endl;
	cout << endl;

	//트리 == 오퍼레이터
	(!(ptree == newTree)) ? cout << "두개의 트리가 같다 " << endl : 
		cout << "두개의 트리가 다르다. " << endl;
	
	return 0;
}

트리 자료구조를 구현했습니다. 결과가 잘 나옵니다!