[C++] 11주차 과제7

이원탐색트리를 구현한다.  

• 임의의 정수 리스트를 입력받아 이원탐색트리에 저장한다.
• 이원탐색트리는 연결리스트를 사용하여 구현한다.
• 이원탐색트리를 중위순회하여 정렬된 순서로 출력한다.

입력물: 정수리스트

출력물: 입력한 정수리스트의 정렬된 결과 (출력 결과물).

 

* 프로그램 내용 외에 다른 내용이 출력된다면 감점이 될 수 있으니 유의바람.

 

과제7-BST

 

과제7 확인필수

Code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <string.h>

#define N 1000

using namespace std;

template <typename T> class Tree;  // 전방선언
template <typename T>
class TreeNode {
	friend class Tree<T>;
private:
	T data;
	TreeNode<T>* leftChild;
	TreeNode<T>* rightChild;
public:
	TreeNode(T data);
};

template <typename T>
class Tree {
public:
	Tree() : root(NULL) { };
	TreeNode<T>* Get(TreeNode<T>* node);
	void InsertNode(TreeNode<T>* node);
	void Visit(TreeNode<T>* currentNode);
	void Inorder(TreeNode<T>* currentNode);  // 중위순회
	void Inorder() { Inorder(root); };
private:
	TreeNode<T>* root;
};

template <typename T>
TreeNode<T>::TreeNode(T data)
{
	this->data = data;
	this->leftChild = NULL;
	this->rightChild = NULL;
}

template <typename T>
TreeNode<T>* Tree<T>::Get(TreeNode<T>* node)  // 반복적 탐색
{
	TreeNode<T>* currentNode = root;
	while (currentNode) {
		if (node->data < currentNode->data)
			currentNode = currentNode->leftChild;
		else if (node->data > currentNode->data)
			currentNode = currentNode->rightChild;
		else return currentNode;
	}
	return 0;  // 노드가 없는 경우
}

template <typename T>
void Tree<T>::InsertNode(TreeNode<T>* node)
{
	// 탐색결과 이 노드가 존재하지 않을때
	if (!Get(node)) {
		TreeNode<T>* parent = NULL;
		TreeNode<T>* current = root;
		while (current) {
			parent = current;
			if (node->data < parent->data) current = current->leftChild;
			else current = current->rightChild;
		}
		if (parent) {
			// 탐색 실패하면 탐색 끝난 지점에 노드 삽입
			if (node->data < parent->data) parent->leftChild = node;
			else parent->rightChild = node;
		}
		else root = new TreeNode<T>(node->data);
	}
}

template <typename T>
void Tree<T>::Visit(TreeNode<T>* currentNode)
{
	cout << currentNode->data << " ";
}

template <typename T>
void Tree<T>::Inorder(TreeNode<T>* currentNode)
{
	if (currentNode) {
		Inorder(currentNode->leftChild);
		Visit(currentNode);
		Inorder(currentNode->rightChild);
	}
}

int main()
{
	while (1) {
		string input;
		getline(cin, input);
		if (input == ".") break;
		
		int num_arr[N];
		int str_cnt = 0;
		char* str_buff = new char[N];
		strcpy(str_buff, input.c_str());
		char* tok = strtok(str_buff, " ");
		
		Tree<int> tree;
		while (tok != nullptr) {
			num_arr[str_cnt++] = atoi(tok);
			tok = strtok(nullptr, " ");
		}

		int i = 0;
		while (i < str_cnt) {
			tree.InsertNode(new TreeNode<int>(num_arr[i]));
			i++;
		}

		tree.Inorder();
		cout << "\n" << endl;
	}
}

실행결과

 

점수 10/10

 

 

  ❤와 댓글은 큰 힘이 됩니다. 감사합니다 :-)