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

비선형 자료구조는 데이터 간의 관계가 일직선이 아닌 계층적 또는 비계층적 관계(네트워크 구조)로 연결되는 구조를 말한다.
대표적으로 다음 자료구조들이 존재한다.

• 트리(Tree) : 계층 구조를 표현
• 힙(Heap) : 우선순위를 갖는 완전 이진 트리
• 그래프(Graph) : 네트워크 구조를 표현
• 트라이 : 문자열 탐색에 최적화된 전위 트리 구조
• 해시 : 해시 함수를 통해 빠르게 데이터 접근 (내부적으로 리스트나 트리로 충돌 처리)

이러한 비선형 구조에서는 데이터의 저장 방식보다는 연결 관계가 훨씬 중요
즉, "어떤 데이터를 갖고 있는가"보다 "각 데이터가 어떻게 연결되어 있는가"가 중요하다.

Node

이러한 연결 관계의 기본 단위는 Node이다.
Node는 다음의 역할을 수행합니다:

1. 데이터 보관: 실제 값을 저장하는 컨테이너 역할
2. 연결 정보 보유: 다른 노드(부모 / 자식 / 이웃 등)와의 관계를 포인터로 연결

예를 들어 트리(Tree) 구조에서는 각 노드가 다음과 같은 정보갖는다.

• 자신이 가진 데이터 (data)
• 자신의 부모 노드 (parent)
• 자신의 자식 노드들 (children)

📌 구현 목표

• 본 글에서는 Node(노드) 자료를 직접 구현
• 템플릿 기반으로 자료형에 독립적인 구조를 구성
• 동적 배열을 사용하여 자식 노드 관리

🧱 프로젝트 구조

• Node는 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_2_PriorityQueue/PriorityQueue.h	// PriorityQueue 템플릿 정의
 ├── #2.Non_Linear_Data_Structures/
 │    └── Non_Linear_Data_Structures.h  	// 통합 헤더
 │    └── 0_Node/Node.h			  	// Node 템플릿 정의
 └── 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"


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

