자료구조 Tree 구현체

README.Tree.md

Tree C++ 구현

파일 설명

• main.cpp : 메인 함수가 있는 파일
• Tree.h : 트리 클래스가 있는 파일
• Stack.h : 스택 클래스가 있는 파일
• ExpTree.h : ExpTree 네임스페이스 안 함수가 선언 되어있는 파일
• ExpTree.cpp : ExpTree.h의 구현체

참고 자료

• 윤성우의 열혈 자료구조 / 윤성우 / 오렌지미디어
• 다양한 예제로 학습하는 데이터 구조와 알고리즘 / 나라심하 카루만치 / 인사이트
• 트리의 시각적인 출력 | hongcho1818.tistory.com/8

ExpTree.cpp

//
// Created by Cheolbak on 2016. 5. 4..
//

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

// 관리의 편의성을 위해 namespace ExpTree 선언
namespace ExpTree {
	// 특수한 수식 트리를 만들기 위한 함수
	// 호출 할때 매개변수인 exp는 후위표기법을 사용해야 한다.
	// Example : ExpTree::makeExpTree("13+4/3*4-") << 중위 표기법은 (1 + 3) / 4 * 3 - 4 이다.
	Tree<int> * makeExpTree(std::string exp) {
		// int형 Tree 클래스의 포인터를 저장할 stack을 선언
		Stack<Tree<int>*> stack;

		// 참조 : http://stackoverflow.com/questions/9438209/for-every-character-in-string
		// C++11 에서 가능한 구문
		// for ( 배열참조 변수 : 배열이름 )
		for (char& c : exp) {
			Tree<int> * node = new Tree<int>();
			if (c >= '0' && c <= '9')
				node->setData(c);
			else {
				try {
					node->edgeRight(stack.pop());
					node->edgeLeft(stack.pop());
				}
				catch (const std::runtime_error& e) {
					std::cout << e.what() << std::endl;
				}
				node->setData(c);
			}
			stack.push(node);
		}
		return stack.pop();
	}

	// 수식 트리를 계산
	int evaluateExpTree(Tree<int> * tree) {
		// left와 right에 연결된 node가 없으면 literal로 처리
		if (tree->getLeft() == nullptr
			&& tree->getRight() == nullptr)
			return tree->getData() - '0';

		// 재귀 함수로 트리 계산
		int op1 = evaluateExpTree(tree->getLeft());
		int op2 = evaluateExpTree(tree->getRight());

		// 연산자 처리
		switch (tree->getData()) {
		case '+':
			return op1 + op2;
		case '-':
			return op1 - op2;
		case '*':
			return op1 * op2;
		case '/':
			// 0으로 나누기 예외
			if (op2 == 0)
				throw std::runtime_error("0으로 나눔");
			return op1 / op2;
		default:
			// + - / * 연산 할 수 없음
			throw std::runtime_error("연산자가 아닌 다른 값");
		}
	}

	int evalExpTreeNonRecursive(Tree<int> * node) {
		Stack<Tree<int>*> stack;
		std::string formula = "";
		while (true) {
			if (node != nullptr) {
				stack.push(node);
				node = node->getLeft();
			}
			else {
				if (stack.isEmpty()) {
					break;
				}
				else {
					if (stack.peek()->getRight() == nullptr) {
						node = stack.pop();
						formula += (char)node->getData();
						while (!stack.isEmpty() && node == stack.peek()->getRight()) {
							node = stack.pop();
							formula += (char)node->getData();
						}
					}
				}
				if (!stack.isEmpty())
					node = stack.peek()->getRight();
				else
					node = nullptr;
			}
		}

		Stack<int> evalStack;
		for (char& c : formula) {
			if (isdigit(c)) {
				evalStack.push(c - '0');
			}
			else {
				int op2 = evalStack.pop();
				int op1 = evalStack.pop();

				switch (c) {
				case '+':
					evalStack.push(op1 + op2);
					break;
				case '-':
					evalStack.push(op1 - op2);
					break;
				case '*':
					evalStack.push(op1 * op2);
					break;
				case '/':
					evalStack.push(op1 / op2);
					break;
				}
			}
		}
		return evalStack.pop();
	}

