C++로 다시 구현하는 비 선형 자료구조 #2-1 Tree

이제 비 선형 자료구조를 구현할 차례다.

이번에 구현할 것은 Tree다.

트리는 대표적인 비선형 자료구조로,

시각화 하면 다음과 같이 마치 나무와 같은 연결 구조를 가지고 있어서 트리라고 불린다.

사실 STL에서 트리라는 자료구조를 제공하고 있지는 않다. 

하지만 Tree의 한 갈래인 Red-Black Tree를 기반으로 STL 내부에서는 다음과 같이 자료구조가 구현되어 있다.

• std::set, std::map → 내부적으로 Red-Black Tree 기반
• std::priority_queue → 내부적으로 Heap (완전 이진 트리) 기반
• 즉, 사용자에게 Tree 구조가 드러나지 않을 뿐, STL 내부에서는 Tree 기반 구조가 널리 사용된다.

일반 트리는 배열로 구현하지 않는 이유

일반적으로 일반 트리(General Tree)는 배열로 구현하지 않는다.
그 이유는 다음과 같다:

• 비선형 자료구조의 특성상, 노드 간의 관계가 고정된 것이 아니라 불규칙하고 다양하게 형성된다.
• 완전 이진 트리나 힙처럼 구조가 정형화된 경우를 제외하면, 배열을 사용하면 대부분의 공간이 빈 슬롯으로 낭비되며,
• 특히 부모-자식 관계의 표현이 매우 불편해지고 인덱스 기반 계산이 복잡해진다.

따라서 지역성/캐시 친화성(Locality of Reference)을 포기하더라도,
포인터를 통한 연결 방식이 훨씬 직관적이고 유연하다.

이는 트리 구조가 본질적으로 계층적이며 동적 확장이 필요한 구조라는 점에서,
정적 메모리인 배열보다 동적 연결이 적합하다는 설계 철학과도 일치한다.

 

 

Tree

• 트리는 계층적 구조를 표현하는 비선형 자료구조
• 하나의 루트 노드(root)를 중심으로 여러 개의 자식 노드(child)를 연결
• 노드들은 부모-자식 관계를 가지며, 이러한 관계는 재귀적으로 계속 확장될 수 있다.
• 노드 간 관계는 간선(Edge)를 통해 구성된다.

트리의 용어 정리

Root (루트)	트리의 최상위 노드
Parent (부모)	자식 노드를 가지는 노드
Child (자식)	부모로부터 연결된 노드
Leaf (잎)	자식 노드가 없는 노드
Subtree	어떤 노드를 루트로 하는 트리
Depth	루트에서 특정 노드까지의 거리
Height	어떤 노드를 루트로 하는 서브트리의 최대 깊이
Degree(차수)	자식 노드의 수

📌 구현 목표

• 본 글에서는 트리(Tree) 자료구조를 직접 구현합니다.
  • 템플릿 기반으로 자료형에 독립적인 구조를 구성
  • Node 구조체를 활용해 자식 노드를 동적으로 연결
  • 깊은 복사(Deep Copy) 지원
  • 포인터 기반 계층 구조 표현
  • 다음 주요 연산을 지원합니다:
    • 루트 설정
    • 삽입
      • 트리의 마지막에 노드 삽입
      • 특정 노드의 자식으로 삽입
    • 삭제
      • 트리에서 특정 자식 노드 제거 (관계만 해제)
      • 특정 자식 노드 삭제 (Delete) — 서브트리까지 삭제
      • 전체 자식 초기화 (Clear)
      • 트리 삭제
    • 탐색
      • 특정 노드 기준 데이터 탐색
      • 특정 노드 존재 유무 탐색
    • 조회
      • 트리 높이 계산
      • 특정 노드의 깊이
      • 노드 수 
      • 잎 노드 수
      • 서브 트리 크기 
      • 서브 트리 수 
    • 순회(Traverse)
      • 전위(Preorder) 순회
      • 후위(PostOrder) 순회
      • 레벨(Level) 순회
      • 중위(Inorder) 순회
        • 특수 트리에서만 가능 

※ 이번 구현은 일반 트리(General Tree) 구조를 기준으로 하며 InOrder만 이진트리임을 가정하고 구현합니다.

✅ 참고: 이진 트리 / 이진 탐색 트리(BST) 시간 복잡도

단, 이진 탐색 트리(BST) 혹은 **균형 트리(AVL/Red-Black Tree)**의 경우에는 연산 시간 복잡도가 다름

연산	일반 BST (편향 가능)	균형 BST (AVL / Red-Black)
Insert, Delete, Search	O(N) (최악)	O(log N) (보장됨)
InOrder 순회	O(N)	O(N)
Height 계산	O(N)	O(log N) (보장됨)

중위 순회를 통해 BST는 정렬된 값을 얻을 수 있기 때문에, O(N) 시간이 걸려도 유의미한 결과를 가짐.

✅ 요약

• 일반 트리에서는 대부분의 연산이 O(N)
• 특정 노드에 자식 추가는 vector 사용 시 O(1)
• 이진 트리 이상에서는 높이에 따라 연산이 O(log N)까지 개선 가능 (균형 트리 기준)
• 트리 순회는 전부 O(N) — 단, 전체를 순회하기 때문

🧱 프로젝트 구조

• Tree 은 Non_Linear_Data_Structures 네임스페이스에 포함되어 있습니다.
• 전체 프로젝트는 다음과 같은 구조를 가집니다:

/자료구조
 ├── #1.Linear_Data_Structures/
 │    ├── Linear_Data_Structures.h      	// 통합 헤더
 │    ├── 1_Stack/Stack.h               	// Stack 템플릿 정의
 │    ├── 2_1_Queue/Queue.h             	// Queue 템플릿 정의
 │    ├── 2_2_Deque/Deque.h             	// Deque 템플릿 정의
 │    ├── 2_3_PriorityQueue/PriorityQueue.h	// PriorityQueue 템플릿 정의
 │    └── 999_Extra
 │    	├── Adatpors
 │    	│	├──AdaptorStack.h		// AdaptorStack 템플릿 정의
 │    	│	├──AdaptorQueue.h		// AdaptorQueue 템플릿 정의
 │    	│	└──AdaptorPriorityQueue.h	// AdaptorPriorityQueue 템플릿 정의
 │    	└── Base
 │    		└──ChunkBasedDeque.h		// ChunkBasedDeque 템플릿 정의
 │
 ├── #2.Non_linear_Data_Structures/
 │    └── Non_Linear_Data_Structures.h  	// 통합 헤더
 │    └── 0_Node/Node.h  			// Node 템플릿 정의
 │    └── 1_1_Tree/Tree.h  			// Tree 템플릿 정의
 │
 └── main.cpp                           	// 테스트 메인 함수

프로그램 구성은 다음과 같다.

main.cpp

