[C++ 쉽게 풀어쓴 자료구조] 프로그래밍 프로젝트 8

완전 이진트리 검사 함수 구현

• 완전 이진트리란 높이n 의 트리에서 n-1레벨까지는 포화상태, n레벨의 노드들은 왼쪽부터 채워져 있는 상태인 이진트리를 의미한다.
• 완전 이진트리 검사는 레벨 순회를 통해 구현했다.
• Left와 Right중 하나라도 null node일 경우, 그 이후 나타나는 노드들은 모든 노드가 단말노드여야 한다.

bool CBinaryTree::IsFull()
{
	std::queue<CBinaryNode*> bQueue;
	bQueue.push(m_Root);

	while (!bQueue.empty())
	{
		bool meetNotFull = false;
		CBinaryNode* node = bQueue.front();

		// full node라면 계속 탐색한다.
		if (node->GetLeft() && node->GetRight())
		{
			bQueue.push(node->GetLeft());
			bQueue.push(node->GetRight());
			bQueue.pop();
		}
		else
		{
			// Full Node가 아닌 노드를 만났을 경우, 모든 노드가 단말 노드여야 한다.
			if (meetNotFull)
			{
				if (!node->IsLeaf())
					return false;
			}
			else
			{
				// 오른쪽만 있는 노드가 존재하면 완전 이진트리가 아니다
				if (!node->GetLeft() && node->GetRight())
					return false;

				// Full Node가 아닌 Node를 처음 만남
				meetNotFull = true;

				if (node->GetLeft())
					bQueue.push(node->GetLeft());

				bQueue.pop();
			}
		}
	}

	return true;
}

---

임의의 노드 레벨 구하기

• level n 인 트리는 2^(n-1)개의 노드 이상을 가질 수 없다는 성질을 이용해 레벨을 구할 수 있다.

int CBinaryTree::GetLevel(CBinaryNode* node)
{
	if (!m_Root)
		return 0;

	int level = 1;
	int	nodeCount = 0;
	std::queue<CBinaryNode*> nodeQueue;
	nodeQueue.push(m_Root);

	// 레벨 순회
	while (!nodeQueue.empty())
	{
		++nodeCount;

		CBinaryNode* curNode = nodeQueue.front();

		// level의 높이를 가진 트리가 가질 수 있는 최대 노드 개수를 넘어간 경우
		if (pow(2, level) <= nodeCount)
		{
			++level;
		}

		if (curNode == node)
			return level;

		if (curNode->GetLeft())
			nodeQueue.push(curNode->GetLeft());

		if (curNode->GetRight())
			nodeQueue.push(curNode->GetRight());

		nodeQueue.pop();
	}

	return 0;
}

---

이진트리 균형 여부

• 재귀적으로 구현했다.

bool CBinaryTree::IsBalanced()
{
	if (!m_Root)
		return false;

	return m_Root->IsBalanced();
}

bool CBinaryNode::IsBalanced()
{
	bool balanced = true;

	int rLevel = 0;
	int lLevel = 0;

	if (m_Left)
		lLevel = m_Left->GetLevel();

	if (m_Right)
		rLevel = m_Right->GetLevel();

	// 레벨차가 2 이상으로 나는 경우
	if (abs(lLevel - rLevel) > 1)
		return false;

	// 자식 노드도 판별한다.
	if (m_Left)
		balanced = m_Left->IsBalanced();

	if (!balanced)
		return false;

	if (m_Right)
		balanced = m_Right->IsBalanced();

	return true;
}

---

경로의 길이 합

• 이또한 재귀적으로 구현했다.
• 노드가 자식 노드들의 경로의 합을 구해서 리턴하도록

int CBinaryTree::GetPathLength()
{
	if (!m_Root)
		return false;

	return m_Root->GetPathLength(1);
}