	// Tree 순회 함수 내에서 사용할 함수 포인터에 들어갈 함수
	void showNodeData(int data) {
		std::cout << (char)data << " ";
	}

	// 전위 표기법 출력
	void showPrefixExp(Tree<int> * tree) {
		Tree<int>::preorderTraverse(tree, showNodeData);
	}

	// 중위 표기법 출력
	// ( ) 출력을 위해 트리의 중위 순회를 응용하였음.
	void showInfixExp(Tree<int> * tree) {
		if (tree == nullptr)
			return;

		if (tree->getLeft() != nullptr
			|| tree->getRight() != nullptr)
			std::cout << "(";

		showInfixExp(tree->getLeft());
		if (tree->getData() >= '0'
			&& tree->getData() <= '9')
			std::cout << (char)tree->getData();
		else
			std::cout << " " << (char)tree->getData() << " ";
		showInfixExp(tree->getRight());

		if (tree->getLeft() != nullptr
			|| tree->getRight() != nullptr)
			std::cout << ")";
	}

	// 후위 표기법 출력
	void showPostfixExp(Tree<int> * tree) {
		Tree<int>::postorderTraverse(tree, showNodeData);
	}

	void visualShowTree(Tree<int> * root, Tree<int> * node) {
		if (node == nullptr)
			return;
		visualShowTree(root, node->getRight());
		int * nodeDepth = new int;
		*nodeDepth = 0;
		Tree<int>::getDepth(root, node, nodeDepth);
		for (int tap = 0; tap < (*nodeDepth); tap++)
			std::cout << '\t';
		std::cout << (char)node->getData() << std::endl;
		visualShowTree(root, node->getLeft());
	}
}

ExpTree.h

//
// Created by Cheolbak on 2016. 5. 3..
//

#ifndef TREE_EXPTREE_H
#define TREE_EXPTREE_H

#include "Tree.h"
#include "Stack.h"

namespace ExpTree {
	Tree<int> * makeExpTree(std::string exp);
	int evalExpTreeNonRecursive(Tree<int> * root);
	int evaluateExpTree(Tree<int> * tree);

	void showNodeData(int data);

	void showPrefixExp(Tree<int> * tree);
	void showInfixExp(Tree<int> * tree);
	void showPostfixExp(Tree<int> * tree);

	void visualShowTree(Tree<int> * root, Tree<int> * node);
}

#endif //TREE_EXPTREE_H

Main.cpp

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

using namespace std;

void expTreeView();
void treeView();

int main() {
	while (true) {
		char input;
		cout << endl << "1) 트리 예제" << endl;
		cout << "2) 수식 트리 예제" << endl;
		cout << "q) 종료" << endl;
		cout << ">> ";
		cin >> input;
		switch (input) {
		case '1':
			treeView();
			break;
		case '2':
			expTreeView();
			break;
		case 'q':
			return 0;
		default:
			continue;
		}
	}
}

void expTreeView() {
	string input;
	cout << "수식 입력: ";
	// 1 + 2 + 3 일 경우 12+3+ 으로 input
	cin >> input;
	cin.clear();
	auto root = ExpTree::makeExpTree(input);
	ExpTree::visualShowTree(root, root);
	cout << "Result: " << ExpTree::evalExpTreeNonRecursive(root) << endl;
	cout << "중위 표현: ";
	ExpTree::showInfixExp(root);
	cout << endl << "전위 표현: ";
	ExpTree::showPrefixExp(root);
	cout << endl << "후위 표현: ";
	ExpTree::showPostfixExp(root);
	cout << endl;
}


