Node.h
|
#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 |
Node.cpp
|
#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; } |
BinaryTree.h
|
#include "Node.h"
#ifndef BINARY_TREE_H #define BINARY_TREE_H class BinaryTree { public: Node* getParentNode(Node* root, int data); void insertNode(Node* root, int data); void remove(Node* node, int data); void preorder(Node* curr); void inorder(Node* curr); void postorder(Node* curr); private: };
#endif |
BinaryTree.cpp
|
#include "BinaryTree.h" #include "Node.h" #include<iostream>
using namespace std;
/* * 부모노드를 불러오는 함수 * 재귀를 통해 찾아서 불러온다 */ Node* BinaryTree::getParentNode(Node* root, int data) { if (root->getLeft() == NULL && root->getRight() == NULL) return NULL;
if (root->getLeft()->getData() == data) {
return root; } else if (root->getRight()->getData() == data) {
return root; }
else { Node* temp1 = getParentNode(root->getLeft(), data); if (temp1 != NULL) { return temp1; } Node* temp2 = getParentNode(root->getRight(), data); if (temp2 != NULL) { return temp2; }
} }
/* * 추가 * 새로운 노드와 queue의 마지막 노드를 삽입하기위한 포인터 노드를 생성하고 루트노드와 data를 받아서 큐를 이용해 추가한다 * 추가하는 과정은 큐를 이용해 트리의 마지막 노드를 찾고 삽입한다 */ void BinaryTree::insertNode(Node* root, int data) { /* * 새로운 노드 newNode 를 생성하고 초기화 해준다 */ Node* newNode = new Node(NULL); newNode->setData(data); newNode->setLeft(NULL); newNode->setRight(NULL); newNode->setQueueLink(NULL); /* * 포인터 노드 p는 추가해야한 위치의 부모노드를 가지고있다 */ Node* p = root->getQueueLink();
if (root->getQueueLink() == NULL) { /* * 최초 root노드 삽입시 설정 */ root->setQueueLink(root); root->setData(data); } else { /* * p의 왼쪽 자식이 비어있는경우 newNode를 삽입한다 */ if (p->getLeft() == NULL) { p->setLeft(newNode);
/* * 최초 root 노드의 자식노들이 체워질때까지 root노드를 queueLink에 고정 */ if (root->getRight() == NULL) { root->setQueueLink(root); } /* * queue 삽입을 위한 포인터 이동 */ else { while (p->getQueueLink() != NULL) { p = p->getQueueLink(); } /* * queue에 삽입 */ p->setQueueLink(newNode); } } else { /* * 최초 root 노드의 자식노들이 체워질때까지 root노드를 queueLink에 고정 */ if (root->getRight() == NULL) {
root->setRight(newNode);
root->setQueueLink(p->getLeft()); root->getQueueLink()->setQueueLink(newNode); } /* * p의 왼쪽 자식이 비어있는경우 newNode를 삽입한다 */ else { p->setRight(newNode); /* * queue 삽입을 위한 포인터 이동 */ while (p->getQueueLink() != NULL) { p = p->getQueueLink(); } /* * queue에 삽입 */ p->setQueueLink(newNode); /* * 다음 번 삽입해야할 노드의 정보 변경 */ root->setQueueLink(root->getQueueLink()->getQueueLink()); } } } } /* * 제거 */ void BinaryTree::remove(Node* node, int data) { if (node->getLeft()->getData() == data) { if (node->getLeft()->getLeft() != NULL) { cout << "can't remove"; } else { free(node->getLeft()); node->setLeft(NULL); } } else if (node->getRight()->getData() == data) { if (node->getRight()->getLeft() != NULL) { cout << "can't remove"; } else { free(node->getRight()); node->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() << " "; } } |
BinaryTreeApp.cpp
|
#include <iostream> #include "Node.h" #include "BinaryTree.h"
using namespace std;
int main() { Node* root = new Node(NULL); /* * 루트노드로 설정 */ root->setRoot(true);
BinaryTree* h = new BinaryTree();
h->insertNode(root, 5);
h->insertNode(root, 6); h->insertNode(root, 3);
h->insertNode(root, 1); h->insertNode(root, 7);
h->insertNode(root, 2); h->insertNode(root, 8);
h->insertNode(root, 4);
h->preorder(root);
cout << endl;
h->postorder(root);
cout << endl;
h->inorder(root); } |
by 송현고등학교 3학년 김준석
이진 트리를 구현한 것이다. 설명은 주석으로 대체한다.