#include <iostream>
#include <string>
#include "#1.Linear_Data_Structures/Linear_Data_Structures.h"
#include "#2.Non_Linear_Data_Structures/Non_Linear_Data_Structures.h"
#include "TestFunctions.h"
#include "#2.Non_Linear_Data_Structures/0_Node/Node.h"

using namespace Linear_Data_Structures;
/// <summary>
/// 메인 애플리케이션 진입점 클래스
/// </summary>
/// <param name="argc"></param>
/// <param name="argv"></param>
/// <returns></returns>
/// 

int main(int argc, char* argv[])
{
	testTree();
	return 0;
}

#2.Non_Linear_Data_Structures/Non_Linear_Data_Structures.h

#pragma once

#include "0_Node/Node.h"
#include "1_1_Tree/Tree.h"
#include "1_2_BinaryTree/BinaryTree.h"
#include "1_3_RedBlackTree/RedBlackTree.h"
#include "1_4_AvlTree/AvlTree.h"

# 2.Non_Linear_Data_Structures/1_1_Tree/Tree .h

#pragma once

#include "../0_Node/Node.h"
#include "../../#1.Linear_Data_Structures/1_Stack/Stack.h"
#include "../../#1.Linear_Data_Structures/2_1_Queue/Queue.h"

namespace Non_Linear_Data_Structures
{
	// Tree class definition
	template <typename T>
	class Tree
	{
	public:
		// Default constructor Empty Tree
		inline Tree()
			: root(nullptr)
			, nodeCount(0)
		{}

		// Constructor with root node
		inline Tree(const Node<T>* node)
			: root(const_cast<Node<T>*>(node))
			, nodeCount(0)
		{
			if (root == nullptr)
			{
				return;
			}

			nodeCount = 1;
		}
		
		// Constructor with value
		// This constructor creates a tree with a single root node containing the given value
		// 한글설명 : 이 생성자는 주어진 값을 가진 단일 루트 노드로 트리를 만듭니다.
		inline Tree(const T& value, unsigned int initialCapacity = 2u)
			: root(nullptr)
			, nodeCount(1)
		{
			if (initialCapacity == 0)
			{
				initialCapacity = 2u; // Ensure a minimum initial capacity
			}
			root = CreateNode<T>(value, initialCapacity);
		}

		// Overloaded constructor with value and initial capacity
		inline Tree(const T& value, int initialCapacity)
			: root(nullptr)
			, nodeCount(1)
		{
			if (initialCapacity <= 0)
			{
				initialCapacity = 2; // Ensure a minimum initial capacity
			}
			root = CreateNode<T>(value, static_cast<unsigned int>(initialCapacity));
		}
		
		// DeepCopy constructor
		// This constructor creates a deep copy of the tree
		// It allocates new memory for the root node and all its children
		// 한글설명 : 이 생성자는 트리의 깊은 복사본을 만듭니다.
		// 루트 노드와 모든 자식 노드에 대해 새로운 메모리를 할당합니다.
		inline Tree(const Tree& other)
			: root(nullptr), nodeCount(0)
		{
			CopyFrom(other);
		}
		
		// move constructor
		inline Tree(Tree&& other) noexcept
			: root(other.root), nodeCount(other.nodeCount)
		{
			other.root = nullptr;
			other.nodeCount = 0;
		}

		// Destructor
		inline ~Tree()
		{ 
			Clear();
		}
		
		// Assignment operator
		inline Tree& operator=(const Tree& other)
		{
			if (this != &other)
			{
				Clear();
				CopyFrom(other);
			}
			return *this;
		}

		// Move assignment operator
		inline Tree& operator=(Tree&& other) noexcept
		{
			if (this != &other)
			{
				Clear();
				root = other.root;
				nodeCount = other.nodeCount;
				other.root = nullptr;
				other.nodeCount = 0;
			}
			return *this;
		}

		// modified methods
		Node<T>* Insert(Node<T>* node, bool order = false);							// Insert a node into the tree
		Node<T>* Insert(const T& value												// Insert a value into the tree
					, unsigned int initialCapacity = 2
					, bool order = false);													
		Node<T>* Insert(const T& value												// Insert a value into the tree
					, int initialCapacity
					, bool order = false);		

		Node<T>* InsertAt(Node<T>* target, Node<T>* node, bool order = false);		// Insert a node at a specific position
		Node<T>* InsertAt(Node<T>* target											// Insert a value at a specific position with order
					, const T& value
					, unsigned int initialCapacity = 2
					, bool order = false);
		Node<T>* InsertAt(Node<T>* target											// Insert a value at a specific position
					, const T& value
					, int initialCapacity
					, bool order = false);
		
		Node<T>* Remove(Node<T>* node);												// Remove a node from the tree
		Node<T>* Remove(const T& value);											// Remove a value from the tree
		Node<T>* RemoveIndex(const int index);										// Remove a node using index from the tree
		Node<T>* RemoveIndex(const unsigned int index);								// Remove a node using index from the tree
		
		Node<T>* RemoveAt(Node<T>* parent, Node<T>* node);							// Remove a node at a specific position
		Node<T>* RemoveAt(Node<T>* parent, const T& value);							// Remove a value at a specific position
		Node<T>* RemoveAtIndex(Node<T>* parent, const int index);					// Remove a node at a specific position using index
		Node<T>* RemoveAtIndex(Node<T>* parent, const unsigned int index);			// Remove a node at a specific position using index

		void Delete();																// Delete the entire tree
		void Delete(Node<T>* node);													// Delete a node from the tree
		void Delete(const T& value);												// Delete a value from the tree
		void DeleteIndex(const int index);											// Delete a node using index from the tree
		void DeleteIndex(const unsigned int index);									// Delete a node using index from the tree

		void DeleteAt(Node<T>* parent, Node<T>* node);								// Delete a node at a specific position
		void DeleteAt(Node<T>* parent, const T& value);								// Delete a value at a specific position
		void DeleteAtIndex(Node<T>* parent, const int index);						// Delete a node at a specific position using index
		void DeleteAtIndex(Node<T>* parent, const unsigned int index);				// Delete a node at a specific position using index
		
		void Clear();								// Clear the tree
	
		// accessor methods
		Node<T>* GetRoot();							// Get the root node of the tree
		const Node<T>* GetRoot() const;				// Get the root node of the tree (const version)
		int GetHeight() const;						// Get the height of the tree
		int GetHeight(const Node<T>* node) const;	// Get the height of a specific node
		int GetDegree() const;						// Get the degree of the root node
		int GetDegree(const Node<T>* node) const;	// Get the degree of a specific node
		int GetDepth(const Node<T>* node) const;	// Get the depth of a specific node
		bool Empty() const;							// Check if the tree is empty
		int Size() const;							// Get the size of the tree

		int CountSubtreeNodes(const Node<T>* n);	// Count the number of nodes in a subtree rooted at node n