void showData(int data) {
	cout << data << " ";
}

void treeView() {
	Tree<int> * root = new Tree<int>(1);
	root->edgeLeft(new Tree<int>(2,
		new Tree<int>(4),
		new Tree<int>(5)));
	root->edgeRight(new Tree<int>(3,
		new Tree<int>(6),
		new Tree<int>(7,
			new Tree<int>(8),
			new Tree<int>(9))));
	cout << "중위 순회: ";
	Tree<int>::inorderNonRecursive(root, showData);
	cout << endl;
	cout << "전위 순회: ";
	Tree<int>::preorderNonRecursive(root, showData);
	cout << endl;
	cout << "후위 순회: ";
	Tree<int>::postorderNonRecursive(root, showData);
	cout << endl;
	Tree<int>::visualShowTree(root, root);
}

Stack.h

//
// Created by Cheolbak on 2016. 5. 3..
//

#ifndef TREE_STACK_H
#define TREE_STACK_H

#include <stdexcept>

// Stack 구현
// 템플릿이 사용되었으므로 선언은 Stack<int>와 같은 형태로 사용
template <typename Data>
class Stack {
private:
    // 연결 리스트 구조체
    struct Node {
        Data data;
        Node * next;
    };

    // 스택에 마지막에 들어온 데이터 주소를 저장할 변수
    Node * head;

public:
    // 생성자
    // head 포인터를 초기화
    Stack() {
        head = nullptr;
    }

    // boolean 형을 사용하여 head가 비어있는지 확인
    bool isEmpty() {
        return head == nullptr;
    }

    // Stack push 연산
    void push(Data data) {
        // 새 node를 만듦
        Node * node = new Node();

        node->data = data;
        // 현재 최상위의 주소를 next에 옮김
        node->next = head;

        // 새 node의 주소를 최상위에 저장
        head = node;
    }

    // Stack pop 연산
    Data pop() {
        // 비어있으면 예외를 던진다.
        // 밖에서는 try {} catch (const std::runtime_error& e) {}
        // 형태로 throw 된 것을 받아서 처리 해줘야 한다.
        if (isEmpty())
            throw std::runtime_error("스택이 비었음");

        // pop으로 리턴할 데이터를 가져옴
        Data returnData = head->data;
        // 메모리 반환할 node를 잠시 저장
        Node * deleteNode = head;

        // 최상위 데이터의 다음 데이터의 주소를 저장
        head = head->next;

        delete deleteNode;
        return returnData;
    }

    // 최상위 데이터가 무엇인지 확인
    Data peek() {
        if (isEmpty())
            throw std::runtime_error("스택이 비었음");
        return head->data;
    }
};

#endif //TREE_STACK_H

Tree.h

//
// Created by Cheolbak on 2016. 4. 30..
//

#ifndef TREE_TREE_H
#define TREE_TREE_H

// Tree 클래스 구현
// 구현된 트리는 이진트리 (Binary Tree)
// 템플릿 사용 후 .cpp 컴파일시 링킹이 안된다.
// 따라서 .h에 구현까지 한다.

#include "Stack.h"

// 템플릿 선언. Tree 클래스 사용시 Tree<type>으로 써야함
// Example : Tree<int> rootNode;
template <typename Data>
class Tree {
private:
	// 저장될 Data
	Data data;
	// 왼쪽, 오른쪽 Node Pointer
	Tree<Data> * left;
	Tree<Data> * right;
public:
	Tree() : Tree(0) { }

	Tree(Data data) : Tree(data, nullptr, nullptr) { }

	Tree(Data data, Tree<Data> * left, Tree<Data> * right) {
		// nullptr은 C++11에서의 NULL
		// NULL은 기본적으로 0이므로 int로 취급됨
		// nullptr은 말 그대로 0도 아닌 null이다.
		this->left = left;
		this->right = right;
		this->data = data;
	}

	// 데이터 삽입 및 가져오기
	Data getData() {
		return data;
	}

