[자료구조] C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9-1

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

프로그래밍 프로젝트

1) 9.2절에서 이진 탐색 트리의 탐색 연산을 트리 클래스에서 구현했고 노드 클래스에서도 구현해 보았다. 트리의 각 노드들을 모두 자신을 루트로 하는 서브트리를 대표한다고 보면 많은 트리의 연산들을 노드에서 구현할 수 있다. 8장의 프로그램 8.1과 프로그램 8.2를 수정하여 BinaryTree 클래스에서 구현했던 다음 멤버함수들을 BinaryNode 클래스에서 구현해라.

 

void BinaryNode::inorder();

void BinaryNode::preorder();

void BinaryNode::postorder();

int BinaryNode::getCount();

int BinaryNode::getHeight();

int BinaryNode::getLeafCount();

 

2) BinaryTree를 상속하여 구현한 이진 탐색 트리 BinSrchTree의 삽입과 탐색 연산도 노드 class에서 다시 구현하고 이를 호출하는 다음 함수를 수정하라.

 

BinaryNode* BinSrchTree::search(int key); => 이거만 아직 미해결...

void BinSrchTree::insert(BinaryNode* n);

 

BinaryNode.h

#pragma once
#include <iostream>
#include <cstdio>

class BinaryNode {
protected:
	char data;
	BinaryNode* left;
	BinaryNode* right;
public:
	BinaryNode(int val = 0, BinaryNode* l = nullptr, BinaryNode* r = nullptr)
		: data(val), left(l), right(r) {}
	void setData(char val) { data = val; }
	void setLeft(BinaryNode* l) { left = l; }
	void setRight(BinaryNode* r) { right = r; }
	char getData() { return data; }
	BinaryNode* getLeft() { return left; }
	BinaryNode* getRight() { return right; }
	bool isEmpty() { return this == nullptr; }
	bool isLeaf() { return left == nullptr && right == nullptr; }

	void inorder();
	void inorder(BinaryNode* node);
	void preorder();
	void preorder(BinaryNode* node);
	void postorder();
	void postorder(BinaryNode* node);
	int getCount() { return isEmpty() ? 0 : getCount(this); }
	int getCount(BinaryNode* node);
	int getHeight() { return isEmpty() ? 0 : getHeight(this); }
	int getHeight(BinaryNode* node);
	int getLeafCount() { return isEmpty() ? 0 : getLeafCount(this); }
	int getLeafCount(BinaryNode* node);

	BinaryNode* searchRecur(BinaryNode* node, char key);
	void insertRecur(BinaryNode* r, BinaryNode* n);
};

void BinaryNode::inorder()
{
	inorder(this);
}

void BinaryNode::inorder(BinaryNode* node)
{
	if (node != nullptr) {
		inorder(node->getLeft());
		std::cout << node->getData() << " ";
		inorder(node->getRight());
	}
}

void BinaryNode::preorder()
{
	preorder(this);
}

void BinaryNode::preorder(BinaryNode* node)
{
	if (node != nullptr) {
		std::cout << node->getData() << " ";
		preorder(node->getLeft());
		preorder(node->getRight());
	}
}

void BinaryNode::postorder()
{
	inorder(this);
}

void BinaryNode::postorder(BinaryNode* node)
{
	if (node != nullptr) {
		postorder(node->getLeft());
		postorder(node->getRight());
		std::cout << node->getData() << " ";
	}
}

int BinaryNode::getCount(BinaryNode* node)
{
	if (node == nullptr) return 0;
	return 1 + getCount(node->getLeft()) + getCount(node->getRight());
}

int BinaryNode::getHeight(BinaryNode* node)
{
	if (node == nullptr) return 0;
	int lefth = node->getHeight(node->getLeft());
	int righth = node->getHeight(node->getRight());
	return (lefth > righth) ? lefth + 1 : righth + 1;
}

int BinaryNode::getLeafCount(BinaryNode* node)
{
	if (node == nullptr) return 0;
	if (node->isLeaf()) return 1;
	else return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
}

BinaryNode* BinaryNode::searchRecur(BinaryNode* node, char key)
{
	if (node == nullptr) return NULL;
	if (key == this->getData()) return this;
	else if (key < this->getData())
		return searchRecur(this->getLeft(), key);
	else
		return searchRecur(this->getRight(), key);

}

