Tree 자료구조

tree를 만드는 자료구조와 몇가지 구현 문제를 풀어보려고 한다. 현재도 푸는 중이라 글이 계속해서 올라올 것이다.

 

우선 노드를 표현하는 클래스가 필요하다. 현업에선 data가 int인 경우가 없다고 보면 된다고 하는데, 교육을 위해서 

편의상 int타입을 쓴다고 하셨다.

#include <cstdio>
#pragma once
class BinaryNode {
protected:
	int data;
	BinaryNode* left;
	BinaryNode* rigth;
public:
	BinaryNode(int val = 0, BinaryNode* l = NULL, BinaryNode* r = NULL)
		:data(val), left(l), rigth(r) {}//생성자//
        //셋팅함수//
	void setData(int val) { data = val; }
	void setLeft(BinaryNode* l) { left = l; }
	void setRihgt(BinaryNode* r) { rigth = r; }
    //
       //값을 보내주는 함수//
	int getData() { return data; }
	BinaryNode* getLeft() { return left; }
	BinaryNode* getRight() { return rigth; }
    //
       //단말노드(자식노드를 가지고 있지 않은 노드)인지 확인//
	bool isLeaf() { return left == NULL && rigth == NULL; }
};

이 다음은 Tree를 그리기 위한 클래스가 필요하다.

코드가 길기 때문에 소분해서 올리겠다.

#include "BinaryNode.h"//노드를 표현한 클래스를 include//
#include "f://linker/CircluarQueue.h"
//level순환 기능을 위해 원형큐를 기능하는 클래스도 include했다.//

class BinaryTree {
	BinaryNode* root;//노드클래스 호출//
    
    public:
	BinaryTree() :root(NULL) {}
	void setRoot(BinaryNode* node) { root = node; }//루트노드를 셋팅//
	BinaryNode* getRoot() { return root; }//영어그대로 보면 해석되는 그런 함수//
	bool isEmpty() { return root == NULL; }//트리가 비어있는지 확인하는 함수//

이 이후에 나오는 코드를 보기 위해 알아야 하는 것은 트리의 순회에 대해 현재 노드를 V라 하고 L(왼쪽), R(오른쪽)이라고 칭한다는 것이다. 명칭들이 참...

 

 

 

 

 

 

 

 

그리고 양쪽 자식노드를 방문할때는 왼쪽에서 오른쪽으로 방문 한다는 것과 순회의 명칭은 현재 노드를 기준으로 탐색 순서가 어떻게 되느냐에 따라 달라진 다는 것을 알면 이해가 쉽다.

 

inorder traversal(중위 순회): LVR

void inorder() { printf("\n   inorder: "); inorder(root); }//중위 순회//
	void inorder(BinaryNode* node) {
		if (node != NULL) {//노드가 NULL(Tree의 끝)일때 까지 순환호출
			inorder(node->getLeft());//L//
			printf(" [%c] ", node->getData());//V//
			inorder(node->getRight());//R//
		}
	}

preorder traversal(전위 순회): VLR        "그 프리오더 아닙니다. 지갑넣어 두십쇼."

void preorder() { printf("\n  preorder: "); preorder(root); }//전위순회(그 프리오더 아님)//
	void preorder(BinaryNode* node) {
		if (node != NULL) {
			printf(" [%c] ", node->getData());//V//
			preorder(node->getLeft());//L//
			preorder(node->getRight());//R//
		}
	}

postorder traversal(후위 순회): LRV      "post에 ick를 붙이면 포스틱이다. 맛있겠다."

void postorder() { printf("\n postorder: "); postorder(root); }//후위 순회//
	void postorder(BinaryNode* node) {
		if (node != NULL) {
			postorder(node->getLeft());//L//
			postorder(node->getRight());//R//
			printf(" [%c] ", node->getData());//V//
		}
	}

여기까지가 표준적인 순회 방법이다. 이 다음은 level order라는 것을 볼 것인데 원형큐가 필요하다.

 

#include<cstdio>
#include <cstdlib>
#define MAX_QUEUE_SIZE 100
inline void error(const char* message) {
	printf("%s\n", message);
	exit(1);
}

class CircluarQueue {
protected:
	int front;
	int rear;
	BinaryNode* data[MAX_QUEUE_SIZE] = { 0 };
public:
	CircluarQueue() { front = rear = 0; }
	bool isEmpty() { return front == rear; }
	bool isFull() { return (rear + 1) % MAX_QUEUE_SIZE == front; }
	void enqueue(BinaryNode* val) {
		if (isFull()) {
			error("error: queue is full");
		}
		else {
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
	}
	BinaryNode* dequeue() {
		if (isEmpty()) {
			error("error: queue is empty");
		}
		front = (front + 1) % MAX_QUEUE_SIZE;
		return data[front];
	}
	/*BinaryNode* peek() {
		if (isEmpty()) {
			error("error: queue is empty");
		}
		else return data[(front + 1) % MAX_QUEUE_SIZE];
	}*/
	/*void display() {
		printf("큐 내용 : ");
		int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
		for (int i = front + 1; i <= maxi; i++) {
			printf("[%2d] ", data[i % MAX_QUEUE_SIZE]);
		}
		printf("\n");
	}*/ //이 코드에선 쓰지 않기 때문에 함수기능을 꺼두었다.//
};

여기선 Tree에 대해 설명하기 때문에 원형큐는 코드만 올려둔다. 어휴 여러분 그냥 STL쓰세요 어휴,,,

 

level order(레벨 순회): 루트노드를 1레벨이라 하고 그 밑으로 갈 수록 레벨이 올라간다. 

꼭대기 부터 하나씩 내려오며 탐색하는 거라 하면 이해가 쉬울 것이다.