	void setData(Data data) {
		this->data = data;
	}

	// 이진 트리의 왼쪽, 오른쪽 Node 가져오기
	Tree<Data> * getLeft() {
		return left;
	}

	Tree<Data> * getRight() {
		return right;
	}

	// 이진 트리의 왼쪽, 오른쪽 Node 할당하기
	void edgeLeft(Tree<Data> *child) {
		// 만약에 left에 할당 되어있으면 지운 후 재할당
		if (left != nullptr)
			deleteTree(left);
		left = child;
	}

	void edgeRight(Tree<Data> *child) {
		// 만약에 right에 할당 되어있으면 지운 후 재할당
		if (right != nullptr)
			deleteTree(right);
		right = child;
	}

	// Function Pointer Type Alias
	// 트리 순회에 사용될 함수 작성시엔
	// void function(Type name) 으로 작성해야 함
	using Func = void(*)(Data);

	// 트리 순회 함수 (Static)
	// 재귀 함수로 구현됨
	// 중위(inorder) 순회 : 왼쪽 -> 부모 -> 오른쪽
	static void inorderTraverse(Tree<Data> * node, Func process) {
		if (node == nullptr)
			return;
		inorderTraverse(node->left, process);
		process(node->data);
		inorderTraverse(node->right, process);
	}

	// 재귀 함수를 사용하지 않은 중위 순회
	static void inorderNonRecursive(Tree<Data> * node, Func process) {
		Stack<Tree<Data>*> stack;
		while (true) {
			while (node != nullptr) {
				stack.push(node);
				node = node->getLeft();
			}
			if (stack.isEmpty())
				break;
			node = stack.pop();
			process(node->getData());
			node = node->getRight();
		}
	}

	// 전위(preorder) 순회 : 부모 -> 왼쪽 -> 오른쪽
	static void preorderTraverse(Tree<Data> * node, Func process) {
		if (node == nullptr)
			return;
		process(node->data);
		preorderTraverse(node->left, process);
		preorderTraverse(node->right, process);
	}

	// 재귀 함수를 사용하지 않은 전위 순회
	static void preorderNonRecursive(Tree<Data> * node, Func process) {
		Stack<Tree<Data>*> stack;
		while (true) {
			while (node != nullptr) {
				process(node->getData());
				stack.push(node);
				node = node->getLeft();
			}
			if (stack.isEmpty())
				break;
			node = stack.pop();
			node = node->getRight();
		}
	}

	// 후위(postorder) 순회 : 왼쪽 -> 오른쪽 -> 부모
	static void postorderTraverse(Tree<Data> * node, Func process) {
		if (node == nullptr)
			return;
		postorderTraverse(node->left, process);
		postorderTraverse(node->right, process);
		process(node->data);
	}

	// 재귀 함수를 사용하지 않은 후위 순회
	static void postorderNonRecursive(Tree<Data> * node, Func process) {
		Stack<Tree<Data>*> stack;
		while (true) {
			if (node != nullptr) {
				stack.push(node);
				node = node->getLeft();
			}
			else {
				if (stack.isEmpty())
					return;
				else {
					if (stack.peek()->getRight() == nullptr) {
						node = stack.pop();
						process(node->getData());
						while (!stack.isEmpty() && (node == stack.peek()->getRight())) {
							node = stack.pop();
							process(node->getData());
						}
					}
				}
				if (!stack.isEmpty())
					node = stack.peek()->getRight();
				else
					node = nullptr;
			}
		}
	}

	static bool getDepth(Tree<Data> *root, Tree<Data> *node, int *returnCount) {
		if (root == nullptr)
			return false;
		if (root->getLeft() == node || root->getRight() == node
			|| getDepth(root->getLeft(), node, returnCount) || getDepth(root->getRight(), node, returnCount)) {
			(*returnCount)++;
			return true;
		}
		return false;
	}

