220415~220418_자료구조_이진트리(Binary Tree) 실행

* 이진트리 구현

https://hyrule.tistory.com/57

220415~220418_자료구조_이진트리(Binary Tree) 구현

 

//main.cpp

#include "BinaryTree.h"
#include <time.h>


//순회 출력을 위한 함수(이진 트리 클래스에서 주소를 받아서 사용할 예정)
void OutputOrder(const int& Key, const int& Value, const int& ParentKey, const int& LeftKey, const int& RightKey)
{
	std::cout << "*Key: " << Key << " \t*Value: " << Value << " \t*ParentKey: " << ParentKey << " \tLeftKey: " << LeftKey << " \t*RightKey: " << RightKey << std::endl;
}



int main()
{

	//랜덤으로 값을 삽입하고, 정렬되어 저장하는지 확인해보자.
	srand((unsigned int)time(0));
	rand();



	//이진트리 작동 여부 테스트
	CBinaryTree<int, int> Tree;

	for (int i = 0; i < 10; ++i)
	{
		int rnd = rand();
		Tree.insert(rnd, rnd);
	}
	

	CBinaryTreeIterator<int, int> iter;
	CBinaryTreeIterator<int, int> iterEnd = Tree.end();

	for (iter = Tree.begin();iter != iterEnd; ++iter)
	{
		std::cout << iter->m_Key << std::endl;
	}
	std::cout << "* Size: " << Tree.getsize() << std::endl;
	////////////////////////////////////////////



	//순회기능 및 규칙에 맞게 잘 들어가는지 테스트.
	CBinaryTree<int, int>	tree;

	//사용자가 원하는 값을 골라 삽입 가능하게 함.
	int find = 1;
	while (true)
	{
		std::cout << "\n* 추가할 값을 입력하세요.(0 = 삽입 종료.)\n>>> ";
		std::cin >> find;
		iter = tree.Find(find);
		if (find == 0)
			break;
		//중복되는 키값이 없을 경우 삽입해준다.
		if (iter == tree.end())
			tree.insert(find, find);
		else
		{
			std::cout << "* 중복된 키값이 있어 삽입할 수 없습니다." << std::endl;
		}
			
	}
	////////////////////////////////////////////////////

	//임의의 값 삽입.
	//tree.insert(7, 7);
	//tree.insert(4, 4);
	//tree.insert(3, 3);
	//tree.insert(6, 6);
	//tree.insert(10, 10);
	//tree.insert(8, 8);

	std::cout << "\n* 리스트 형태 출력" << std::endl;
	iterEnd = tree.end();
	for (iter = tree.begin(); iter != iterEnd; ++iter)
	{
		std::cout << iter->m_Key << std::endl;
	}
	std::cout << "* Tree Size: " << tree.getsize() << std::endl;
	
	std::cout << "\n* 전위순회" << std::endl;
	tree.PreOrder(OutputOrder);

	std::cout << "\n* 중위순회" << std::endl;
	tree.InOrder(OutputOrder);
	
	std::cout << "\n* 후위순회" << std::endl;
	tree.PostOrder(OutputOrder);
	////////////////////////////////////////////



	//Find 함수 테스트
	find = 1;
	while (true)
	{
		std::cout << "\n* Find 함수 테스트 - 찾고싶은 키 값을 입력하세요.(0을 입력하면 종료)\n>>> ";
		std::cin >> find;
		iter = tree.Find(find);
		if (find == 0)
			break;

		if (iter != tree.end())
			std::cout << "* 찾는 " << find << "번 Key 값에 해당하는 Value: " << *iter << std::endl;
		else
			std::cout << "* 찾는 " << find << "번 Key 값이 존재하지 않습니다." << std::endl;
	}
	////////////////////////////////////////////////////

	system("cls");

	//Erase 기능 테스트.
	//임의의 값 삽입.
	/*tree.clear();
	tree.insert(7, 7);
	tree.insert(4, 4);
	tree.insert(3, 3);

	tree.insert(6, 6);
	tree.insert(10, 10);
	tree.insert(8, 8);*/

	//삭제 전 전방순회
	std::cout << "\n< 삭제 전 >" << std::endl;
	tree.PreOrder(OutputOrder);

	find = 1;
	while (true)
	{
		std::cout << "\n* Find 함수 테스트 - 삭제할 키 값을 입력하세요.(0을 입력하면 종료)\n>>> ";
		std::cin >> find;
		if (find == 0)
			break;


		iter = tree.erase(find);
		if (iter == tree.end())
		{
			if (tree.getsize() != 0)
				std::cout << "* 삭제 실패." << std::endl;
			else
				std::cout << "* 더이상 삭제할 값이 없습니다." << std::endl;

			std::cout << "\n* Size: " << tree.getsize() << std::endl;
		}
		else
		{ 
			std::cout << "< 삭제 결과 > " << std::endl;
			tree.PreOrder(OutputOrder);

			std::cout << "< 리스트로 보기 >\n* ";
			iterEnd = tree.end();
			for (iter = tree.begin(); iter != iterEnd; ++iter)
			{
				std::cout << *iter << "\t";
			}
			std::cout << "\n* Size: " << tree.getsize() << std::endl;

		}
			
	}


	return 0;
}

 

 

rand() 함수를 통해 이진 트리에 삽입한 값들이 잘 정렬되서 들어가고 있다.

 

 

 

삽입

 

 

 

전위순회, 중위순회, 후위순회

 

 

 

값 탐색

 

 

 

값 제거