	void levelorder() {
		printf("\nlevelorder: ");
		if (!isEmpty()) {
			CircluarQueue q;
			q.enqueue(root);//처음엔 루트노드를 큐에 넣는다//
			while (!q.isEmpty())//큐가 공백이 될때 까지//
			{
				BinaryNode* n = q.dequeue();
				if (n != NULL) {
					printf(" [%c] ", n->getData());
					q.enqueue(n->getLeft());
					q.enqueue(n->getRight());
				}
			}//데이터를 꺼내고, LR순서로 데이터를 큐에 넣는다.//
			printf("\n");
		}
	}

이 다음은 이진트리 연산이다. 순환호출을 주로 이용하는데, 앞으로 나올 형태 (같은 이름을 쓰지만 매개변수로 구분하는 것)의 함수들은 c++배울때 몇번 봐서 아는 사이였는데, 이렇게 쓰이는 것을 보니 내가 생각한거보다 아주 강력한 것이었단걸 알았다.

int getCount() { return isEmpty() ? 0 : getCount(root); }//노드의 개수를 구하는 함수//
int getCount(BinaryNode* node) {
		if (node == NULL)return 0;
		return 1 + getCount(node->getLeft())
			+getCount(node->getRight());
	}//순환호출을 하며 값이 있으면 1씩 더한다. 없으면 0을 더한다.//

int getHeight() { return isEmpty() ? 0 : getHeight(root); }//트리의 높이를 구하는 함수//
	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;
	}//순환호출을 각각마치고 더 큰 값을 retrun.//

int getLeafCount() { return isEmpty() ? 0 : getLeafCount(root); }//단말노드 개수를 구하는 함수//
	int getLeafCount(BinaryNode* node) {
		if (node == NULL)return 0;
		if (node->isLeaf())return 1;
		else return getLeafCount(node->getLeft())
			+ getLeafCount(node->getRight());
	}//단말노드이면 1씩 더하며 순환호출하고 모두 더해진 값을 retrun.//

이 이후론 구현문제 풀이이다. 그것들은 따로 작성해서 올리겠다.