	static void visualShowTree(Tree<Data> * root, Tree<Data> * node) {
		if (node == nullptr)
			return;
		visualShowTree(root, node->getRight());
		int * nodeDepth = new int;
		*nodeDepth = 0;
		getDepth(root, node, nodeDepth);
		for (int tap = 0; tap < (*nodeDepth); tap++)
			std::cout << '\t';
		std::cout << node->getData() << std::endl;
		visualShowTree(root, node->getLeft());
	}

	// 트리 삭제 : 후위 순회
	static void deleteTree(Tree<Data> * node) {
		if (node == nullptr)
			return;
		deleteTree(node->left);
		deleteTree(node->right);
		delete node;
	}
};

#endif //TREE_TREE_H

Tree.md

Tree Structure(트리 구조)

• 트리는 계층적 관계를 표현하는 자료구조이다.

트리의 용어

• Node(노드) : 원소가 저장되어 있는 것.
  • Root Node(근노드, 뿌리노드) : 부모가 없는 노드. 최상위에 존재하는 노드.
  • Leaf Node, Terminal Node(잎노드, 단말노드) : 자식이 없는 노드.
  • Non-Terminal Node, Branch Node, Internal Node(간노드, 내부노드) : 잎 노드를 제외한 노드.
• Edge(가지, 간선) : 노드와 노드를 연결하는 선.
• Subtree : 트리에서 Root Node를 제거했을 때 생기는 트리.
• Forest(숲) : 분리된 부트리들의 모임.
• Degree(차수) : 노드의 서브트리의 수.
• Level : 트리 전체에 대한 노드의 위치. 주어진 깊이의 모든 노드의 모임.
• Depth(깊이) : Root로부터 그 노드까지의 경로의 길이.
• Height(높이) : 그 노드로부터 가장 깊은 노드까지의 경로의 길이.
• 트리의 깊이 = 트리의 높이
• Path(경로) : 어떤 노드로부터 그 노드까지의 연결된 모임.

트리의 관계

• Parent(부모) : 어떤 노드의 상위 노드.
• Child(자식) : 어떤 노드의 하위 노드.
• Sibling(형제) : 같은 레벨에 동일한 부모를 갖는 노드들의 모임.
• Ancestor(조상) : 어떤 노드의 부모 노드로 부터 뿌리 노드까지의 경로에 존재하는 노드.
• Descendant(자손) : 어떤 노드의 하위에 존재하는 모든 노드.

Binary Tree(이진 트리)

• 엄격한(Strict) 이진 트리 : 모든 노드가 두 개의 자식을 가지거나 자식이 없을 때.
• 포화(Full) 이진 트리 : 모든 노드가 두 개의 자식을 가지고 잎 노드가 같은 레벨에 있을 때.
• 완전(Complete) 이진 트리 : 노드가 위에서 아래로, 왼쪽에서 오른쪽의 순서대로 채워졌을 때.
• 경사진(Skewed) 이진 트리 : 노드가 한 쪽으로만 치우쳤을 때.

Binary Tree의 구현

Linear List(Array)를 이용한 구현

• Root Node를 1번 배열에 저장하고 자식노드를 각각 2번 3번 배열에 저장한다.
• 노드에 고유의 노드번호를 부여한다.

Linked List를 이용한 구현

• 이중 연결 리스트의 노드를 이용하여 구현한다.
• 왼쪽, 오른쪽 포인터에 자식들의 주소를 대입한다.

Binary Tree의 탐색

• 탐색 가능성은 6가지가 있다.

전위(Preorder) 탐색 (DLR)

• 부모 -> 왼쪽 -> 오른쪽 순 탐색

중위(Inorder) 탐색 (LDR)

• 왼쪽 -> 부모 -> 오른쪽 순 탐색

후위(Postorder) 탐색 (LRD)

• 왼쪽 -> 오른쪽 -> 부모 순 탐색