Tree

오늘은 Tree이다.

Tree란, 쉽게 말해 부모와 자식 노드간의 관계를 가지지만 부모는 절대적으로 1개인 자료구조이다.

(Cycle이 존재 하지 않는다)

이것이 무슨 의미를 가지는지는 아래와 같다.

탐색의 방향이 정해져있다. 위, 아래 어느 방향이던 손쉽게 행적을 추적할 수 있다.

사실 Tree구조란것은 특징별로 다양하게 파생되어 순수 Tree는 사용할 일이 적다.

https://en.wikipedia.org/wiki/Tree_(data_structure)

다양한 Tree중 대표적인게 Binary Tree로 자식을 최대 2개까지만 허용하는 Tree이다.

특징은 아래에서 찾을 수 있다.

https://www.cs.auckland.ac.nz/software/AlgAnim/trees.html

AVL Tree, B- Tree, B+ Tree,  red-black Tree 종류도 많다...

http://www.i-programmer.info/babbages-bag/477-trees.html?start=2

Tree종류는 입맛대로 사용하면 된다.

필수적인 메소드는 Insertion, Removal이며 명령 후에도 Tree의 고유 성질을 만족하는게 중요하다.

#include 

class TreeNode
{
public:
	TreeNode(){
		Value = 0;
		Parent = NULL;
		Childs = NULL;
	}
	TreeNode(int _value, TreeNode *_parent){
		Value = _value;
		Parent = _parent;
		Childs = NULL;
	}
public:
	int Value;
	TreeNode *Parent;
	TreeNode **Childs;
};
class myTree
{
public:
	myTree(int rootValue){
		root = new TreeNode(rootValue, NULL);
	}
private:
	TreeNode* root;
public:
	TreeNode* getRoot(){ return root; }
	virtual bool Insertion(int Value) = 0;
	virtual bool Removal(int Value) = 0;
	virtual bool isFind(int Value) = 0;
};

class LCRS_Tree :public myTree
{
public:
	LCRS_Tree(int rootValue) : myTree(rootValue){ }
public:
	TreeNode* appendChildNode(TreeNode* _parent,int _value){
		TreeNode *current = new TreeNode(_value, _parent);
		if (_parent->Childs == NULL){
			_parent->Childs = new TreeNode*[2];
			_parent->Childs[0] = _parent->Childs[1] = NULL;
		}
		_parent->Childs[0] = current;
		return current;
	}
	TreeNode* appendSiblingNode(TreeNode* _parent, int _value){
		TreeNode *current = new TreeNode(_value, _parent);
		if (_parent->Childs == NULL){
			_parent->Childs = new TreeNode*[2];
			_parent->Childs[0] = _parent->Childs[1] = NULL;
		}
		_parent->Childs[1] = current;
		return current;
	}
	bool Insertion(int Value){ return true; }
	bool Removal(int Value){ return true; }
	bool isFind(int Value){
		TreeNode* stack[255];
		int cpt, lpt;
		cpt = lpt = 0;
		stack[lpt++] = getRoot();

		while (cptValue == Value)
				return true;
			else
			{
				if (currentNode->Childs[0] != NULL)
					stack[lpt++] = currentNode->Childs[0];
				if (currentNode->Childs[1] != NULL)
					stack[lpt++] = currentNode->Childs[1];
			}
			++cpt;
		}
		return false;
	}
};

#include "myTree.h"

int main()
{
	LCRS_Tree* lt = new LCRS_Tree(1);

	TreeNode * nTN = lt->appendChildNode(lt->getRoot(), 3);
	nTN = lt->appendChildNode(nTN, 5);
	nTN = lt->appendChildNode(nTN, 8);

	printf("%s\n",(lt->isFind(8))?"FIND":"NOFIND");

	delete(lt);
	return 0;
}