#include <iostream>

#ifndef NODE_H

#define NODE_H

class Node

{

private:

/*

* Node* left: 왼쪽 자식노드

* Node* right: 오른쪽 자식노드

* Node* queueLink: 트리의 마지막으로 추가된 노드를 담고있는 노드이며 큐의 형태로 저쟝되어있다

* Node* parent: 부모노드를 가리키고있는 노드이다

* int root: 노드가 루트노드인지 아닌지 확인하기위한 변수이다

* int data: 노드의 데이터를 저장하고있는 변수이다

*/

Node* left;

Node* right;

Node* queueLink;

bool isRoot;

int data;

public:

Node(int key);

bool getRoot();

void setRoot(bool flag);

void setQueueLink(Node* node);

Node* getQueueLink();

int getData();

void setData(int key);

void setLeft(Node* node);

void setRight(Node* node);

Node* getLeft();

Node* getRight();

};

#endif

#include "Node.h"

using namespace std;

Node::Node(int key) :data{ key } {

}

bool Node::getRoot() {

return isRoot;

}

void Node::setRoot(bool flag) {

isRoot = flag;

}

/*

 * 큐 노드 설정

 */

void Node::setQueueLink(Node* node) {

queueLink = node;

}

/*

 * 큐 노드 불러오기

 */

Node* Node::getQueueLink() {

return queueLink;

}

/*

 * 데이터 불러오기

 */

int Node::getData() {

return data;

}

/*

 * 데이터 설정

 */

void Node::setData(int key) {

data = key;

}

/*

 * 왼쪽 차일드 노드 설정

 */

void Node::setLeft(Node* node) {

left = node;

}

/*

 * 오른쪽 차일드 노드 설정

 */

void Node::setRight(Node* node) {

right = node;

}

/*

 * 왼쪽 차일드 노드 불러오기

 */

Node* Node::getLeft() {

return left;

}

/*

 * 오른쪽 차일드 노드 불러오기

 */

Node* Node::getRight() {

return right;

}

#include <vector>

#include "Node.h"

using namespace std;

#ifndef BINARY_TREE_H

#define BINARY_TREE_H

class BinaryTree

{

public:

Node* getParentNode(vector<Node*>& queue, int data);

void LevelOder(vector<Node*>& q, vector<Node*>& sq, Node* node);

void insertNode(vector<Node*>& queue, vector<Node*>& sq, Node* root, int data);

void remove(vector<Node*> queue, Node* node);

void preorder(Node* curr);

void inorder(Node* curr);

void postorder(Node* curr);

private:

};

#endif

#include <iostream>

#include <vector>

#include "BinaryTree.h"

#include "Node.h"

#include "Heap.h"

using namespace std;

/*

 * 부모노드를 불러오는 함수

 * 레벨오더를 통해 찾아서 불러온다

 */

Node* BinaryTree::getParentNode(vector<Node*>& queue, int data) {

int flag = 0;

for (int i = 0; i < queue.size(); i++) {

if (queue[i]->getLeft()->getData() == data) {

++flag;

return queue[i];

}

else if (queue[i]->getRight()->getData() == data) {

return queue[i];

}

}

if (flag == 0) {

return NULL;

}

}

/*

 * 추가

 * 새로운 노드와 queue의 마지막 노드를 삽입하기위한 포인터 노드를 생성하고 루트노드와 data를 받아서 큐를 이용해 추가한다

 * 추가하는 과정은 큐를 이용해 트리의 마지막 노드를 찾고 삽입한다

 */

void BinaryTree::insertNode(vector<Node*>& queue, vector<Node*>& sq, Node* root, int data) {

/*

* 새로운 노드 newNode 를 생성하고 초기화 해준다

*/

Node* newNode = new Node(NULL);

newNode->setData(data);

newNode->setLeft(NULL);

newNode->setRight(NULL);

newNode->setQueueLink(NULL);

Heap* he = new Heap();

if (queue.size() == NULL) {

root->setData(data);

queue.push_back(root);

sq.push_back(root);

}

else {

LevelOder(queue, sq, newNode);

if (queue[0]->getRight() == NULL) {

if (queue[0]->getLeft() == NULL) {

queue[0]->setLeft(newNode);

he->sort(sq, newNode);

}

else {

queue[0]->setRight(newNode);

he->sort(sq, newNode);

}

}

}

}

 /*

  * 레벨 오더 추가

  */