int main(int argc, char* argv[])
{
	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/0_Node/Node.h

핵심 데이터 구조체

template <typename T>
struct Node
{
	T data;
	unsigned int childCount;
	unsigned int capacity = 2;

	Node<T>* parent;
	Node<T>** children;
};

노드의 생성, 삭제, 자식관리를 담당하는 헬퍼 함수들

#pragma once

namespace Non_Linear_Data_Structures
{
	/// <summary>
	/// struct Node
	/// <param name="data">T</param>
	/// <param name="childCount">int</param>
	/// <param name="capacity">int</param>
	/// <param name="parent">Node*</param>
	/// <param name="children">Node**</param>
	/// </summary>
	template <typename T>
	struct Node
	{
		T data;
		unsigned int childCount;
		unsigned int capacity = 2;

		Node<T>* parent;
		Node<T>** children;
	};

	// create a new Node with initial children capacity
	template <typename T>
	inline Node<T>* CreateNode(const T& value, unsigned int initialCapacity = 2u)
	{
		Node<T>* newNode = new Node<T>{};
		newNode->data = value;
		newNode->childCount = 0u;
		if (initialCapacity == 0)
		{
			initialCapacity = 2; // Ensure a minimum capacity
		}
		newNode->capacity = initialCapacity;
		newNode->parent = nullptr;
		newNode->children = new Node<T>*[initialCapacity] {};
		return newNode;
	}

	// overloaded CreateNode function
	// type casting for initialCapacity
	template <typename T>
	inline Node<T>* CreateNode(const T& value, int initialCapacity)
	{
		if (initialCapacity <= 0)
		{
			initialCapacity = 2; // Ensure a minimum capacity
		}
		return CreateNode<T>(value, static_cast<unsigned int>(initialCapacity));
	}

	// Extend the capacity of the node's children array
	// Use this function when you know the parent node's capacity is not enough
	// 한글설명 : 노드의 자식 배열의 용량을 확장합니다.
	// 이 함수는 부모 노드의 자식 수용력이 충분하지 않을 때 사용합니다.
	// 무조건 부모 노드의 자식 수용력을 두 배로 확장합니다.
	template <typename T>
	inline void ExtendCapacity(Node<T>* parent)
	{
		if (parent == nullptr)
		{ 
			return; 
		}

		unsigned int newCapacity = 2 * parent->capacity;

		Node<T>** newChildren = new Node<T>*[newCapacity] {};
		for (unsigned int i = 0u; i < parent->childCount; ++i)
		{
			newChildren[i] = parent->children[i];
		}
		delete[] parent->children;
		parent->children = newChildren;
		parent->capacity = newCapacity;
	}

	// ensure the node's children array has enough capacity
	// Use this function when you know the required capacity
	// 한글설명 : 노드의 자식 배열을 충분한 용량으로 확보합니다.
	// 이 함수는 필요한 용량을 알고 있을 때 사용합니다.
	template <typename T>
	inline void EnsureCapacity(Node<T>* node, unsigned int required)
	{
		if (node == nullptr || node->capacity >= required)
		{ 
			return; 
		}

		unsigned int newCapacity = node->capacity;
		while (newCapacity < required)
		{
			newCapacity *= 2;
		}
		
		Node<T>** newChildren = new Node<T>*[newCapacity] {};
		for (unsigned int i = 0u; i < node->childCount; ++i)
		{
			newChildren[i] = node->children[i];
		}
		delete[] node->children;
		node->children = newChildren;
		node->capacity = newCapacity;
	}
	
	// overloaded EnsureCapacity function
	// type casting for required capacity
	template <typename T>
	inline void EnsureCapacity(Node<T>* node, int required)
	{
		if (required <= 0)
		{
			required = 2; // Ensure a minimum required capacity
		}
		EnsureCapacity<T>(node, static_cast<unsigned int>(required));
	}

	// AttachChild with value
	// Use this function to create a new node and attach it as a child to the parent node.
	// 한글설명 : 새로운 노드를 생성하고, 부모에게 자식으로 추가합니다.
	// 새로운 노드를 생성하며, 값을 복사합니다.
	// order는 자식 노드를 정렬할지 여부를 지정합니다.
	// 기본값은 false입니다.
	template <typename T>
	inline Node<T>* AttachChild(Node<T>* parent
							, const T& value
							, unsigned int initialCapacity = 2u
							, bool order = false)
	{
		if (parent == nullptr) 
		{
			return nullptr; 
		}

		// Ensure the parent node has enough capacity for a new child
		// 부모 노드가 새로운 자식을 위한 충분한 용량을 가지고 있는지 확인합니다.
		if (parent->childCount >= parent->capacity)
		{
			ExtendCapacity<T>(parent);
		}

		// 하나 생성해서
		Node<T>* child = CreateNode<T>(value, initialCapacity);

		if (order)
		{
			for (unsigned int i = 0u; i < parent->childCount; ++i)
			{
				// If order is true, find the correct position to insert the new child
				// 한글설명 : order가 true인 경우, 새로운 자식을 삽입할 올바른 위치를 찾습니다.
				if (parent->children[i]->data > child->data)
				{
					// Shift existing children to the right
					for (unsigned int j = parent->childCount; j > i; --j)
					{
						parent->children[j] = parent->children[j - 1u];
					}
					parent->children[i] = child;
					child->parent = parent;
					parent->childCount += 1u;
					return child;
				}
			}
		}

		// If order is false or no position found, add to the end
		// 한글설명 : order가 false이거나 위치를 찾지 못한 경우, 끝에 추가합니다.
		child->parent = parent;
		parent->children[parent->childCount] = child;
		parent->childCount += 1u;
		// Return the newly created child node
		// 새로 생성된 자식 노드를 반환합니다.
		return child;
	}

	// overloaded AttachChild function
	// type casting for initial capacity
	template <typename T>
	inline Node<T>* AttachChild(Node<T>* parent
							, const T& value
							, int initialCapacity = 2
							, bool order = false)
	{
		if (initialCapacity <= 0)
		{
			initialCapacity = 2; // Ensure a minimum initial capacity
		}
		return AttachChild<T>(parent, value, static_cast<unsigned int>(initialCapacity), order);
	}

	// AttachChild with existing Node
	// Use this function to attach an existing node as a child to the parent node.
	// 한글설명 : 기존 노드를 부모에게 자식으로 추가합니다.
	// 기존 노드를 그대로 사용하며, 값을 복사하지 않습니다.
	template <typename T>
	inline void AttachChild(Node<T>* parent, Node<T>* child, bool order = false)
	{
		if (parent == nullptr || child == nullptr) 
		{
			return; 
		}

		if (parent->childCount >= parent->capacity)
		{
			ExtendCapacity<T>(parent);
		}

		if (order)
		{
			for (unsigned int i = 0u; i < parent->childCount; ++i)
			{
				if (parent->children[i]->data > child->data)
				{
					for (unsigned int j = parent->childCount; j > i; --j)
					{
						parent->children[j] = parent->children[j - 1u];
					}
					parent->children[i] = child;
					child->parent = parent;
					parent->childCount += 1u;
					return;
				}
			}
		}

		child->parent = parent;
		parent->children[parent->childCount] = child;
		parent->childCount += 1u;
	}

	

	// DetachChild with target Child Node
	// Use this function to detach a specific child node from the parent node.
	// The detached child node will not be deleted.
	// Remaining child nodes will be shifted to the left to fill the gap.
	// 한글설명 : 부모 노드에서 특정 자식 노드를 분리합니다.
	// 분리된 자식 노드가 삭제되지 않습니다.
	// 남은 자식 노드를 왼쪽으로 이동하여 빈 공간을 채웁니다.
	template <typename T>
	inline Node<T>* DetachChild(Node<T>* parent, Node<T>* target)
	{
		if (parent == nullptr || target == nullptr)
		{
			return nullptr; // 부모 노드나 대상 노드가 nullptr인 경우
		}

		int index = -1;
		for (unsigned int i = 0u; i < parent->childCount; ++i)
		{
			if (parent->children[i] == target)
			{
				index = static_cast<int>(i);
				break;
			}
		}

		// Target not found in parent's children
		// 타겟을 못찾았음
		if (index < 0)
		{
			return nullptr;
		}

		// Shift remaining children to the left
		// 남은 자식 노드를 왼쪽으로 이동합니다.
		for (unsigned int j = static_cast<unsigned int>(index); j < parent->childCount - 1u; ++j)
		{
			parent->children[j] = parent->children[j + 1u];
		}

		parent->childCount -= 1u;	// Decrease the child count
		parent->children[parent->childCount] = nullptr; // Clear the last child
		target->parent = nullptr;	// Detach the target node from its parent
		return target;
	}

	// DetachChild with Node
	// Use this function to detach a child node from the parent node.
	// // The detached child node will not be deleted.
	// Remaining child nodes will be shifted to the left to fill the gap.
	// 한글설명 : 노드를 부모 노드에서 분리합니다.
	// 분리된 노드가 삭제되지 않습니다.
	// 부모노드에게서 남은 자식 노드를 왼쪽으로 이동하여 빈 공간을 채웁니다.
	template <typename T>
	inline Node<T>* DetachNode(Node<T>* target)
	{
		if (target == nullptr || target->parent == nullptr)
		{
			return nullptr;
		}

		DetachChild<T>(target->parent, target);
		return target;
	}

	// DetachChild with value
	// 자식 노드가 삭제되지 않습니다.
	template <typename T>
	inline Node<T>* DetachChild(Node<T>* parent, const T& value)
	{
		if (parent == nullptr)
		{
			return nullptr; // 부모 노드가 nullptr인 경우
		}

		int index = -1;
		for (unsigned int i = 0u; i < parent->childCount; ++i)
		{
			if (parent->children[i] && parent->children[i]->data == value)
			{
				index = static_cast<int>(i);
				break;
			}
		}

		if (index < 0)
		{
			return nullptr; // Value not found in parent's children
		}

		Node<T>* target = parent->children[index];
		// Shift remaining children to the left
		for (unsigned int j = static_cast<unsigned int>(index); j < parent->childCount - 1u; ++j)
		{
			parent->children[j] = parent->children[j + 1u];
		}
		parent->childCount -= 1u; // Decrease the child count
		parent->children[parent->childCount] = nullptr; // Clear the last child
		target->parent = nullptr; // Detach the target node from its parent
		return target;
	}

	// DetachChild with index
	// Use this function to detach a child node at a specific index from the parent node.
	// The detached child node will not be deleted.
	// Remaining child nodes will be shifted to the left to fill the gap.
	// 한글설명 : 부모 노드에서 특정 인덱스의 자식 노드를 분리합니다.
	// 분리된 자식 노드가 삭제되지 않습니다.
	// 남은 자식 노드를 왼쪽으로 이동하여 빈 공간을 채웁니다.
	template <typename T>
	inline Node<T>* DetachChild(Node<T>* parent, unsigned int index)
	{
		if (parent == nullptr || index >= parent->childCount)
		{
			return nullptr; // 부모 노드가 nullptr이거나 인덱스가 범위를 벗어난 경우
		}
		
		Node<T>* target = parent->children[index];

		if (target == nullptr)
		{
			return nullptr; // 해당 인덱스에 자식 노드가 없는 경우
		}
		
		// Shift remaining children to the left
		for (unsigned int j = index; j < parent->childCount - 1u; ++j)
		{
			parent->children[j] = parent->children[j + 1u];
		}

		parent->childCount -= 1u; // Decrease the child count
		parent->children[parent->childCount] = nullptr; // Clear the last child
		target->parent = nullptr; // Detach the target node from its parent
		return target;
	}

	// overloaded DetachChild function
	template <typename T>
	inline Node<T>* DetachChild(Node<T>* parent, int index)
	{
		if (index < 0)
		{
			return nullptr; // 인덱스가 음수인 경우
		}
		return DetachChild<T>(parent, static_cast<unsigned int>(index));
	}

	// Detach All Children
	// Detach all children from the parent node
	// 모든 자식 노드를 부모 노드에서 분리합니다.
	// 자식 노드가 삭제되지 않습니다.
	template <typename T>
	inline bool DetachAllChildren(Node<T>* parent)
	{
		if (parent == nullptr)
		{
			return false; // 부모 노드가 nullptr인 경우
		}

		for (unsigned int i = 0u; i < parent->childCount; ++i)
		{
			if (parent->children[i] != nullptr)
			{
				parent->children[i]->parent = nullptr; // Detach each child node from its parent
				parent->children[i] = nullptr;
			}
		}
		
		parent->childCount = 0u; // Reset child count

		return true; // Return true to indicate successful detachment
	}

	// Delete Node
	// Use this function to delete a specific node and all its children.
	// The node will be deleted, and all its children will also be deleted recursively.
	// 한글설명 : 처음 만난 특정 노드와 그 자식 노드를 모두 삭제합니다.
	template <typename T>
	inline void DeleteNode(Node<T>*& target)
	{
		if (target == nullptr)
		{
			return; // 노드가 nullptr인 경우
		}

		// Recursively delete all children
		for (unsigned int i = 0u; i < target->childCount; ++i)
		{
			if (target->children[i] != nullptr)
			{
				DeleteNode<T>(target->children[i]); // 자식 서브트리 재귀 삭제
				target->children[i] = nullptr;
			}
		}
		delete[] target->children;	// Delete the children array
		target->children = nullptr; // Clear the pointer to children
		delete target;				// Delete the target node itself
		target = nullptr;			// Clear the target node pointer
	}


	// DeleteChild
	// Use this function to delete a specific child node from the parent node.
	// The child node will be deleted, and remaining child nodes will be shifted to the left to fill the gap.
	// 한글설명 : 부모 노드에서 처음 만난 특정 자식 노드를 삭제합니다.
	// 자식 노드가 삭제되며, 남은 자식 노드를 왼쪽으로 이동하여 빈 공간을 채웁니다.
	template <typename T>
	inline void DeleteChild(Node<T>* parent, Node<T>* target)
	{
		if (parent == nullptr || target == nullptr)
		{
			return; // 부모 노드나 대상 노드가 nullptr인 경우
		}
		int index = -1;
		for (unsigned int i = 0u; i < parent->childCount; ++i)
		{
			if (parent->children[i] == target)
			{
				index = static_cast<int>(i);
				break;
			}
		}
		if (index < 0) 
		{
			return; // Target not found in parent's children
		}

		DeleteNode<T>(target);

		// Shift remaining children to the left
		for (unsigned int j = static_cast<unsigned int>(index); j < parent->childCount - 1u; ++j)
		{
			parent->children[j] = parent->children[j + 1u];
		}
		parent->childCount -= 1u; // Decrease the child count
		parent->children[parent->childCount] = nullptr; // Clear the last child
	}

	// DeleteChild with value
	// Use this function to delete a specific child node with the given value from the parent node.
	// The child node will be deleted, and remaining child nodes will be shifted to the left to fill the gap.
	// 한글설명 : 부모 노드에서 처음 만난 특정 값의 자식 노드를 삭제합니다.
	// 자식 노드가 삭제되며, 남은 자식 노드를 왼쪽으로 이동하여 빈 공간을 채웁니다.
	template <typename T>
	inline void DeleteChild(Node<T>* parent, const T& value)
	{
		if (parent == nullptr)
		{
			return; // 부모 노드가 nullptr인 경우
		}
		int index = -1;
		for (unsigned int i = 0u; i < parent->childCount; ++i)
		{
			// Find the index of the child with the given value 
			if (parent->children[i] && parent->children[i]->data == value)
			{
				index = static_cast<int>(i);
				break;
			}
		}

		if (index < 0)
		{
			return; // Value not found in parent's children
		}
		
		Node<T>* target = parent->children[index];
		DeleteNode<T>(target); // Delete the target node

		// Shift remaining children to the left
		for (unsigned int j = index; j < parent->childCount - 1u; ++j)
		{
			parent->children[j] = parent->children[j + 1u];
		}
		parent->childCount -= 1u; // Decrease the child count
		parent->children[parent->childCount] = nullptr; // Clear the last child
	}

	// DeleteChild with index
	// Use this function to delete a child node at a specific index from the parent node.
	// The child node will be deleted, and remaining child nodes will be shifted to the left to fill the gap.
	// 한글설명 : 부모 노드에서 특정 인덱스의 자식 노드를 삭제합니다.
	// 자식 노드가 삭제되며, 남은 자식 노드를 왼쪽으로 이동하여 빈 공간을 채웁니다.
	template <typename T>
	inline void DeleteChild(Node<T>* parent, unsigned int index)
	{
		if (parent == nullptr || index >= parent->childCount)
		{
			return; // 부모 노드가 nullptr이거나 인덱스가 범위를 벗어난 경우
		}
		
		if (parent->children[index] == nullptr)
		{
			return; // 해당 인덱스에 자식 노드가 없는 경우
		}
		
		Node<T>* target = parent->children[index];
		DeleteNode<T>(target); // Delete the target node
		// Shift remaining children to the left
		for (unsigned int j = index; j < parent->childCount - 1u; ++j)
		{
			parent->children[j] = parent->children[j + 1u];
		}

		parent->childCount -= 1u; // Decrease the child count
		parent->children[parent->childCount] = nullptr; // Clear the last child
	}

	// overloaded DeleteChild function
	template <typename T>
	inline void DeleteChild(Node<T>* parent, int index)
	{
		if (index < 0)
		{
			return; // 인덱스가 음수인 경우
		}
		DeleteChild<T>(parent, static_cast<unsigned int>(index));
	}

	// DeleteAllChildren
	// Use this function to delete all child nodes of a given node.
	// The node itself will not be deleted, only its children will be deleted recursively.
	// 한글설명 : 주어진 노드의 모든 자식 노드를 삭제합니다.
	// 노드 자체는 삭제되지 않으며, 자식 노드만 재귀적으로 삭제됩니다.
	template <typename T>
	inline bool DeleteAllChildren(Node<T>* node)
	{
		if (node == nullptr)
		{
			return false; // 노드가 nullptr인 경우
		}

		for (unsigned int i = 0u; i < node->childCount; ++i) 
		{
			if (node->children[i])
			{
				DeleteNode<T>(node->children[i]); // 하위 전체 삭제
				node->children[i] = nullptr;
			}
		}
		node->childCount = 0u;   // 부모는 유지
		return true; // 모든 자식 노드를 성공적으로 삭제했음을 나타냅니다.
	}
}

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

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

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

 

 

 

 

 

※ 25.08.11 수정 내용

Node의 형태를 순수 데이터인 Struct형태로 변경

이제 노드의 생성 삭제 등은 외부 자료구조에서 관리함.

Node는 단순히 데이터를 저장하고 자신과 다른 노드와의 관계 만을 갖음

 

※ 25.08.12

노드 생성과 자식 삽입, 삭제 헬퍼 함수 범용 함수로 추가 

***다양한 자료구조에서 공통적으로 지원해야 하는 기능이기 때문에 추가함***