void BinaryNode::insertRecur(BinaryNode* r, BinaryNode* n)
{
	if (n->getData() == r->getData()) return;
	else if (n->getData() < r->getData()) {
		if (r->getLeft() == nullptr)
			r->setLeft(n);
		else
			insertRecur(r->getLeft(), n);
	}
	else {
		if (r->getRight() == nullptr)
			r->setRight(n);
		else
			insertRecur(r->getRight(), n);
	}
}

 

BinaryTree.h

#pragma once
#include <queue>
#include "BinaryNode.h"

using namespace std;

class BinaryTree {
protected:
	BinaryNode* root;
public:
	BinaryTree() : root(nullptr) {}
	void setRoot(BinaryNode* node) { root = node; }
	BinaryNode* getRoot() { return root; }
	bool isEmpty() { return root == nullptr; }
	void levelorder();
};

void BinaryTree::levelorder()
{
	cout << endl << "levelorder: ";
	if (!isEmpty())
	{
		queue<BinaryNode*> q;
		q.push(root);

		while (!q.empty())
		{
			BinaryNode* temp = q.front();
			q.pop();

			if (temp != nullptr)
			{
				std::cout << "[" << temp->getData() << "] ";
				q.push(temp->getLeft());
				q.push(temp->getRight());
			}
		}
	}
	cout << endl;
}

 

BinSrchTree.h

#pragma once
#include "BinaryTree.h"
#include "BinaryNode.h"

class BinSrchTree : public BinaryTree {
public:
	BinSrchTree(void) {}
	~BinSrchTree(void) {}

	BinaryNode* search(const char& key);
	void insert(BinaryNode* n);
};

BinaryNode* BinSrchTree::search(const char& key)
{
	BinaryNode temp;
	BinaryNode* tp;
	tp = temp.searchRecur(root, key);

	if (tp != nullptr)
		std::cout << "탐색 성공 : 키값이 " << tp->getData() << "인 노드" << tp << std::endl;
	else
		std::cout << "탐색 실패 !" << std::endl;
	return tp;
}

void BinSrchTree::insert(BinaryNode* n)
{
	if (n == nullptr) return;
	if (isEmpty()) root = n;
	else {
		BinaryNode temp;
		temp.insertRecur(this->getRoot(), n);
	}
}

 

main.cpp

#include "BinSrcTree.h"

using namespace std;

int main()
{
    BinaryTree tree;

    BinaryNode* d = new BinaryNode('D', nullptr, nullptr);
    BinaryNode* e = new BinaryNode('E', nullptr, nullptr);
    BinaryNode* b = new BinaryNode('B', d, e);
    BinaryNode* f = new BinaryNode('F', nullptr, nullptr);
    BinaryNode* c = new BinaryNode('C', f, nullptr);
    BinaryNode* a = new BinaryNode('A', b, d);
    tree.setRoot(a);

    cout << "inorder() : ";
    b->inorder();
    cout << endl;
    cout << "preorder() : ";
    b->preorder();
    cout << endl;
    cout << "postorder() : ";
    b->postorder();
    cout << endl;

    cout << "getCount() : " << b->getCount() << endl;
    cout << "getHeight : " << b->getHeight() << endl;
    cout << "getLeafCount() : " << b->getLeafCount() << endl;

    BinSrchTree SrchTree;
    SrchTree.insert(new BinaryNode('A'));
    SrchTree.insert(new BinaryNode('B'));
    SrchTree.insert(new BinaryNode('G'));
    SrchTree.insert(new BinaryNode('H'));
    SrchTree.insert(new BinaryNode('E'));

    SrchTree.levelorder();

    //SrchTree.search('E');


    return 0;
}

 

실행결과는 다음과 같다.

search 함수가 계속 탐색 실패라고 나오는데... 추측으로는 temp라는 임시 node를 만든후 이걸 탐색하려고 드니 내부에 노드들이 없어서 탐색 오류가 나는 것 같다. 이를 수정하기 위해서는 외부에서 만들어진 SrchTree의 주소를 받아서 탐색해야하는데 흠... 뭔가 잘 안된다...