14. 이진트리 - a. 완전이진트리(구현)

완전이진트리

  # 기본적인 형태만 잡은 것으로 데이터의 삽입과 삭제는 마지막 노드에 대해서만 이루어진다고 가정했다.

  # 배열 기반 완전이진트리의 순회를 구현하는데 중점을 두었다.

  # 완전이진트리를 Absolute Binary Tree라고 생각하고 ABT라고 썼는데 CBT가 맞음... (...)

C++로 구현한 배열 기반 완전이진트리

#pragma once
#include <math.h>

template <typename T>
class ABT_array
{
	T* capacity;
	int size;

	int iLastIndex;

	T tRet;

	int OrderIndex;

private:
	int   ParentIndex(int index); // 지정한 노드의 부모 노드의 인덱스를 반환
	int   LeftIndex(int index);   // 지정한 노드의 왼쪽 노드의 인덱스를 반환
	int   RightIndex(int index);  // 지정한 노드의 오른쪽 노드의 인덱스를 반환

	// 인덱스를 받아 재귀호출을 하며 노드를 저장한다.
	bool     PreOrder(int index, T* tArray);
	bool     InOrder(int index, T* tArray);
	bool     PostOrder(int index, T* tArray);

public:
	bool AddNode(T data);
	bool DelNode();
	bool ChangeNode(int index, T data);

	T&   CheckNode(int index);

	int  Count();

	// 트리 탐색 방법들
	//결과를 담을 배열을 인수로 받는다.
	void  LevelOrderTD(T* tArray); 
	void  LevelOrderBU(T* tArray);
	void  PreInPost(T* tArray, int select); //select 값에 따라 pre, in, post order를 수행한다.

public:
	ABT_array(int size);
	virtual ~ABT_array();
};

//------------------------>

//private Function
// 지정한 노드의 부모 노드의 인덱스를 반환, -1은 없음을 의미.
template <typename T>
int   ABT_array<T>::ParentIndex(int index)
{
	if (index == 0) {
		return -1;
	}

	return (index - 1) / 2;
}

// 지정한 노드의 왼쪽 노드의 인덱스를 반환, -1은 없음을 의미.
template <typename T>
int   ABT_array<T>::LeftIndex(int index)
{
	int iRet = index * 2 + 1;

	if (iRet >= iLastIndex) {
		return -1;
	}

	return iRet;
}

// 지정한 노드의 오른쪽 노드의 인덱스를 반환, -1은 없음을 의미.
template <typename T>
int   ABT_array<T>::RightIndex(int index)
{
	int iRet = index * 2 + 2;

	if (iRet >= iLastIndex) {
		return -1;
	}

	return iRet;
}

// 인덱스를 받아 재귀호출을 하며 노드를 저장한다.
template <typename T>
bool ABT_array<T>::PreOrder(int index, T* tArray)
{
	if (index != -1) {
		tArray[OrderIndex++] = capacity[index];
		PreOrder(LeftIndex(index), tArray);
		PreOrder(RightIndex(index), tArray);
		return true;
	}

	return false;
}

template <typename T>
bool ABT_array<T>::InOrder(int index, T* tArray)
{
	if (index != -1) {
		InOrder(LeftIndex(index), tArray);
		tArray[OrderIndex++] = capacity[index];
		InOrder(RightIndex(index), tArray);
	}

	return false;
}

template <typename T>
bool ABT_array<T>::PostOrder(int index, T* tArray)
{
	if (index != -1) {
		PostOrder(LeftIndex(index), tArray);
		PostOrder(RightIndex(index), tArray);
		tArray[OrderIndex++] = capacity[index];
	}

	return false;
}

//---------------------------->
//Public Function
template <typename T>
ABT_array<T>::ABT_array(int _size)
{
	size = _size;
	capacity = new T[size];
	iLastIndex = 0;
	OrderIndex = 0;
}


template <typename T>
bool ABT_array<T>::AddNode(T data)
{
	if (iLastIndex == size) {
		return false;
	}

	capacity[iLastIndex++] = data;

	return true;
}

template <typename T>
bool ABT_array<T>::DelNode()
{
	if (iLastIndex == 0) {
		return false;
	}

	iLastIndex--;

	return true;
}

template <typename T>
bool ABT_array<T>::ChangeNode(int index, T data)
{
	if (index < 0 && index >= iLastIndex) {
		return false;
	}

	capacity[index] = data;

	return true;
}



template <typename T>
T& ABT_array<T>::CheckNode(int index)
{
	if (index >= 0 && index < iLastIndex) {
		tRet = capacity[index];
		return tRet;
	}
	else {
		return nullptr;
	}
}

template <typename T>
int  ABT_array<T>::Count()
{
	return iLastIndex;
}



// 결과를 담을 배열을 인수로 받는다. 
template <typename T>
void ABT_array<T>::LevelOrderTD(T* tArray)
{
	for (int i = 0; i < iLastIndex; i++) {
		tArray[i] = capacity[i];
	}
}

template <typename T>
void ABT_array<T>::LevelOrderBU(T* tArray)
{
	int depth = 0;
	int depthCheck = 0;

	while (iLastIndex-1 > depthCheck) {
		depth++;
		depthCheck += pow(2, depth);
	}

	int tIndex = 0;
	for (int i = depth; i >= 0; i--) {
		depthCheck -= pow(2, i);
		for (int k = 1; k <= pow(2, i); k++) {
			tArray[tIndex] = capacity[depthCheck+k];
			tIndex++;
		}
	}

}

//select 값에 따라 pre, in, post order를 수행한다.
template <typename T>
void  ABT_array<T>::PreInPost(T* tArray, int select)
{
	OrderIndex = 0;
	switch (select) {
		case 1: { PreOrder(0, tArray); } break;

		case 2: { InOrder(0, tArray); } break;

		case 3: { PostOrder(0, tArray);	} break;
	}
}


template <typename T>
ABT_array<T>::~ABT_array()
{

}