220419_자료구조_자가균형트리_AVL트리(AVL Tree) 실행

* AVL트리 구현

https://hyrule.tistory.com/59

220419_자료구조_자가균형트리_AVL트리(AVL Tree) 구현

 

 

* 실행 코드는 이진트리 실행 코드를 가져옴.

https://hyrule.tistory.com/58

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

 

//main.cpp

#include "BinaryAVLTree.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()
{


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

	for (int i = 0; i < 10; ++i)
	{
		//1~11까지 순차적으로 삽입 -> 무조건 편향트리가 나온다.
		//균형이 맞춰진 상태로 삽입되어있으면 성공.
		Tree.insert(i + 1, i + 1);
	}


	//리스트 잘 작동하는지 테스트 출력
	CBinaryAVLTreeIterator<int, int> iter;
	CBinaryAVLTreeIterator<int, int> iterEnd = Tree.end();

	std::cout << "< 리스트 형태로 출력 >" << std::endl;
	for (iter = Tree.begin(); iter != iterEnd; ++iter)
	{
		std::cout << iter->m_Key << std::endl;
	}
	std::cout << "* 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);
	////////////////////////////////////////////


	//clear 테스트
	Tree.clear();


	//사용자가 원하는 값을 골라 삽입 가능하게 함.
	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;
		}

	}


	system("cls");



	//Erase 기능 테스트.

	//삭제 전 전방순회
	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;
}