C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 8

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

프로그래밍 프로젝트

(1) 이진트리가 완전 이진트리인지를 검사하는 연산

 

(2) 임의의 node의 레벨을 구하는 연산을 구현한다, 만약 node가 트리 안에 있지 않으면 0을 반환한다.

 

(3) 이진트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이의 차이가 2보다 작으면 이 트리를 균형잡혀있다라고 한다. 현재 이진트리가 균형 잡혀 있는지를 검사하는 다음 연산을 구현한다.

 

(4) 이진트리에서 경로의 길이를 루트에서부터 모든 자식 노드까지의 경로의 길이의 합이라고 하자. 경로의 길이를 구하는 연산을 구현한다

 

(5) 이진트리를 좌우로 대칭시키는 연산을 구현한다

 

(6) 현재 트리와 that 트리가 같은 노드를 가지지 않으면 두 트리는 분리되어(disjoint) 있다. 이를 판단하는 연산을 순환을 이용하여 구현하라. => 아직 미해결...

 

 

BinaryNode.h

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

class BinaryNode {
protected:
	int data;
	BinaryNode* left;
	BinaryNode* right;
public:
	BinaryNode(int val = 0, BinaryNode* l = nullptr, BinaryNode* r = nullptr)
		: 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 == nullptr && right == nullptr; }
	bool isFullNode() {
		if (left != nullptr && right != nullptr)
			return true;
		else
			return false;
	}
};

 

 

BinaryTree.h

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

using namespace std;

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

	int getHeight() { return isEmpty() ? 0 : getHeight(root); }
	int getHeight(BinaryNode* node);

	int levelUtil(BinaryNode* node, int data, int level);
	int level(BinaryNode* node);

	bool isBlanced() { return isEmpty() ? false : isBlanced(root); }
	bool isBlanced(BinaryNode* node);

	int pathLength();

	bool reverse() { return isEmpty() ? false : reverse(root); }
	bool reverse(BinaryNode* node);
};

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)
			{
				cout << "[" << (char)temp->getData() << "] ";
				q.push(temp->getLeft());
				q.push(temp->getRight());
			}
		}
	}
	cout << endl;
}

bool BinaryTree::isFull()
{
	if (root == nullptr) return true;

	queue<BinaryNode*> q;
	q.push(root);

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

		if (!temp->isFullNode()) // 만약 fullnode가 아닐경우
		{  // left가 비었는데 right가 있다면 오류
			if (temp->getLeft() == nullptr && temp->getRight() != nullptr)
				return false;
			else { // left만 있는경우는 추가
				if (temp->getLeft() != nullptr)
				{
					q.push(temp->getLeft());
				}
			}
		}
		else { // fullnode인 경우
			q.push(temp->getLeft());
			q.push(temp->getRight());
		}
	}
    return true;
}

int BinaryTree::levelUtil(BinaryNode* node, int data, int level)
{
	if (node == nullptr) return 0;
	if (node->getData() == data) return level;
	// 왼쪽노드부터 먼저 모두 검사
	int downlevel = levelUtil(node->getLeft(), data, level + 1);
	if (downlevel != 0) 
		return downlevel;

	downlevel = levelUtil(node->getRight(), data, level + 1);
	return downlevel;
}

int BinaryTree::level(BinaryNode* node)
{
	int target = node->getData();
	return BinaryTree::levelUtil(root, target, 1);
}

bool BinaryTree::isBlanced(BinaryNode* node)
{
	int lh = 0, rh = 0;
	if (node == nullptr)
		return true;

	lh = getHeight(node->getLeft());
	rh = getHeight(node->getRight());
	if (abs(lh - rh) < 2 && isBlanced(node->getLeft()) && isBlanced(node->getRight()))
		return true;

	return false;
}

int BinaryTree::pathLength()
{
	int total = 0;

	if (!isEmpty())
	{
		queue<BinaryNode*> q;
		q.push(root);

		while (!q.empty())
		{
			BinaryNode* temp = q.front();
			q.pop();
			
			if (temp != nullptr)
			{
				total += level(temp) - 1;
				if(temp->getLeft())
					q.push(temp->getLeft());
				if (temp->getRight())
					q.push(temp->getRight());
			}
		}
	}
	return total;
}

bool BinaryTree::reverse(BinaryNode* node)
{
	if (node == nullptr) return false;
	else {
		reverse(node->getLeft());
		reverse(node->getRight());
		BinaryNode* temp = node->getLeft();
		node->setLeft(node->getRight());
		node->setRight(temp);
	}
	return true;
}

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

 

 

main.cpp

#include <iostream>
#include "BinaryTree.h"
using namespace std;

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

    cout << "완전-이진트리 인가? : " << boolalpha << tree.isFull() << endl;
    cout << "d의 level은? : "<< tree.level(d) << endl;
    cout << "균형 잡혀있는가? : " << boolalpha << tree.isBlanced() << endl;
    cout << "경로 길이는? : " << tree.pathLength() << endl;
    tree.levelorder();
    tree.reverse();
    tree.levelorder();
    return 0;
}

 

결과는 다음과 같다.

#자료구조, #쉽게풀어쓴자료구조, #생능출판, #프로그래밍프로젝트, #자료구조론, #씨쁠쁠, #CPP, #코딩, #컴퓨터공학, #이즌트리, #완전이진트리, #binary, #binarytree