c++) 이진 탐색 트리

안녕하세요~ 

알고리즘 탐색 부분으로 넘어왔습니다.

알고리즘 게시판에서 이진 검색을 포스팅 했는데요

이건 트리 ADT를 이용하여 검색하는 코드를 작성하였습니다.

○ 코드 특징

- 중복을 허용하지 않음

- 이진 트리 형식

- 완전 이진트리는 아닙니다.

- 모듈화가 잘되어 있지 않습니다. (대충대충.. 멘붕상태로 함.. )

○ 코드

- BinaryTree.h

#pragma once
#include <iostream>

using namespace std;

class BinaryTree {
	BinaryTree *leftc;
	BinaryTree *rightc;
	int data;

public:
	BinaryTree();
	BinaryTree(int elem);

	void setChild(BinaryTree *child);
	int getData();
	BinaryTree *search(int key);

	friend ostream& operator<<(ostream &os, const BinaryTree &bt);
};

BinaryTree::BinaryTree()
{}

BinaryTree::BinaryTree(int elem)
	: data(elem),
	leftc(nullptr),
	rightc(nullptr)
{

}

void BinaryTree::setChild(BinaryTree *child) {
	if (data == child->getData()) return;

	if (child->getData() > this->data) {
		if (rightc == nullptr) {
			this->rightc = child;
		}
		else {
			rightc->setChild(child);
		}
	}
	else {
		if (leftc == nullptr) {
			this->leftc = child;
		}
		else {
			leftc->setChild(child);
		}
	}
}

int BinaryTree::getData() {
	return data;
}

BinaryTree *BinaryTree::search(int key) {
	if (key == data) return this;

	BinaryTree *tmp;
	if (key < data) {
		tmp = leftc;
	}
	else {
		tmp = rightc;
	}

	if (tmp == nullptr) return nullptr;
	tmp->search(key);
}

ostream& operator<<(ostream &os, const BinaryTree &bt) {
	if (bt.leftc != nullptr) {
		os << *(bt.leftc);
	}
	os << bt.data << " ";
	if (bt.rightc != nullptr) {
		cout << *(bt.rightc);
	}

	return os;
}

- main.cpp

#include <ctime>
#include <cstdlib>
#include "BinaryTree.h"

using namespace std;

#define NUM 2000

int main() {
	srand((unsigned int)time(nullptr));
	
	// 루트 노드
	BinaryTree root((int)(rand() % 1000) + 1);

	for (int i = 1; i < NUM; ++i) {
		
		int tmp = (int)(rand() % 1000) + 1;

		BinaryTree *now = new BinaryTree(tmp);
		root.setChild(now);

	}

	cout << root << endl;


	BinaryTree *t;
	cout << endl << "looking for value : 13" << endl;
	t = root.search(13);
	if (t == nullptr) cout << "No Such Key" << endl;
	else cout << "find value : " << t->getData() << endl;

	cout << endl << "looking for value : 223" << endl;
	t = root.search(223);
	if (t == nullptr) cout << "No Such Key" << endl;
	else cout << "find value : " << t->getData() << endl;

	cout << endl << "looking for value : 987" << endl;
	t = root.search(987);
	if (t == nullptr) cout << "No Such Key" << endl;
	else cout << "find value : " << t->getData() << endl;

	return 0;
}

○ 실행 화면

이번에는 주석을 별로 안달았네요..

그래도 간단한 코드니까 ㅎㅎ...

저는 어려운 문법 잘 못씁니다 ㅎㅎ ㅜㅜ

공부하려고 일부러 작성해보며 했지만...

여러분 set 구조를 쓰면 자동으로 다 됩니다.. ㅎㅎ

stl 열심히 숙달합시다!