void BinaryTree::LevelOder(vector<Node*>& q, vector<Node*>& sq, Node* newNode) {

q.push_back(newNode);

sq.push_back(newNode);

if (q[0]->getRight() != NULL) {

q.erase(q.begin());

}

}

/*

 * 제거

 */

void BinaryTree::remove(vector<Node*> queue, Node* node) {

if (node->getLeft() != NULL || node->getRight() != NULL) {

cout << "can't remove! it has chlid" << endl;

}

else {

Node* p = getParentNode(queue, node->getData());

int data = node->getData();

if (p->getLeft()->getData() == data) {

p->setLeft(NULL);

}

else {

p->setRight(NULL);

}

}

}

/*

 * 전위 순회

 */

void BinaryTree::preorder(Node* curr) {

if (curr->getRoot()) {

cout << curr->getData();

}

if (curr->getLeft() != NULL) {

cout << "( " << curr->getLeft()->getData();

preorder(curr->getLeft());

if (curr->getRight() != NULL) {

cout << ", " << curr->getRight()->getData();

preorder(curr->getRight());

}

cout << ")";

}

}

/*

 * 중위 순회

 */

void BinaryTree::inorder(Node* curr) {

if (curr != NULL) {

inorder(curr->getLeft());

cout << curr->getData() << " ";

inorder(curr->getRight());

}

}

/*

 * 후위 순회

 */

void BinaryTree::postorder(Node* curr) {

if (curr != NULL) {

postorder(curr->getLeft());

postorder(curr->getRight());

cout << curr->getData() << " ";

}

}

#include <iostream>

#include "Node.h"

#include "BinaryTree.h"

#ifndef HEAP

#define HEAP

class Heap

{

public:

void sort(vector<Node*>& queue, Node* node);

void swap(Node* x, Node* y);

void HeapSort(vector<Node*>& queue, vector<Node*>& sq, Node* root, vector<int>& list);

};

#endif

#include <iostream>

#include <vector>

#include "Heap.h"

#include "Node.h"

#include "BinaryTree.h"

using namespace std;

/*

 * 정렬

 * 트리에 추가된 노드들을 max heap으로 만든다

 * 재귀함수를 이용해 만듬

 */

void Heap::sort(vector<Node*>& queue, Node* node) {

BinaryTree* bi = new BinaryTree();

if (bi->getParentNode(queue, node->getData()) != NULL) {

Node* parent = bi->getParentNode(queue, node->getData());

if (parent->getRoot() == true) {

if (parent->getData() < node->getData()) {

swap(parent, node);

return;

}

}

else {

if (parent->getData() < node->getData()) {

swap(parent, node);

sort(queue, parent);

}

else {

return;

}

}

}

else {

return;

}

}

/*

 * 교환

 * 두 노드의 값을 바꿈

 */

void Heap::swap(Node* x, Node* y) {

int temp = x->getData();

x->setData(y->getData());

y->setData(temp);

}

/*

 * 힙 정렬

 * list를 max Heap으로 만든 트리에 담고 다시 Level Oder를 list에 담음

 * 위 과정을 list의 길이만큼 반복

 */

void Heap::HeapSort(vector<Node*>& queue, vector<Node*>& sq, Node* root, vector<int>& list) {

for (int i = 0; i < list.size(); i++) {

BinaryTree* BT = new BinaryTree();

for (int j = 0; j < list.size() - i; j++) {

BT->insertNode(queue, sq, root, list[j]);

}

int k = 0;

for (k = 0; k < sq.size(); k++) {

list[k] = sq[k]->getData();

}

int temp = list[0];

list[0] = list[k - 1];

list[k - 1] = temp;

queue.clear();

queue.reserve(0);

sq.clear();

sq.reserve(0);

}

}

#include <vector>

#include <iostream>

#include "Node.h"

#include "BinaryTree.h"

#include "Heap.h"

using namespace std;

int main()

{

/*

* 정렬할 배열 선언

*/

vector<int> exlist = { 4,2,6,7,1 };

/*

*LevelOrder 에 사용할 벡터 선언

*/

vector<Node*> queue;

vector<Node*> SavedQueue;

/*

* 사용할 class선언

*/

Node* root = new Node(NULL);

Heap* h = new Heap();

BinaryTree* b = new BinaryTree();

/*

* 루트노드로 설정

*/

root->setRoot(true);

/*

* 힙 적용

*/

h->HeapSort(queue, SavedQueue, root, exlist);

cout << "Heap Sort" << endl;

/*

* 정렬된 배열 출력

*/

for (int i = 0; i < exlist.size(); i++) {

cout << exlist[i] << ", ";

}

}