		// Tree traversal methods
		// These methods take a function pointer to visit each node
		// DFS (Depth-First Search) Traversal methods
		void PreOrderTraversal(void (*visit)(const Node<T>*)) const;	// Pre-order traversal == Root -> Left -> Right
		void InOrderTraversal(void (*visit)(const Node<T>*)) const;		// In-order traversal == Left -> Root -> Right remains
		void PostOrderTraversal(void (*visit)(const Node<T>*)) const;	// Post-order traversal == Left -> Right -> Root

		// BFS (Breadth-First Search) Traversal methods
		void LevelOrderTraversal(void (*visit)(const Node<T>*)) const;	// Level-order traversal == Level by Level
	
	private:
		Node<T>* root;		// Root node of the tree
		int nodeCount;		// Count of nodes in the tree

		inline void CopyFrom(const Tree& other)
		{
			if (other.root == nullptr)
			{
				root = nullptr;
				nodeCount = 0;
				return;
			}

			// 루트 생성
			root = CreateNode<T>(other.root->data, other.root->capacity);
			nodeCount = 1;

			// other: BFS로 순회, this: 동일 구조 재구성
			Linear_Data_Structures::Queue<const Node<T>*> otherQueue;
			Linear_Data_Structures::Queue<Node<T>*> copyQueue;

			otherQueue.Push(other.root);
			copyQueue.Push(root);

			while (!otherQueue.Empty())
			{
				const Node<T>* ocur = otherQueue.Front(); otherQueue.Pop();
				Node<T>* current = copyQueue.Front(); copyQueue.Pop();

				for (unsigned int i = 0; i < ocur->childCount; ++i)
				{
					const Node<T>* otherCurrent = ocur->children[i];
					if (otherCurrent == nullptr) continue;

					Node<T>* child = CreateNode<T>(otherCurrent->data, otherCurrent->capacity);
					// order=true: 단순 append(혹은 네 AttachChild가 정렬 고려하면 그 정책 유지)
					if (AttachChild<T>(current, child, /*order=*/true))
					{
						++nodeCount;
						otherQueue.Push(otherCurrent);
						copyQueue.Push(child);
					}
					// Attach 실패 시: 정책상 생략(메모리 부족 같은 예외 상황). 필요하면 assert나 실패 처리 추가 가능.
				}
			}
		}
	};

	/// <summary>
	/// 트리에 새 노드를 삽입합니다.
	/// 루트부터 시작해서 자식의 빈 자리를 찾아서 삽입합니다.
	/// 만약 빈자리가 없다면, 트리의 레벨을 확장하고 새 노드를 삽입합니다.
	/// </summary>
	/// <typeparam name="T">트리와 노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="node">트리에 삽입할 노드입니다. nullptr이면 삽입이 수행되지 않습니다.</param>
	/// <param name="order">삽입 시 사용할 정렬 기준입니다.</param>
	/// <returns>삽입된 노드의 포인터를 반환합니다. 삽입에 실패하면 nullptr를 반환합니다.</returns>
	template <typename T>
	inline Node<T>* Tree<T>::Insert(Node<T>* node, bool order)
	{
		// 노드가 없거나 이미 부모를 가지고 있다면 삽입할 수 없습니다.
		if (node == nullptr || node->parent != nullptr)
		{
			return nullptr;
		}

		// 트리가 비어있는 경우, 새 노드를 루트로 설정합니다.
		if (root == nullptr)
		{
			root = node;
			root->parent = nullptr;
			nodeCount = 1;
			return root;
		}

		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;

		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드에 자식 노드가 있는지 확인합니다.
			if (current->childCount < current->capacity)
			{
				// 현재 노드에 자식 노드를 추가할 수 있는 공간이 있다면
				if (AttachChild<T>(current, node, order))
				{
					nodeCount++;
					return node; // 삽입된 노드를 반환합니다.
				}
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}

		// 트리의 모든 노드를 순회했지만 빈 자리를 찾지 못한 경우
		// 그런 경우는 없다
		// 만약 있다면 버그다

		return nullptr;
	}

