[C++] Tree

※ 무엇인가

초,중학생 때 경우의 수를 배울 때, 가지를 치면서 모든 경우를 셋었던 기억이 있다.

상위 개념에서 하위 개념으로 뻗어나가며 그리다 보면, 나무의 형상을 하게되는..

그 때 배웠던 내용이 트리와 매우 유사 했다. (같다 해야 하나?)

무튼 트리는 이전에 했던 스택 큐과 같은 선형 구조가 아닌

비 선형 구조이다. 하나의 노드가 이전과 다음 노드에 연결 되있는 것을 넘어서

동일한 위상에 새 노드가 생성 될 수 있다.

가족에 비유하면 A는 B의 자식인데 동생 C가 생긴것

이 때 A와 C의 관계를 여기서 sibling 이라 부른다.

A는 C를 포인터로 가리킬 것임

 

트리에서 각 노드는 여러 자식을 둘 수 있으므로

각 노드가 리스트를 가질 수 있음.

그 리스트는 시작(왼쪽이라 가정)부터 sibling 여부를 파악하며

만약 다음 sibling이 없으면 새로 sibling을 생성.  

※ 코드

<Tree.h>

#pragma once
#include <stdio.h>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
template<typename T>
class Tree
{
public:
	struct Node;

public:
	void AddChild(Node* parent, Node* child)//부모의 자식을 추가 왼쪽에서 오른쪽으로 채움
	{
		if (parent->LeftChild == NULL)
		{
			parent->LeftChild = child;

			return;
		}

		Node* node = parent->LeftChild;
		while (node->RightSibling != NULL)
			node = node->RightSibling;
		node->RightSibling = child;
	}

	void PrintNode(Node* node, int depth)
	{
		for (int i = 0; i < depth; i++)
			cout << "-";

		cout << node->Data << endl;
		stack.push(node);
		queue.push(node->Data);

		if (node->LeftChild != NULL)//자식이 있으면 sibling 전에 자식 먼저 출력, 재귀
			PrintNode(node->LeftChild, depth + 1);

		if (node->RightSibling != NULL)
			PrintNode(node->RightSibling, depth);
	}

public:
	static Node* CreateNode(T data)
	{
		Node* node = new Node();
		node->Data = data;
		node->LeftChild = node->RightSibling = NULL;

		return node;
	}

	static void DestroyNode(Node** node)
	{
		delete* node;
		*node = NULL;
	}
	
public:
	stack<Node*>*Stack() { return &stack; }
	queue<T>*Queue() { return &queue; }
public:
	struct Node
	{
		T Data;

		Node* LeftChild;
		Node* RightSibling;

		~Node()
		{
			Data = 0;
			LeftChild = NULL;
			RightSibling = NULL;
		}
	};


private:
	stack<Node*> stack;
	queue<T> queue;
};

 

<main.cpp>

#include "Tree.h"
int main()
{
	Tree<char> tree;

	Tree<char>::Node* A = Tree<char>::CreateNode('A');
	Tree<char>::Node* B = Tree<char>::CreateNode('B');
	Tree<char>::Node* C = Tree<char>::CreateNode('C');
	Tree<char>::Node* D = Tree<char>::CreateNode('D');
	Tree<char>::Node* E = Tree<char>::CreateNode('E');
	Tree<char>::Node* F = Tree<char>::CreateNode('F');
	Tree<char>::Node* G = Tree<char>::CreateNode('G');
	Tree<char>::Node* H = Tree<char>::CreateNode('H');
	Tree<char>::Node* I = Tree<char>::CreateNode('I');
	Tree<char>::Node* J = Tree<char>::CreateNode('J');
	Tree<char>::Node* K = Tree<char>::CreateNode('K');

	tree.AddChild(A, B);
	tree.AddChild(B, C);
	tree.AddChild(B, D);
	tree.AddChild(D, E);
	tree.AddChild(D, F);

	tree.AddChild(A, G);
	tree.AddChild(G, H);

	tree.AddChild(A, I);
	tree.AddChild(I, K);

	tree.PrintNode(A, 0);

	cout << endl <<endl;


	while (tree.Queue()->empty() == false)
	{
		cout << tree.Queue()->front() << endl;
		tree.Queue()->pop();
	}
	cout << endl << endl;

	while (tree.Stack()->empty() == false)
	{
		Tree<char>::Node* node = tree.Stack()->top();
		tree.Stack()->pop();
		//Tree<char>::DestroyNode(&node);

		int a = 0;
	}
	
	
	return 0;
}