[BinaryTree.h]
/*
이진트리 클래스의 구현
연산 추가
(1) 이진트리가 완전 이진트리인지를 검사하는 연산
(2) 임의의 node의 레벨을 구하는 연산을 구현한다, 만약 node가 트리 안에 있지 않으면 0을 반환한다.
(3) 이진트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이의 차이가 2보다 작으면 이 트리를 균형잡혀있다라고 한다.
현재 이진트리가 균형 잡혀 있는지를 검사하는 다음 연산을 구현한다.
(4) 이진트리에서 경로의 길이를 루트에서부터 모든 자식 노드까지의 경로의 길이의 합이라고 하자. 경로의 길이를 구하는 연산을 구현한다
(5) 이진트리를 좌우로 대칭시키는 연산을 구현한다
*/
#include "TreeCircularQueue.h"
class BinaryTree
{
private:
BinaryNode *root;
bool reverse(BinaryNode *node)
{
if (node == NULL)
return false;
else
{
//재귀
reverse(node->getLeft());
reverse(node->getRight());
//leftNode와 rightNode를 서로 바꾼다
BinaryNode *temp = node->getLeft();
node->setLeft(node->getRight());
node->setRight(temp);
}
return true;
}
bool isBalanced(BinaryNode *node)
{
int leftHeight;
int rightHeight;
if (node == NULL)
return true;
leftHeight = getHeight(node->getLeft());
rightHeight = getHeight(node->getRight());
//왼쪽 서브트리와 오른쪽서브트리의 높이차가 2이상 나지 않고 둘 다 균형이 잡혀있을 경우 참
if ((leftHeight - rightHeight) <= 1 && (leftHeight - rightHeight) >= -1 && isBalanced(node->getLeft()) && isBalanced(node->getRight()))
return true;
return false;
}
int level(BinaryNode *node1, BinaryNode *node2, int lev = 1) //node2가 우리가 찾고자 하는 node
{
if (node1 == NULL)
return 0;
if (node1 == node2)
return lev;
if (node1->getLeft() == NULL && node1->getRight() == NULL)
return 0;
//재귀
int left = level(node1->getLeft(), node2, lev + 1); //왼쪽으로
int right = level(node1->getRight(), node2, lev + 1); //오른쪽으로
if (!left) //왼쪽 노드가 존재하지 않는다면
return right; //오른쪽 노드 반환
else //반대
return left;
}
void inorder(BinaryNode *node)
{
if (node != NULL)
{
if (node->getLeft() != NULL)
inorder(node->getLeft());
cout << "[" << (char)node->getData() << "] ";
if (node->getRight() != NULL)
inorder(node->getRight());
}
}
void preorder(BinaryNode *node)
{
if (node != NULL)
{
cout << "[" << (char)node->getData() << "] ";
if (node->getLeft() != NULL)
preorder(node->getLeft());
if (node->getRight() != NULL)
preorder(node->getRight());
}
}
void postorder(BinaryNode *node)
{
if (node != NULL)
{
if (node->getLeft() != NULL)
postorder(node->getLeft());
if (node->getRight() != NULL)
postorder(node->getRight());
cout << "[" << (char)node->getData() << "] ";
}
}
int getCount(BinaryNode *node)
{
if (node == NULL)
return 0;
return 1 + getCount(node->getLeft()) + getCount(node->getRight());
}
int getHeight(BinaryNode *node)
{
if (node == NULL)
return 0;
int hLeft = getHeight(node->getLeft());
int hRight = getHeight(node->getRight());
return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
}
int getLeafCount(BinaryNode *node)
{
if (node == NULL)
return 0;
if (node->isLeaf())
return 1;
else
return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
}
int evaluate(BinaryNode *node)
{
if (node == NULL)
return 0;
if (node->isLeaf())
return node->getData();
else
{
int op1 = evaluate(node->getLeft());
int op2 = evaluate(node->getRight());
switch (node->getData())
{
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1*op2;
case '/':
return op1 / op2;
}
return 0;
}
}
//순환 호출에 의해 node를 루트로 하는 트리의 전체 용량 계산 함수
int calcSize(BinaryNode *node)
{
if (node == NULL)
return 0;
return node->getData() + calcSize(node->getLeft()) + calcSize(node->getRight());
}
public:
BinaryTree() :root(NULL)
{
}
void setRoot(BinaryNode *node)
{
root = node;
}
BinaryNode *getRoot()
{
return root;
}
bool isEmpty()
{
return root == NULL;
}
bool isFull() //이진트리가 완전 이진트리인지 검사하는 함수
{
if (!isEmpty())
{
CircularQueue q;
q.enqueue(root);
while (!q.isEmpty())
{
BinaryNode *n = q.dequeue();
//말단노드가 아니고 왼쪽 오른쪽 자식 중 하나라도 없으면 완전이진트리 X
if (!(n->isLeaf()) && n->getLeft() == NULL && n->getRight() != NULL)
return false;
else if (!(n->isLeaf()) && n->getLeft() != NULL && n->getRight() == NULL)
return false;
if (n != NULL)
{
if(n->getLeft())
q.enqueue(n->getLeft());
if(n->getRight())
q.enqueue(n->getRight());
}
}
return true;
}
}
bool isBalanced() //균형이 잡혀있는가?
{
return isBalanced(root);
}
//뒤바꾼다
bool reverse()
{
return reverse(root);
}
void inorder()
{
cout << endl << "inorder: ";
inorder(root);
}
void preorder()
{
cout << endl << "preorder: ";
preorder(root);
}
void postorder()
{
cout << endl << "postorder: ";
postorder(root);
}
void levelorder()
{
cout << endl << "levelorder: ";
if (!isEmpty())
{
CircularQueue q;
q.enqueue(root);
while (!q.isEmpty())
{
BinaryNode *n = q.dequeue();
if (n != NULL)
{
cout << "[" << (char)n->getData() << "] ";
q.enqueue(n->getLeft());
q.enqueue(n->getRight());
}
}
}
cout << endl;
}
int getCount()
{
return isEmpty() ? 0 : getCount(root);
}
int getHeight()
{
return isEmpty() ? 0 : getHeight(root);
}
int getLeafCount()
{
return isEmpty() ? 0 : getLeafCount(root);
}
int evaluate()
{
return evaluate(root);
}
//디렉터리 용량 계산 함수
int calcSize()
{
return calcSize(root);
}
//레벨을 구하는 연산
int level(BinaryNode *node)
{
return level(root, node);
}
//경로의 길이
int pathLength()
{
int sum = 0;
if (!isEmpty())
{
CircularQueue q;
q.enqueue(root);
while (!q.isEmpty())
{
BinaryNode *n = q.dequeue();
sum += level(n) - 1; //각 노드의 레벨-1만큼 더하면 총 경로
if (n != NULL)
{
if(n->getLeft())
q.enqueue(n->getLeft());
if(n->getRight())
q.enqueue(n->getRight());
}
}
}
return sum;
}
};
[BinaryNode.h]
/*
이진트리 노드 클래스의 구현
*/
#include <iostream>
using namespace std;
class BinaryNode
{
protected:
int data;
BinaryNode *left;
BinaryNode *right;
public:
BinaryNode(int val = 0, BinaryNode *l = NULL, BinaryNode *r = NULL) :data(val), left(l), right(r)
{
}
void setData(int val)
{
data = val;
}
void setLeft(BinaryNode *l)
{
left = l;
}
void setRight(BinaryNode *r)
{
right = r;
}
int getData()
{
return data;
}
BinaryNode *getLeft()
{
return left;
}
BinaryNode *getRight()
{
return right;
}
bool isLeaf()
{
return left == NULL && right == NULL;
}
};
[TreeCircularQueue.h]
/*
레벨 순회 프로그램
*/
#include "BinaryNode.h"
#include <iostream>
using namespace std;
inline void error(char *str)
{
fprintf(stderr, "%s\n", str);
exit(1);
}
#define MAX_QUEUE_SIZE 100
class CircularQueue
{
int front;
int rear;
BinaryNode *data[MAX_QUEUE_SIZE];
public:
CircularQueue()
{
front = rear = 0;
}
bool isEmpty()
{
return front == rear;
}
bool isFull()
{
return (rear + 1) % MAX_QUEUE_SIZE == front;
}
void enqueue(BinaryNode *n)
{
if (isFull())
error("Error:큐가 포화상태입니다\n");
else
{
rear = (rear + 1) % MAX_QUEUE_SIZE;
data[rear] = n;
}
}
BinaryNode *dequeue()
{
if (isEmpty())
error("Error: 큐가 공백상태입니다\n");
else
{
front = (front + 1) % MAX_QUEUE_SIZE;
return data[front];
}
}
};
[BinaryTree.cpp]
/*
이진트리 테스트 프로그램
*/
#include "BinaryTree.h"
int main(void)
{
BinaryTree tree, tree2, tree3;
BinaryNode *d = new BinaryNode('D', NULL, NULL);
BinaryNode *e = new BinaryNode('E', NULL, NULL);
BinaryNode *b = new BinaryNode('B', d, e);
BinaryNode *f = new BinaryNode('F', NULL, NULL);
BinaryNode *c = new BinaryNode('C', f, NULL);
BinaryNode *a = new BinaryNode('A', b, c);
tree.setRoot(a);
tree.inorder();
tree.preorder();
tree.postorder();
tree.levelorder();
if (tree.isFull())
cout << "tree는 완전 이진트리이다" << endl;
else
cout << "tree는 완전 이진트리가 아니다" << endl;
cout << "d의 레벨은 " << tree.level(d) << endl;
if (tree.isBalanced())
cout << "tree는 균형이 잡혀있다" << endl;
else
cout << "tree는 균형이 잡혀있지 않다" << endl;
cout << "총 경로의 길이: " << tree.pathLength() << endl;
if (tree.reverse())
cout << endl << "tree reverse 완료" << endl;
else
cout << endl << "tree reverse 실패" << endl;
tree.inorder();
cout << endl;
/*
cout << "노드의 개수= " << tree.getCount() << endl;
cout << "단말의 개수= " << tree.getLeafCount() << endl;
cout << "트리의 높이= " << tree.getHeight() << endl;
BinaryNode *n1 = new BinaryNode(3, NULL, NULL);
BinaryNode *n2 = new BinaryNode(2, NULL, NULL);
BinaryNode *n3 = new BinaryNode('*',n1, n2);
BinaryNode *n4 = new BinaryNode(5, NULL, NULL);
BinaryNode *n5 = new BinaryNode(6, NULL, NULL);
BinaryNode *n6 = new BinaryNode('-', n4, n5);
BinaryNode *n7 = new BinaryNode('+', n3, n6);
tree2.setRoot(n7);
cout << "계산 결과= " << tree2.evaluate() << endl;
BinaryNode *m4 = new BinaryNode(200, NULL, NULL);
BinaryNode *m5 = new BinaryNode(500, NULL, NULL);
BinaryNode *m3 = new BinaryNode(100, m4, m5);
BinaryNode *m2 = new BinaryNode(50, NULL, NULL);
BinaryNode *m1 = new BinaryNode(0, m2, m3);
tree3.setRoot(m1);
cout << "디렉터리 용량 계산 결과 = " << tree3.calcSize() << endl;
*/
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
[참고] C++로 쉽게 풀어쓴 자료구조
*시험기간이라 개인적인 공부를 할 시간이 제한되어 요즘 자주 업로드를 못하고 있습니다...
'C++ > C++로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9 (2) (0) | 2017.11.01 |
|---|---|
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9 (1) (0) | 2017.10.31 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 7 (13) | 2017.10.07 |
| C++로 쉽게 풀어쓴 자료구조 7장 연습문제 (0) | 2017.10.07 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 6 (4) | 2017.10.04 |