자료구조...67

이진 탐색 트리 삽입 메서드 구현

 

BinarySearchTree.cpp

#pragma region 생성자
/// <summary>
/// 비어있는 DoublyLinkedList를 생성한다.
/// </summary>
BinarySearchTree::BinarySearchTree()
	: m_count(0), m_max(0), m_min(0), m_root(nullptr), m_free(nullptr)
{
}

/// <summary>
/// 메모리 누수를 막기 위해 동적 생성한 노드들을 제거한다.
/// </summary>
BinarySearchTree::~BinarySearchTree()
{
	Clear();

	while (m_free != nullptr)
	{
		Node* curNode{ m_free };
		m_free = m_free->m_right;
		delete curNode;
	}
}
#pragma endregion

#pragma region 메서드
/// <summary>
/// 
/// </summary>
/// <param name="value">추가할 값</param>
void BinarySearchTree::Insert(int value)
{
	
	Node** target{ &m_root };
	while (*target != nullptr)
	{
		if ((*target)->m_data == value)
		{
			target = nullptr;
			break;
		}

		if ((*target)->m_data > value)
		{
			target = &((*target)->m_left);
		}
		else
		{
			target = &((*target)->m_right);
		}
	}

	if (target != nullptr)
	{
		*target = PopNode(value);
		m_count++;
	}
}

/// <summary>
/// 테스트용 리스트 정보 출력 함수
/// </summary>
void BinarySearchTree::PrintInfo()
{
	std::cout << "----------------------\n";
	PrintInfo(m_root);
	std::cout << "----------------------\n\n";
}

/// <summary>
/// 테스트용 리스트 정보 출력 함수
/// </summary>
void BinarySearchTree::PrintInfo(Node* node, size_t depth)
{
	if (node == nullptr)
	{
		return;
	}

	for (int i = 0; i < depth; i++)
	{
		std::cout << "  ";
	}
	std::cout << "└  " << node->m_data << '\n';

	PrintInfo(node->m_left, depth + 1);
	PrintInfo(node->m_right, depth + 1);
}
#pragma endregion

 

main.cpp

#include <iostream>
#include "BinarySearchTree/BinarySearchTree.h"

// 생성한 자료구조 테스트용 메인
int main()
{
	BinarySearchTree bst;

	bst.Insert(5);

	bst.Insert(3);

	bst.Insert(1);

	bst.Insert(0);

	bst.Insert(4);

	bst.Insert(8);

	bst.Insert(7);

	bst.Insert(9);
	bst.PrintInfo();
}

 

실행 결과

----------------------
└  5
  └  3
    └  1
      └  0
    └  4
  └  8
    └  7
    └  9
----------------------