	template <typename T>
	inline Node<T>* Tree<T>::Insert(const T& value
		, unsigned int initialCapacity
		, bool order)
	{
		if (initialCapacity == 0)
		{
			initialCapacity = 2;
		}

		// 트리가 비어있는 경우, 새 노드를 루트로 설정합니다.
		if (root == nullptr)
		{
			root = CreateNode<T>(value, initialCapacity);
			if (root != nullptr)
			{
				root->parent = nullptr;
				nodeCount = 1;
			}
			return root;
		}

		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드에 자식 노드가 있는지 확인합니다.
			if (current->childCount < current->capacity)
			{
				// 현재 노드에 자식 노드를 추가할 수 있는 공간이 있다면
				Node<T>* newNode = AttachChild<T>(current, value, initialCapacity, order);
				if (newNode != nullptr)
				{
					nodeCount++;
					return newNode; // 삽입된 노드를 반환합니다.
				}
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
		// 트리의 모든 노드를 순회했지만 빈 자리를 찾지 못한 경우
		// 그런 경우는 없다
		// 만약 있다면 버그다
		return nullptr; // 삽입에 실패한 경우 nullptr 반환
	}
	
	template <typename T>
	inline Node<T>* Tree<T>::Insert(const T& value
		, int initialCapacity
		, bool order)
	{
		if (initialCapacity <= 0)
		{
			initialCapacity = 2; // Ensure a minimum initial capacity
		}

		if (root == nullptr)
		{
			root = CreateNode<T>(value, initialCapacity);
			if (root != nullptr)
			{
				root->parent = nullptr;
				nodeCount = 1;
			}
			return root; 
		}
		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드에 자식 노드가 있는지 확인합니다.
			if (current->childCount < current->capacity)
			{
				// 현재 노드에 자식 노드를 추가할 수 있는 공간이 있다면
				Node<T>* newNode = AttachChild<T>(current, value, initialCapacity, order);
				if (newNode != nullptr)
				{
					nodeCount++;
					return newNode; // 삽입된 노드를 반환합니다.
				}
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
		return nullptr; 

	}

	/// <summary>
	/// 트리에서 지정된 노드에 새 자식 노드를 삽입합니다.
	/// 자식 노드의 수용력이 부족한 경우, 자동으로 확장합니다.
	/// </summary>
	/// <typeparam name="T">노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="target">노드를 삽입할 기준이 되는 대상 노드입니다.</param>
	/// <param name="node">삽입할 노드입니다.</param>
	/// <param name="order">자식 노드를 삽입할 위치(순서)를 지정하는 불리언 값입니다.</param>
	/// <returns>삽입에 성공하면 새로 삽입된 노드의 포인터를 반환하고, 실패하면 nullptr를 반환합니다.</returns>
	template <typename T>
	inline Node<T>* Tree<T>::InsertAt(Node<T>* target, Node<T>* node, bool order)
	{
		if (target == nullptr || node == nullptr)
		{
			return nullptr;
		}

		if (AttachChild<T>(target, node, order))
		{
			nodeCount++;
			return node; // Return the newly inserted node
		}
		
		// If insertion failed, return nullptr
		return nullptr;
	}

	template <typename T>
	inline Node<T>* Tree<T>::InsertAt(Node<T>* target
		, const T& value
		, unsigned int initialCapacity
		, bool order)
	{
		if (target == nullptr)
		{
			return nullptr;
		}
		
		Node<T>* newNode = AttachChild<T>(target, value, initialCapacity, order);

		if (newNode != nullptr)
		{
			nodeCount++;
		}

		return newNode; 
	}

	template <typename T>
	inline Node<T>* Tree<T>::InsertAt(Node<T>* target
		, const T& value
		, int initialCapacity
		, bool order)
	{
		if (target == nullptr)
		{
			return nullptr;
		}

		Node<T>* newNode = AttachChild<T>(target, value, initialCapacity, order);
		if (newNode != nullptr)
		{
			nodeCount++;
		}
		return newNode;
	}

	/// <summary>
	/// 트리에서 지정된 노드를 찾아 제거합니다
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <param name="node"></param>
	/// <returns></returns>
	template <typename T>
	inline Node<T>* Tree<T>::Remove(Node<T>* node)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		
		if (node == nullptr || node->parent == nullptr)
		{
			return nullptr;
		}

		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드가 제거할 노드와 일치하는지 확인합니다.
			if (current == node)
			{
				return RemoveAt(current->parent, current);
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
		// 트리의 모든 노드를 순회했지만 제거할 노드를 찾지 못한 경우
		return nullptr; // 제거할 노드를 찾지 못한 경우 nullptr 반환
	}

	template <typename T>
	inline Node<T>* Tree<T>::Remove(const T& value)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;

		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드가 제거할 노드와 일치하는지 확인합니다.
			if (current->data == value)
			{
				return RemoveAt(current->parent, value);
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
		// 트리의 모든 노드를 순회했지만 제거할 노드를 찾지 못한 경우
		return nullptr; // 제거할 노드를 찾지 못한 경우 nullptr 반환
	}

	// overloaded RemoveIndex methods
	template <typename T>
	inline Node<T>* Tree<T>::RemoveIndex(const int index)
	{
		return RemoveIndex(static_cast<unsigned int>(index));
	}
	
	/// <summary>
	/// 트리에서 지정된 인덱스에 해당하는 노드를 제거합니다.
	/// 루트부터 시작하여 인덱스에 해당하는 노드를 찾아 제거합니다.
	/// 레벨 순회 방식으로 구현되어 있습니다.
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <param name="index"></param>
	/// <returns></returns>
	template <typename T>
	inline Node<T>* Tree<T>::RemoveIndex(const unsigned int index)
	{
		if (root == nullptr || index >= static_cast<unsigned int>(nodeCount))
		{
			return nullptr;
		}

		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		unsigned int currentIndex = 0;
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			if (currentIndex == index)
			{
				return RemoveAt(current->parent, current);
			}
			currentIndex++;
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
		return nullptr; 
	}

	/// <summary>
	/// 특정 부모 노드에서 지정된 노드를 제거합니다.
	/// 부모 노드는 이미 특정되어 있어야 한다.
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <param name="parent"></param>
	/// <param name="node"></param>
	/// <returns></returns>
	template <typename T>
	inline Node<T>* Tree<T>::RemoveAt(Node<T>* parent, Node<T>* node)
	{
		if (node == nullptr) 
		{
			return nullptr;
		}
		
		if (parent == nullptr && node != root)
		{
			return nullptr;
		}

		if (node != root && node->parent != parent)
		{
			return nullptr;
		}

		Node<T>* target = DetachChild<T>(parent, node);     // 1) 분리 먼저
		if (target == nullptr)
		{
			return nullptr;
		}

		// 노드가 제거된 후 남는 노드 수를 재계산합니다.
		int removed = CountSubtreeNodes(target);
		
		// 음수가 발생한다면 에러입니다.
		int temp = nodeCount - removed;

		if (temp < 0)
		{
			// 노드가 제거된 후 남는 노드 수가 음수라면
			// 다시 부모 노드에 붙입니다.
			AttachChild<T>(parent, target, /*order=*/true);
			return nullptr;
		}

		nodeCount = temp;
		return target;
	}

	template <typename T>
	inline Node<T>* Tree<T>::RemoveAt(Node<T>* parent, const T& value)
	{
		if (parent == nullptr)
		{
			return nullptr;
		}

		Node<T>* target = DetachChild<T>(parent, value);
		if (target == nullptr)
		{
			return nullptr;
		}

		int removed = CountSubtreeNodes(target);

		int temp = nodeCount - removed;

		if (temp < 0)
		{
			AttachChild<T>(parent, target, /*order=*/true);
			return nullptr;
		}

		nodeCount = temp;
		return target;
	}
		
	/// <summary>
	/// 특정 부모 노드에서 지정된 인덱스에 해당하는 노드를 제거합니다.
	/// 항상 직계 자식 노드만을 대상으로 합니다.
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <param name="parent"></param>
	/// <param name="index"></param>
	/// <returns></returns>
	template <typename T>
	inline Node<T>* Tree<T>::RemoveAtIndex(Node<T>* parent, const int index)
	{
		if (parent == nullptr || index < 0 || index >= static_cast<int>(parent->childCount))
		{
			return nullptr;
		}
		
		Node<T>* target = DetachChildAtIndex<T>(parent, index);

		if (target == nullptr)
		{
			return nullptr;
		}

		int removed = CountSubtreeNodes(target);

		int temp = nodeCount - removed;

		if (temp < 0)
		{
			AttachChild<T>(parent, target, /*order=*/true);
			return nullptr;
		}

		nodeCount = temp;
		return target;
	}

	template <typename T>
	inline Node<T>* Tree<T>::RemoveAtIndex(Node<T>* parent, const unsigned int index)
	{
		if (parent == nullptr || index >= parent->childCount)
		{
			return nullptr;
		}
		
		Node<T>* target = DetachChildAtIndex<T>(parent, index);

		if (target == nullptr)
		{
			return nullptr;
		}

		int removed = CountSubtreeNodes(target);

		int temp = nodeCount - removed;

		if (temp < 0)
		{
			AttachChild<T>(parent, target, /*order=*/true);
			return nullptr;
		}

		nodeCount = temp;
		return target;
	}

	/// <summary>
	/// 트리를 삭제합니다.
	/// </summary>
	template <typename T>
	inline void Tree<T>::Delete()
	{
		delete this; // 트리 객체를 삭제합니다.
	}

	/// <summary>
	/// 트리에서 지정된 노드를 삭제합니다.
	/// Remove와 달리, 이 함수는 노드와 그 자식 노드를 모두 메모리에서 제거합니다.
	/// </summary>
	/// <typeparam name="T">트리와 노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="node">삭제할 노드를 가리키는 포인터입니다.</param>
	template <typename T>
	inline void Tree<T>::Delete(Node<T>* node)
	{
		// 트리에서 지정된 노드를 찾아 삭제합니다.
		if (node == nullptr)
		{
			return; // 노드가 nullptr이면 아무 작업도 하지 않습니다.
		}
		
		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드가 삭제할 노드와 일치하는지 확인합니다.
			if (current == node)
			{
				DeleteAt(current->parent, current);
				return; // 삭제 후 함수 종료
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
	}

	template <typename T>
	inline void Tree<T>::Delete(const T& value)
	{
		// 트리에서 지정된 값을 가진 노드를 찾아 삭제합니다.
		if (root == nullptr)
		{
			return; // 트리가 비어있으면 아무 작업도 하지 않습니다.
		}

		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			// 현재 노드가 삭제할 노드와 일치하는지 확인합니다.
			if (current->data == value)
			{
				DeleteAt(current->parent, current);
				return; // 삭제 후 함수 종료
			}
			// 현재 노드의 자식들을 큐에 추가합니다.
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
	}
	
	// overloaded DeleteIndex methods
	template <typename T>
	inline void Tree<T>::DeleteIndex(const int index)
	{
		DeleteIndex(static_cast<unsigned int>(index));
	}

	/// <summary>
	/// 트리의 전체 노드중 지정된 인덱스에 해당하는 노드를 삭제합니다.
	/// BFS(너비 우선 탐색) 방식으로 트리를 순회하여 인덱스에 해당하는 노드를 찾아 삭제합니다.
	/// 전체 노드 수를 기준으로 인덱스를 계산합니다.
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <param name="index"></param>
	template <typename T>
	inline void Tree<T>::DeleteIndex(const unsigned int index)
	{
		if (root == nullptr || index >= static_cast<unsigned int>(nodeCount))
		{
			return;
		}
		// 트리가 비어있지 않은 경우, 루트부터 시작하여 노드를 삽입합니다.
		// 순회 방식은 너비 우선 탐색(BFS)으로 구현합니다.
		Linear_Data_Structures::Queue<Node<T>*> queue;
		queue.Push(root);
		Node<T>* current;
		unsigned int currentIndex = 0;
		
		while (!queue.Empty())
		{
			current = queue.Front();
			queue.Pop();
			if (currentIndex == index)
			{
				DeleteAt(current->parent, current);
				return; // 삭제 후 함수 종료
			}
			currentIndex++;
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
	}

	template <typename T>
	inline void Tree<T>::DeleteAt(Node<T>* parent, Node<T>* node)
	{
		if (node == nullptr)
		{
			return; // 잘못된 입력
		}

		if (parent == nullptr && node != root)
		{
			return;
		}

		// 노드가 루트가 아니면서 부모를 갖지 않은 경우
		if (node != root && node->parent != parent)
		{
			return; 
		}

		int removed = CountSubtreeNodes(node);
		int temp = nodeCount - removed;

		if (temp < 0)
		{
			return;
		}

		nodeCount = temp;
		DeleteChild<T>(parent, node);

		if (node == root)
		{
			root = nullptr;
		}
	}

	template <typename T>
	inline void Tree<T>::DeleteAt(Node<T>* parent, const T& value)
	{
		if (parent == nullptr)
		{
			return; // 잘못된 입력
		}

		Node<T>* target = nullptr;
		for (int i = 0; i < parent->childCount; ++i)
		{
			if (parent->children[i] != nullptr && parent->children[i]->data == value)
			{
				target = parent->children[i];
				break; 
			}
		}

		int removed = CountSubtreeNodes(target);
		int temp = nodeCount - removed;

		if (temp < 0)
		{
			return;
		}

		nodeCount = temp;
		DeleteChild<T>(parent, value);
	}

	template <typename T>
	inline void Tree<T>::DeleteAtIndex(Node<T>* parent, const int index)
	{
		if (parent == nullptr || index < 0 || index >= static_cast<int>(parent->childCount))
		{
			return; // 잘못된 입력
		}

		int removed = CountSubtreeNodes(parent->children[index]);
		int temp = nodeCount - removed;
		if (temp < 0)
		{
			return; // 노드 제거 후 남는 노드 수가 음수인 경우
		}

		nodeCount = temp;

		DeleteChildAtIndex<T>(parent, index);
	}

	template <typename T>
	inline void Tree<T>::DeleteAtIndex(Node<T>* parent, const unsigned int index)
	{
		if (parent == nullptr || index >= parent->childCount)
		{
			return; // 잘못된 입력
		}
		int removed = CountSubtreeNodes(parent->children[index]);
		int temp = nodeCount - removed;
		if (temp < 0)
		{
			return; // 노드 제거 후 남는 노드 수가 음수인 경우
		}
		nodeCount = temp;
		DeleteChildAtIndex<T>(parent, index);
	}

	template <typename T>
	inline void Tree<T>::Clear()
	{
		if (root == nullptr)
		{ 
			nodeCount = 0; 
			return; 
		}

		Delete(root);
		root = nullptr; // 트리의 루트를 nullptr로 설정하여 트리를 비웁니다.
		nodeCount = 0; // 노드 수를 0으로 초기화합니다.
	}
	template <typename T>
	inline Node<T>* Tree<T>::GetRoot()
	{
		return root;
	}
	
	template <typename T>
	inline const Node<T>* Tree<T>::GetRoot() const
	{
		return root;
	}

	template <typename T>	
	inline int Tree<T>::GetHeight() const
	{
		return GetHeight(root);
	}

	template <typename T>	
	inline int Tree<T>::GetHeight(const Node<T>* node) const
	{
		if (node == nullptr)
		{
			return -1; // Height of an empty node is -1
		}

		int maxHeight = -1;
		for (unsigned int i = 0; i < node->childCount; ++i)
		{
			const Node<T>* child = node->children[i];
			if (child)
			{
				int h = GetHeight(child);

				if (h > maxHeight)
				{
					maxHeight = h;
				}
			}
		}

		return maxHeight + 1; // Add 1 for the current node
	}

	template <typename T>	
	inline int Tree<T>::GetDegree() const
	{
		if (root == nullptr)
		{
			return 0;
		}

		int maxDegree = 0;

		Linear_Data_Structures::Queue<const Node<T>*> queue;
		queue.Push(root);
		while (!queue.Empty())
		{
			const Node<T>* current = queue.Front();
			queue.Pop();
			int degree = static_cast<int>(current->childCount);
			if (degree > maxDegree)
			{
				maxDegree = degree; 
			}

			// Add children to the queue for further processing
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				if (current->children[i] != nullptr)
				{
					queue.Push(current->children[i]);
				}
			}
		}
		return maxDegree; // Return the maximum degree found
	}

	template <typename T>	
	inline int Tree<T>::GetDegree(const Node<T>* node) const
	{
		return node ? static_cast<int>(node->childCount) : 0;
	}

	template <typename T>	
	inline int Tree<T>::GetDepth(const Node<T>* node) const
	{
		if (node == nullptr)
		{
			return -1;
		}
		int depth = 0;
		const Node<T>* current = node->parent;

		while (current != nullptr)
		{
			depth++;
			current = current->parent;
		}
		return depth; // Return the depth of the node
	}

	template <typename T>	
	inline bool Tree<T>::Empty() const	
	{
		return root == nullptr; // If root is null, the tree is empty
	}

	template <typename T>	
	inline int Tree<T>::Size() const
	{
		return nodeCount;
	}

	/// <summary>
	/// 
	/// </summary>
	/// <typeparam name="T"></typeparam>
	/// <param name="n"></param>
	/// <returns></returns>
	template <typename T>
	inline int Tree<T>::CountSubtreeNodes(const Node<T>* node)
	{
		if (node == nullptr)
		{
			return 0;
		}

		int count = 0;
		Linear_Data_Structures::Queue<const Node<T>*> queue;
		queue.Push(node);
		while (!queue.Empty()) 
		{
			const Node<T>* current = queue.Front();
			queue.Pop();
			++count;
			for (unsigned i = 0; i < current->childCount; ++i)
			{
				if (current->children[i])
				{
					queue.Push(current->children[i]);
				}
			}
		}

		return count;
	}

	/// <summary>
	/// 트리의 모든 노드를 전위 순회(Pre-order Traversal) 방식으로 방문합니다.
	/// </summary>
	/// <typeparam name="T">트리 노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="visit">각 노드를 방문할 때 호출되는 함수 포인터입니다. 인자로 현재 노드의 포인터(const Node<T>*)를 받습니다.</param>
	template <typename T>
	inline void Tree<T>::PreOrderTraversal(void (*visit)(const Node<T>*)) const
	{
		if (root == nullptr || visit == nullptr)
		{
			return;
		}

		Linear_Data_Structures::Stack<const Node<T>*> stack;
		stack.Push(root);

		while (!stack.Empty())
		{
			const Node<T>* current = stack.Top();
			stack.Pop();
			visit(current); // Visit the current node

			// Push children onto the stack in reverse order to maintain left-to-right order
			for (int i = static_cast<int>(current->childCount) - 1; i >= 0; --i)
			{
				const Node<T>* child = current->children[i];
				if (child != nullptr)
				{
					stack.Push(child);
				}
			}
		}
	}

	/// <summary>
	/// Warning : This function only works for binary trees.
	/// 경고 : 이 함수는 이진 트리에만 사용하시오.
	/// 이진 트리의 중위 순회(In-order traversal)를 수행하며, 각 노드에 대해 지정된 함수를 호출합니다.
	/// </summary>
	/// <typeparam name="T">트리 노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="visit">각 노드를 방문할 때 호출되는 함수 포인터입니다. 인자로 노드의 포인터(const Node<T>*)를 받습니다.</param>
	template <typename T>
	inline void Tree<T>::InOrderTraversal(void (*visit)(const Node<T>*)) const
	{
		if (root == nullptr || visit == nullptr)
		{
			return; // If the tree is empty or visit function is null, do nothing
		}

		Linear_Data_Structures::Stack<const Node<T>*> stack;
		const Node<T>* current = root;

		while (current != nullptr || !stack.Empty())
		{
			while (current != nullptr)
			{
				stack.Push(current);

				current = (current->childCount > 0) ? current->children[0] : nullptr;
			}
			current = stack.Top();
			stack.Pop();
			visit(current); // Visit the current node

			current = current->childCount > 1 ? current->children[1] : nullptr; // Move to the right child
		}
	}

	/// <summary>
	/// 트리의 모든 노드를 후위 순회(post-order traversal) 방식으로 방문합니다.
	/// </summary>
	/// <typeparam name="T">트리 노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="visit">각 노드를 방문할 때 호출되는 함수 포인터입니다. 이 함수는 const Node<T>* 타입의 인자를 받아야 합니다.</param>
	template <typename T>
	inline void Tree<T>::PostOrderTraversal(void (*visit)(const Node<T>*)) const
	{
		if (root == nullptr || visit == nullptr)
		{
			return;
		}

		Linear_Data_Structures::Stack<const Node<T>*> stack;
		Linear_Data_Structures::Stack<const Node<T>*> outputStack;
		stack.Push(root);

		while (!stack.Empty())
		{
			const Node<T>* current = stack.Top();
			stack.Pop();
			outputStack.Push(current); // Push the current node to output stack

			// Push children onto the stack
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				const Node<T>* child = current->children[i];
				if (child != nullptr)
				{
					stack.Push(child);
				}
			}
		}

		while (!outputStack.Empty())
		{
			const Node<T>* child = outputStack.Top();
			outputStack.Pop();
			visit(child);
		}
	}

	/// <summary>
	/// 트리의 레벨 순회(너비 우선 탐색)를 수행하며 각 노드에 대해 지정된 함수를 호출합니다.
	/// </summary>
	/// <typeparam name="T">트리 노드에 저장되는 데이터의 타입입니다.</typeparam>
	/// <param name="visit">각 노드를 방문할 때 호출되는 함수 포인터입니다. 이 함수는 const Node<T>* 타입의 인자를 받아야 합니다.</param>
	template <typename T>
	inline void Tree<T>::LevelOrderTraversal(void (*visit)(const Node<T>*)) const
	{
		if (root == nullptr || visit == nullptr)
		{
			return;
		}

		Linear_Data_Structures::Queue<const Node<T>*> queue;
		queue.Push(root);

		while (!queue.Empty())
		{
			const Node<T>* current = queue.Front();
			queue.Pop();
			visit(current); // Visit the current node

			// Enqueue all children of the current node
			for (unsigned int i = 0; i < current->childCount; ++i)
			{
				const Node<T>* child = current->children[i];
				if (child != nullptr)
				{
					queue.Push(child);
				}
			}
		}
	}
}

실습 코드는 제 깃허브에 있습니다.

Workspace/자료구조 at main · cyphen156/Workspace

Workspace/자료구조 at main · cyphen156/Workspace

 

 

 

 

 

※ 25.08.13 회고

트리구조 구현하는데 엄청 오래걸렷다 

그냥 메서드 오버로딩 안하거나, 하더라도 API 호출을 한갈래로 통일시키면 빠르게 끝낼 수 있었는데

그렇게 하지 않은건 User <-> Tree <-> Node간의 호출 관계와 인자 전달을 같은 규격으로 통일시켜서 단일 흐름을 보일 수 있게 하고싶었기 때문이다. 

중간에 새 노드를 생성해서 API호출인자를 다르게 만들지 않고 직렬화 해서 동일하게 단말 노드까지 전달되어 실제 수행되도록 함으로써 조금 더 호출 흐름이 이해되기 쉽도록 구현해보았다.

그리고 현재 일반트리를 구현했지만 사실상 이 구조를 Adaptor Base로 사용하여 다른 자료구조 클래스들에 적용할 수 있도록 구현되어 있다.

TestFunctions.cpp

#include "TestFunctions.h"
#include <iostream>
#include <string>
#include <cassert>
#include <vector>
#include <algorithm>
#include "#1.Linear_Data_Structures/Linear_Data_Structures.h"
#include "#2.Non_Linear_Data_Structures/Non_Linear_Data_Structures.h"

using namespace Linear_Data_Structures;
using namespace Non_Linear_Data_Structures;

static std::vector<int> visit_log;
static void VisitCollect(const Node<int>* n) { visit_log.push_back(n->data); }
static void ResetVisit() { visit_log.clear(); }

// 유틸: 완전-작은 트리 구성
static Tree<int> BuildSmallTree()
{
    Tree<int> t(1, 3);
    Node<int>* r = t.GetRoot();

    Node<int>* n2 = t.InsertAt(r, 2, 3, true);
    Node<int>* n3 = t.InsertAt(r, 3, 3, true);
    Node<int>* n4 = t.InsertAt(n2, 4, 3, true);
    Node<int>* n5 = t.InsertAt(n2, 5, 3, true);
    Node<int>* n6 = t.InsertAt(n3, 6, 3, true);

    assert(r && n2 && n3 && n4 && n5 && n6);
    return t;
}

/// <summary>
/// 테스트 함수 모음집
/// </summary>

// Stack example usage
void testStack()
{
	Stack<int> stack;
	stack.Push(10);
	stack.Push(20);
	std::cout << "Stack top: " << stack.Top() << '\n'
		<< "Stack Size : " << stack.Size() << std::endl;
	stack.Pop();
	std::cout << "After Pop, Stack top: " << stack.Top() << '\n'
		<< "Stack Size : " << stack.Size() << std::endl;
	stack.Clear();
	std::cout << "Stack is Cleared: " << std::endl;

	Stack<std::string> stringStack;
}

// queue example usage
void testQueue()
{
	Queue<int> queue;
	queue.Push(30);
	queue.Push(40);
	std::cout << "Queue front: " << queue.Front() << '\n'
		<< "Queue Size : " << queue.Size() << std::endl;
	queue.Pop();
	std::cout << "After Pop, Queue front: " << queue.Front() << '\n'
		<< "Queue Size : " << queue.Size() << std::endl;
	queue.Clear();
	std::cout << "Queue is Cleared: " << std::endl;

	Queue<std::string> stringQueue;
	stringQueue.Push("Hello");
	stringQueue.Push("World");
	std::cout << "Queue Back: " << stringQueue.Back() << '\n'
		<< "Queue Size : " << stringQueue.Size() << std::endl;
	stringQueue.Clear();
	std::cout << "String Queue is Cleared: " << std::endl;
}

// Deque example usage
void testDeque()
{
	Deque<int> deque;
	deque.PushFront(50);
	deque.PushBack(60);
	std::cout << "Deque Front: " << deque.Front() << '\n'
		<< "Deque Back: " << deque.Back() << '\n'
		<< "Deque Size : " << deque.Size() << std::endl;
	deque.PopFront();
	std::cout << "After PopFront, Deque Front: " << deque.Front() << '\n'
		<< "Deque Size : " << deque.Size() << std::endl;
	deque.PopBack();
	std::cout << "After PopBack, Deque Back: " << deque.Back() << '\n'
		<< "Deque Size : " << deque.Size() << std::endl;
	deque.Clear();
	std::cout << "Deque is Cleared: " << std::endl;

	Deque<std::string> stringDeque;
	stringDeque.PushFront("Deque");
	stringDeque.PushBack("Example");
	std::cout << "String Deque Front: " << stringDeque.Front() << '\n'
		<< "String Deque Back: " << stringDeque.Back() << '\n'
		<< "String Deque Size : " << stringDeque.Size() << std::endl;

	stringDeque.PopFront();
	std::cout << "After PopFront, String Deque Front: " << stringDeque.Front() << '\n'
		<< "String Deque Size : " << stringDeque.Size() << std::endl;
}

// PriorityQueue example usage
void testPriorityQueue()
{
	PriorityQueue<int> priorityQueue;
	priorityQueue.Push(1, 100);
	priorityQueue.Push(2, 200);
	priorityQueue.Push(3, 300);
	std::cout << "Priority Queue Top: " << priorityQueue.Top() << '\n'
		<< "Priority Queue Size : " << priorityQueue.Size() << std::endl;
	priorityQueue.Pop();
	std::cout << "After Pop, Priority Queue Top: " << priorityQueue.Top() << '\n'
		<< "Priority Queue Size : " << priorityQueue.Size() << std::endl;
	priorityQueue.Clear();
	std::cout << "Priority Queue is Cleared: " << std::endl;
	PriorityQueue<std::string> stringPriorityQueue;
	stringPriorityQueue.Push(1, "High");
	stringPriorityQueue.Push(2, "Medium");
	stringPriorityQueue.Push(3, "Low");
	std::cout << "String Priority Queue Top: " << stringPriorityQueue.Top() << '\n'
		<< "String Priority Queue Size : " << stringPriorityQueue.Size() << std::endl;
	stringPriorityQueue.Clear();
	std::cout << "String Priority Queue is Cleared: " << std::endl;
}

void testChunkBasedDeque()
{
}

void testAdaptorStack()
{
}

void testAdaptorQueue()
{
}

void testAdaptorPriorityQueue()
{
}


// Non-linear Data Structures Test
void testNode()
{
	Node<int>* root = CreateNode<int>(1);
	AttachChild(root, CreateNode<int>(2));
	AttachChild(root, CreateNode<int>(3));
	AttachChild(root, CreateNode<int>(4));
	AttachChild(root, CreateNode<int>(5));
	std::cout << "Root Node Data: " << root->data << std::endl;
	std::cout << "Root Node Child Count: " << root->childCount << std::endl;
	for (unsigned int i = 0; i < root->childCount; ++i)
	{
		std::cout << "Child " << i + 1 << " Data: " << root->children[i]->data << std::endl;
	}

	AttachChild(root->children[0], CreateNode<int>(3));
	AttachChild(root->children[0], CreateNode<int>(6));
	std::cout << "After attaching children to first child:" << std::endl;
	for (unsigned int i = 0; i < root->children[0]->childCount; ++i)
	{
		std::cout << "Child of first child " << i + 1 << " Data: " << root->children[0]->children[i]->data << std::endl;
	}
	DetachAllChildren(root);
	delete root;
	std::cout << "Node Test Completed." << std::endl;
}

/// <summary>
/// Tree.h에 있는 모든 기능을 테스팅
/// 곙계테스트 포함
/// </summary>
void testTree()
{
    // 1) 기본 생성/접근자
    {
        Tree<int> t;
        assert(t.Empty());
        assert(t.Size() == 0);
        assert(t.GetRoot() == nullptr);
        assert(t.GetHeight() == -1);
        assert(t.GetDegree() == 0);
    }

    // 2) 값 생성자(capacity 경계 포함)
    {
        Tree<int> t1(10, 0u);  // 0 -> 2로 보정
        assert(!t1.Empty());
        assert(t1.Size() == 1);
        assert(t1.GetRoot()->data == 10);

        Tree<int> t2(20, -5);  // <=0 -> 2로 보정
        assert(!t2.Empty());
        assert(t2.Size() == 1);
        assert(t2.GetRoot()->data == 20);
    }

    // 3) Insert 오버로드들
    {
        Tree<int> t(1, 2);
        assert(t.Size() == 1);

        // Insert(value, unsigned)
        Node<int>* a = t.Insert(2, 2, true);
        assert(a && t.Size() == 2);

        // Insert(value, int)
        Node<int>* b = t.Insert(3, 2, true);
        assert(b && t.Size() == 3);

        // Insert(node*)
        Node<int>* orphan = CreateNode<int>(99, 2);
        Node<int>* c = t.Insert(orphan, true);
        assert(c == orphan && t.Size() == 4);

        // 이미 부모를 가진 노드 삽입 거부
        assert(t.Insert(orphan, true) == nullptr);
    }

    // 4) InsertAt 오버로드들
    {
        Tree<int> t(1, 3);
        Node<int>* r = t.GetRoot();

        Node<int>* n2 = t.InsertAt(r, 2, 3, true);
        Node<int>* n3 = t.InsertAt(r, 3, 3, true);
        assert(t.Size() == 3);

        // InsertAt(node*, node*)
        Node<int>* orphan = CreateNode<int>(4, 3);
        Node<int>* n4 = t.InsertAt(n2, orphan, true);
        assert(n4 && n4->parent == n2 && t.Size() == 4);

        // target nullptr 거부
        assert(t.InsertAt(nullptr, 7, 2, true) == nullptr);
        // node nullptr 거부
        assert(t.InsertAt(n3, (Node<int>*)nullptr, true) == nullptr);
    }

    // 5) Remove 오버로드들 (BFS로 찾은 뒤 RemoveAt 호출)
    {
        Tree<int> t = BuildSmallTree(); // 1,[2,3],2->[4,5],3->[6]
        int before = t.Size();          // 6 노드

        // Remove(Node*)
        Node<int>* n3 = t.GetRoot()->children[1];
        Node<int>* detached = t.Remove(n3);
        assert(detached == n3);
        assert(t.Size() == before - 2); // n3, n6 분리
        assert(detached->parent == nullptr);

        // Remove(value)
        Node<int>* n2 = t.GetRoot()->children[0];
        Node<int>* d2 = t.Remove(2);
        assert(d2 == n2);
        assert(t.Size() == 1); // 1만 남음
        // 트리에 없는 값
        assert(t.Remove(999) == nullptr);
    }

    // 6) RemoveAt 직계 대상으로만
    {
        Tree<int> t = BuildSmallTree();
        Node<int>* r = t.GetRoot();
        Node<int>* n2 = r->children[0];

        // 잘못된 parent
        assert(t.RemoveAt((Node<int>*)nullptr, n2) == nullptr);
        // parent 불일치
        assert(t.RemoveAt(n2, r) == nullptr);

        // OK
        Node<int>* detached = t.RemoveAt(r, n2);
        assert(detached == n2);
        assert(t.Size() == 6 - 3);

        // RemoveAt(value)
        Node<int>* n3 = t.GetRoot()->children[0]; // 남은 건 3뿐
        Node<int>* d3 = t.RemoveAt(t.GetRoot(), 3);
        assert(d3 == n3);
        assert(t.Size() == 1);
    }

    // 7) RemoveAtIndex
    {
        Tree<int> t = BuildSmallTree();
        Node<int>* r = t.GetRoot();

        // 음수/범위 바깥
        assert(t.RemoveAtIndex(r, -1) == nullptr);
        assert(t.RemoveAtIndex(r, 99u) == nullptr);

        // index 1 -> 노드 3 분리
        Node<int>* n3 = r->children[1];
        Node<int>* out = t.RemoveAtIndex(r, 1u);
        assert(out == n3);
        assert(t.Size() == 4); // 1,2,4,5
    }

    // 8) Delete  메모리 해제 & 카운팅
    {
        Tree<int> t = BuildSmallTree();
        int before = t.Size(); // 6
        // Delete(value)
        t.Delete(2);
        assert(t.Size() == before - 3);

        // DeleteIndex
        t.DeleteIndex(1u);
        assert(t.Size() == 1);

        // Delete(node*)
        Node<int>* r = t.GetRoot();
        t.Delete(r); // 루트 삭제
        assert(t.Size() == 0);
        assert(t.GetRoot() == nullptr);
    }

    // 9) Clear()
    {
        Tree<int> t = BuildSmallTree();
        assert(!t.Empty());
        t.Clear();
        assert(t.Empty());
        assert(t.Size() == 0);
        assert(t.GetRoot() == nullptr);
    }

    // 10) 순회 검증
    {
        Tree<int> t = BuildSmallTree();
        ResetVisit();
        t.LevelOrderTraversal(&VisitCollect);
        assert((visit_log.size() == 6) && visit_log[0] == 1 && visit_log[1] == 2 && visit_log[2] == 3 &&
            visit_log[3] == 4 && visit_log[4] == 5 && visit_log[5] == 6);

        ResetVisit();
        t.PreOrderTraversal(&VisitCollect);
        assert(visit_log.size() == 6 && visit_log[0] == 1 && visit_log[1] == 2);

        ResetVisit();
        t.PostOrderTraversal(&VisitCollect);
        assert(visit_log.size() == 6 && visit_log.back() == 1);
    }

    // 11) GetHeight / GetDegree / GetDepth
    {
        Tree<int> t = BuildSmallTree();
        Node<int>* r = t.GetRoot();
        assert(t.GetHeight() >= 0);
        assert(t.GetDegree() >= 0);
        assert(t.GetDepth(r) == 0);
        assert(t.GetDepth(r->children[0]) == 1);
    }

    // 12) 복사/이동/대입
    {
        Tree<int> t1 = BuildSmallTree();
        Tree<int> t2(t1);
        assert(t2.Size() == t1.Size());

        Tree<int> t3;
        t3 = t1;
        assert(t3.Size() == t1.Size());

        Tree<int> t4(std::move(t1));
        assert(t4.Size() == 6);
        assert(t1.Size() == 0);

        Tree<int> t5;
        t5 = std::move(t2);
        assert(t5.Size() == 6);
        assert(t2.Size() == 0);
    }

    // 13) 경계/방어 로직
    {
        Tree<int> t = BuildSmallTree();
        Node<int>* r = t.GetRoot();
        t.DeleteAt((Node<int>*)nullptr, r->children[0]);
        assert(t.Size() == 6);

        assert(t.RemoveIndex(-1) == nullptr);
        assert(t.RemoveIndex(999u) == nullptr);

        assert(t.Remove((Node<int>*)nullptr) == nullptr);

        t.Delete((Node<int>*)nullptr);
        assert(t.Size() == 6);
    }

    std::cout << "All Tree<T> tests passed.\n";
}