int CBinaryNode::GetPathLength(int Level)
{
	std::cout << " Data : " << m_Data << " ";

	if (!m_Left && !m_Right)
		return 0;

	if (m_Left && m_Right)
		return ((Level * 2) + m_Left->GetPathLength(Level + 1) + m_Right->GetPathLength(Level + 1));

	if (m_Left)
		return Level + m_Left->GetPathLength(Level + 1);

	if (m_Right)
		return Level + m_Right->GetPathLength(Level + 1);
}

---

이진트리 좌우반전

• 가장 쉬웠다. 그냥 자식들 먼저 스왑해주고 자신의 left right노드를 스왑해주면 끝

bool CBinaryNode::Swap()
{
	bool swap = true;

	if (m_Left)
		swap = m_Left->Swap();

	if (m_Right)
		swap = m_Right->Swap();

	CBinaryNode* temp = m_Left;
	m_Left = m_Right;
	m_Right = temp;

	return true;
}

---

현재 트리와 다른 트리 분리되어있는지 확인 (Disjoint)

• 순환적으로 구현하라고 해서 레벨순회하면서 노드별로 other tree가 해당 노드를 포함하고 있는지 확인하도록 했다

bool CBinaryTree::IsDisjointFrom(CBinaryTree* tree)
{
	if (!m_Root)
	{
		return true;
	}

	std::queue<CBinaryNode*> nodeQueue;
	nodeQueue.push(m_Root);

	while (!nodeQueue.empty())
	{
		CBinaryNode* curNode = nodeQueue.front();

		// other 트리가 현재 노드를 포함하고 있는지 확인
		if (tree->Include(curNode))
			return false;

		if (curNode->GetLeft())
			nodeQueue.push(curNode->GetLeft());

		if (curNode->GetRight())
			nodeQueue.push(curNode->GetRight());

		nodeQueue.pop();
	}

	return true;
}

bool CBinaryTree::Include(CBinaryNode* node)
{
	if (!m_Root)
		return false;

	std::queue<CBinaryNode*> nodeQueue;
	nodeQueue.push(m_Root);

	while (!nodeQueue.empty())
	{
		CBinaryNode* curNode = nodeQueue.front();

		if (curNode == node)
			return true;

		if (curNode->GetLeft())
			nodeQueue.push(curNode->GetLeft());

		if (curNode->GetRight())
			nodeQueue.push(curNode->GetRight());

		nodeQueue.pop();
	}

	return false;
}

---

모든 서브트리가 분리되어있는지(Valid) 확인

• 서브트리가 분리되어 있는지 확인하고, 그 서브트리들의 서브트리들도 서로 분리되어있는지 확인해야 한다.
• 따라서 재귀적으로 구현

bool CBinaryTree::IsValid()
{
	if (!m_Root)
		return true;

	bool valid = true;

	std::queue<CBinaryNode*> nodeQueue;
	nodeQueue.push(m_Root);

	while (!nodeQueue.empty())
	{
		CBinaryNode* curNode = nodeQueue.front();

		// left right 둘 다 있는 경우 Disjoint한지 확인한다.
		if (curNode->GetRight() && curNode->GetLeft())
		{
			CBinaryTree leftTree;
			leftTree.SetRoot(curNode->GetLeft());

			CBinaryTree rightTree;
			rightTree.SetRoot(curNode->GetRight());

			if (!leftTree.IsDisjointFrom(&rightTree))
				return false;
		}

		// left right가 Disjoint 하다면 left right가 각자 Valid한지 검사
		if (curNode->GetLeft())
		{
			CBinaryTree leftTree;
			leftTree.SetRoot(curNode->GetLeft());

			if (!leftTree.IsValid())
				return false;

			nodeQueue.push(curNode->GetLeft());
		}

		if (curNode->GetRight())
		{
			CBinaryTree rightTree;
			rightTree.SetRoot(curNode->GetRight());

			if (!rightTree.IsValid())
				return false;

			nodeQueue.push(curNode->GetRight());
		}

		nodeQueue.pop();
	}

	return true;
}

---

트리를 공부하면서 재귀적으로 구현해야 할 것들이 많아 문제를 잘게 쪼개서 보아야 잘 풀리는 것들이 많았다.