APCS程式檢測 -實作題1050305 第4題 血緣關係

發佈留言 / 作者: /

APCS程式檢測 -實作題1050305 第4題 血緣關係

事前準備-樹的資料結構
https://husking-studio.com/apcs-tree/

第一步-先用手動的方式建構樹

#include <iostream>
using namespace std;

//樹的基本結構和功能
void AddChild(int** pTree, int nRow, int nCol, int nParent, int nChild);	//加入節點
int GetLeafNum(int** pTree, int nRow, int nCol);	//取得葉子節點的數量
int FindRoot(int** pTree, int nRow, int nCol);		//找出根節點
int GetChildNum(int** pTree, int nRow, int nCol, int nNode);	//取得某節點的孩子數量
int Distance(int** pTree, int nRow, int nCol, int nNode);	//取得某節點的高度
void PrintTree(int** pTree, int nRow, int nCol);	//印出

int main()
{
	int nTreeRow = 8;
	int nTreeCol = 3;

	//宣告
	int** pTree;
	pTree = new int* [nTreeRow];
	for (int i = 0; i < nTreeRow; i++)
		pTree[i] = new int[nTreeCol];

	//初始化
	for (int i = 0; i < nTreeRow; i++)
		for (int j = 0; j < nTreeCol; j++)
			pTree[i][j] = -1;

	//加入資料
	AddChild(pTree, nTreeRow, nTreeCol, 0, 1);
	AddChild(pTree, nTreeRow, nTreeCol, 0, 2);
	AddChild(pTree, nTreeRow, nTreeCol, 0, 3);
	AddChild(pTree, nTreeRow, nTreeCol, 7, 0);
	AddChild(pTree, nTreeRow, nTreeCol, 1, 4);
	AddChild(pTree, nTreeRow, nTreeCol, 1, 5);
	AddChild(pTree, nTreeRow, nTreeCol, 3, 6);

	//印出
	PrintTree(pTree, nTreeRow, nTreeCol);

	//delete
	for (int i = 0; i < nTreeRow; i++)
		delete[] pTree[i];
	delete[] pTree;

	system("pause");
	return 0;
}
//取得某節點的高度
int Distance(int** pTree, int nRow, int nCol, int nNode)
{
	int nChildNum = GetChildNum(pTree, nRow, nCol, nNode);
	if (nChildNum == 0)
		return 0;

	int nDepthMax = 0;
	int nDepth = 0;
	int* pRow = pTree[nNode];
	for (int k = 0; k < nChildNum; k++)
	{
		nDepth = Distance(pTree, nRow, nCol, pRow[k]) + 1;
		if (nDepth > nDepthMax)
			nDepthMax = nDepth;
	}
	return nDepthMax;
}
//取得某節點的孩子數量
int GetChildNum(int** pTree, int nRow, int nCol, int nNode)
{
	int nChildNum = 0;
	int* pRow = pTree[nNode];

	for (int j = 0; j < nCol; j++)
	{
		if (pRow[j] != -1)
			nChildNum++;
	}
	return nChildNum;
}
//取得葉子節點的數量
int GetLeafNum(int** pTree, int nRow, int nCol)
{
	int nLeafNum = 0;
	bool bHaveChild = false;

	for (int i = 0; i < nRow; i++)
	{
		bHaveChild = false;
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
			{
				bHaveChild = true;
				break;
			}
		}
		if (bHaveChild == false)
			nLeafNum++;
	}
	return nLeafNum;
}
//找出根節點
int FindRoot(int** pTree, int nRow, int nCol)
{
	bool* bNode = new bool[nRow];
	for (int i = 0; i < nRow; i++)
		bNode[i] = false;

	for (int i = 0; i < nRow; i++)
	{
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
				bNode[pTree[i][j]] = true;
		}
	}

	int nRoot = -1;
	for (int i = 0; i < nRow; i++)
	{
		if (bNode[i] == false)
		{
			nRoot = i;
			break;
		}
	}

	delete[] bNode;

	return nRoot;
}
//加入節點
void AddChild(int** pTree, int nRow, int nCol, int nParent, int nChild)
{
	int* pRow = pTree[nParent];

	for (int j = 0; j < nCol; j++)
	{
		if (pRow[j] == -1)
		{
			pRow[j] = nChild;
			break;
		}
	}
}
//印出
void PrintTree(int** pTree, int nRow, int nCol)
{
	for (int i = 0; i < nRow; i++)
	{
		cout << "node(" << i << ")->";
		for (int j = 0; j < nCol; j++)
		{
			cout << pTree[i][j] << " ";
		}
		cout << endl;
	}
}

第二步-思考一下

一般來說，樹結構都是從根節點開始處理資料的，但這題是要找兩個最遠的「葉子節點」，所以我決定反過來思考，從「葉子節點」向上找，直到找到同一個父節點。「把想法逆轉過來」，是我最喜歡的遊戲裡的名言。

第三步-找葉子節點

#include <iostream>
using namespace std;

void SetLeaf(int** pTree, int nRow, int nCol, int* pLeaf);

int main()
{

	//前略

	//找葉子節點，存在 pLeaf 陣列裡
	int nLeafNum = GetLeafNum(pTree, nTreeRow, nTreeCol);
	int* pLeaf = new int[nLeafNum];
	SetLeaf(pTree, nTreeRow, nTreeCol, pLeaf);


	//印出檢查
	for (int i = 0; i < nLeafNum; i++)
		cout << pLeaf[i] << " ";
	cout << endl;

	//delete
	delete[] pLeaf;

	//後略
}
void SetLeaf(int** pTree, int nRow, int nCol, int* pLeaf)
{
	int k = 0;
	bool bAll = true;

	for (int i = 0; i < nRow; i++)
	{
		bAll = true;
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
			{
				bAll = false;
				break;
			}
		}
		if (bAll)
		{
			pLeaf[k] = i;
			k++;
		}
	}
}

第四步-建立從葉子節點向上找的表格

#include <iostream>
using namespace std;

void SetParent(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol);
void FindParent(int** pTree, int nRow, int nCol, int nChild, int* pParent, int nParentRow, int nParentCol, int k);

int main()
{
	//前略

	//找根節點
	int nRoot = FindRoot(pTree, nTreeRow, nTreeCol);
	//深度
	int nDepth = Distance(pTree, nTreeRow, nTreeCol, nRoot);

	//父連結
	int nParentTreeRow = nTreeRow;
	int nParentTreeCol = nDepth;

	//建立父連結資料
	int** pParentTree;
	pParentTree = new int* [nParentTreeRow];
	for (int i = 0; i < nParentTreeRow; i++)
		pParentTree[i] = new int[nParentTreeCol];

	//初始化
	for (int i = 0; i < nParentTreeRow; i++)
		for (int j = 0; j < nParentTreeCol; j++)
			pParentTree[i][j] = -1;

	//建立父連結陣列
	SetParent(pTree, nTreeRow, nTreeCol, pParentTree, nParentTreeRow, nParentTreeCol);

	//印出
	PrintTree(pParentTree, nParentTreeRow, nParentTreeCol);

	//delete
	for (int i = 0; i < nParentTreeRow; i++)
		delete[] pParentTree[i];
	delete[] pParentTree;

	//後略
}
void SetParent(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol)
{
	int k = 0;
	for (int i = 0; i < nRow; i++)
	{
		k = 0;
		FindParent(pTree, nRow, nCol, i, pParentTree[i], nParentRow, nParentCol, k);
	}
}
void FindParent(int** pTree, int nRow, int nCol, int nChild, int* pParent, int nParentRow, int nParentCol, int k)
{
	bool bFind = false;
	for (int i = 0; i < nRow; i++)
	{
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] == nChild)
			{
				bFind = true;
				pParent[k] = i;
				FindParent(pTree, nRow, nCol, i, pParent, nParentRow, nParentCol, k + 1);
			}
		}
	}
	if (bFind == false)
		return;
}

第五步-從葉子節點中捉對找共同父節點和距離

#include <iostream>
using namespace std;

int GetMaxDistance(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum);
int GetPairDistance(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB);

int main()
{
	//前略

	//取得最遠的葉子節點距離
	int nDistance = GetMaxDistance(pParentTree, nParentTreeRow, nParentTreeCol, pLeaf, nLeafNum);
	cout << nDistance << endl;

	//後略
}
int GetPairDistance(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB)
{
	int* pRowA = pParentTree[nA];
	int* pRowB = pParentTree[nB];
	int nMaxDistance = 0;
	int nTempDistance = 0;

	int a2 = 0;
	int b2 = 0;

	bool bFind = false;

	for (int a = 0; a < nParentCol; a++)
	{
		for (int b = 0; b < nParentCol; b++)
		{
			if (pRowA[a] == pRowB[b])		//找共同父節點
			{
				a2 = a + 1;
				b2 = b + 1;

				bFind = true;
				break;
			}
		}
		if (bFind)
			break;
	}

	if (bFind)
	{
		nTempDistance = a2 + b2;
		if (nTempDistance > nMaxDistance)
			nMaxDistance = nTempDistance;
	}

	cout << endl;

	return nMaxDistance;
}
int GetMaxDistance(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum)
{
	int nMaxDistance = 0;
	int nTempDistance = 0;

	//在葉子節點中捉對
	for (int i = 0; i < nLeafNum; i++)
	{
		for (int j = i + 1; j < nLeafNum; j++)
		{
			nTempDistance = GetPairDistance(pParentTree, nParentRow, nParentCol, pLeaf[i], pLeaf[j]);
			if (nTempDistance > nMaxDistance)
				nMaxDistance = nTempDistance;
		}
	}
	return nMaxDistance;
}

完整程式碼

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

//樹的基本結構和功能
void AddChild(int** pTree, int nRow, int nCol, int nParent, int nChild);	//加入節點
int GetLeafNum(int** pTree, int nRow, int nCol);	//取得葉子節點的數量
int FindRoot(int** pTree, int nRow, int nCol);		//找出根節點
int GetChildNum(int** pTree, int nRow, int nCol, int nNode);	//取得某節點的孩子數量
int Distance(int** pTree, int nRow, int nCol, int nNode);	//取得某節點的高度
void PrintTree(int** pTree, int nRow, int nCol);	//印出

//
void SetLeaf(int** pTree, int nRow, int nCol, int* pLeaf);
void SetParent(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol);
void FindParent(int** pTree, int nRow, int nCol, int nChild, int* pParent, int nParentRow, int nParentCol, int k);
int GetMaxDistance(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum);
int GetPairDistance(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB);

int main()
{
	//處理輸入-n個節點
	string strInput;
	getline(cin, strInput);
	int n = stoi(strInput);

	//
	int* nChildNum = new int[n];
	for (int i = 0; i < n; i++)
		nChildNum[i] = 0;

	//將接下來的輸入存在 vector 裡
	vector<string> vecInput;
	for (int i = 0; i < (n - 1); i++)
	{
		int nParentNode = -1;
		getline(cin, strInput);

		stringstream delim(strInput);
		string pch;

		getline(delim, pch, ' ');
		nParentNode = stoi(pch);

		getline(delim, pch, ' ');

		nChildNum[nParentNode]++;
		vecInput.push_back(strInput);
	}
	//
	int nMaxChildNum = 0;
	for (int i = 0; i < n; i++)
	{
		if (nChildNum[i] > nMaxChildNum)
			nMaxChildNum = nChildNum[i];
	}

	delete[] nChildNum;

	//
	int nTreeRow = n;
	int nTreeCol = nMaxChildNum;

	//宣告
	int** pTree;
	pTree = new int* [nTreeRow];
	for (int i = 0; i < nTreeRow; i++)
		pTree[i] = new int[nTreeCol];

	//初始化
	for (int i = 0; i < nTreeRow; i++)
		for (int j = 0; j < nTreeCol; j++)
			pTree[i][j] = -1;

	//加入資料
	for (int i = 0; i < (int)vecInput.size(); i++)
	{
		int nParentNode = -1;
		int nChildNode = -1;

		stringstream delim(vecInput[i]);
		string pch;

		getline(delim, pch, ' ');
		nParentNode = stoi(pch);

		getline(delim, pch, ' ');
		nChildNode = stoi(pch);

		AddChild(pTree, nTreeRow, nTreeCol, nParentNode, nChildNode);
	}

	//找葉子節點，存在 pLeaf 陣列裡
	int nLeafNum = GetLeafNum(pTree, nTreeRow, nTreeCol);
	int* pLeaf = new int[nLeafNum];
	SetLeaf(pTree, nTreeRow, nTreeCol, pLeaf);

	//找根節點
	int nRoot = FindRoot(pTree, nTreeRow, nTreeCol);
	//深度
	int nDepth = Distance(pTree, nTreeRow, nTreeCol, nRoot);

	//父連結
	int nParentTreeRow = nTreeRow;
	int nParentTreeCol = nDepth;

	//建立父連結資料
	int** pParentTree;
	pParentTree = new int* [nParentTreeRow];
	for (int i = 0; i < nParentTreeRow; i++)
		pParentTree[i] = new int[nParentTreeCol];

	//初始化
	for (int i = 0; i < nParentTreeRow; i++)
		for (int j = 0; j < nParentTreeCol; j++)
			pParentTree[i][j] = -1;

	//建立父連結陣列
	SetParent(pTree, nTreeRow, nTreeCol, pParentTree, nParentTreeRow, nParentTreeCol);

	//取得最遠的葉子節點距離
	int nDistance = GetMaxDistance(pParentTree, nParentTreeRow, nParentTreeCol, pLeaf, nLeafNum);
	cout << nDistance << endl;

	//delete
	for (int i = 0; i < nParentTreeRow; i++)
		delete[] pParentTree[i];
	delete[] pParentTree;
	delete[] pLeaf;
	for (int i = 0; i < nTreeRow; i++)
		delete[] pTree[i];
	delete[] pTree;

	system("pause");
	return 0;
}
int GetPairDistance(int** pParentTree, int nParentRow, int nParentCol, int nA, int nB)
{
	int* pRowA = pParentTree[nA];
	int* pRowB = pParentTree[nB];
	int nMaxDistance = 0;
	int nTempDistance = 0;

	int a2 = 0;
	int b2 = 0;

	bool bFind = false;

	for (int a = 0; a < nParentCol; a++)
	{
		for (int b = 0; b < nParentCol; b++)
		{
			if (pRowA[a] == pRowB[b])		//找共同父節點
			{
				a2 = a + 1;
				b2 = b + 1;

				bFind = true;
				break;
			}
		}
		if (bFind)
			break;
	}

	if (bFind)
	{
		nTempDistance = a2 + b2;
		if (nTempDistance > nMaxDistance)
			nMaxDistance = nTempDistance;
	}

	return nMaxDistance;
}
int GetMaxDistance(int** pParentTree, int nParentRow, int nParentCol, int* pLeaf, int nLeafNum)
{
	int nMaxDistance = 0;
	int nTempDistance = 0;

	//在葉子節點中捉對
	for (int i = 0; i < nLeafNum; i++)
	{
		for (int j = i + 1; j < nLeafNum; j++)
		{
			nTempDistance = GetPairDistance(pParentTree, nParentRow, nParentCol, pLeaf[i], pLeaf[j]);
			if (nTempDistance > nMaxDistance)
				nMaxDistance = nTempDistance;
		}
	}
	return nMaxDistance;
}
void SetParent(int** pTree, int nRow, int nCol, int** pParentTree, int nParentRow, int nParentCol)
{
	int k = 0;
	for (int i = 0; i < nRow; i++)
	{
		k = 0;
		FindParent(pTree, nRow, nCol, i, pParentTree[i], nParentRow, nParentCol, k);
	}
}
void FindParent(int** pTree, int nRow, int nCol, int nChild, int* pParent, int nParentRow, int nParentCol, int k)
{
	bool bFind = false;
	for (int i = 0; i < nRow; i++)
	{
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] == nChild)
			{
				bFind = true;
				pParent[k] = i;
				FindParent(pTree, nRow, nCol, i, pParent, nParentRow, nParentCol, k + 1);
			}
		}
	}
	if (bFind == false)
		return;
}
void SetLeaf(int** pTree, int nRow, int nCol, int* pLeaf)
{
	int k = 0;
	bool bAll = true;

	for (int i = 0; i < nRow; i++)
	{
		bAll = true;
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
			{
				bAll = false;
				break;
			}
		}
		if (bAll)
		{
			pLeaf[k] = i;
			k++;
		}
	}
}
//取得某節點的高度
int Distance(int** pTree, int nRow, int nCol, int nNode)
{
	int nChildNum = GetChildNum(pTree, nRow, nCol, nNode);
	if (nChildNum == 0)
		return 0;

	int nDepthMax = 0;
	int nDepth = 0;
	int* pRow = pTree[nNode];
	for (int k = 0; k < nChildNum; k++)
	{
		nDepth = Distance(pTree, nRow, nCol, pRow[k]) + 1;
		if (nDepth > nDepthMax)
			nDepthMax = nDepth;
	}
	return nDepthMax;
}
//取得某節點的孩子數量
int GetChildNum(int** pTree, int nRow, int nCol, int nNode)
{
	int nChildNum = 0;
	int* pRow = pTree[nNode];

	for (int j = 0; j < nCol; j++)
	{
		if (pRow[j] != -1)
			nChildNum++;
	}
	return nChildNum;
}
//取得葉子節點的數量
int GetLeafNum(int** pTree, int nRow, int nCol)
{
	int nLeafNum = 0;
	bool bHaveChild = false;

	for (int i = 0; i < nRow; i++)
	{
		bHaveChild = false;
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
			{
				bHaveChild = true;
				break;
			}
		}
		if (bHaveChild == false)
			nLeafNum++;
	}
	return nLeafNum;
}
//找出根節點
int FindRoot(int** pTree, int nRow, int nCol)
{
	bool* bNode = new bool[nRow];
	for (int i = 0; i < nRow; i++)
		bNode[i] = false;

	for (int i = 0; i < nRow; i++)
	{
		for (int j = 0; j < nCol; j++)
		{
			if (pTree[i][j] != -1)
				bNode[pTree[i][j]] = true;
		}
	}

	int nRoot = -1;
	for (int i = 0; i < nRow; i++)
	{
		if (bNode[i] == false)
		{
			nRoot = i;
			break;
		}
	}

	delete[] bNode;

	return nRoot;
}
//加入節點
void AddChild(int** pTree, int nRow, int nCol, int nParent, int nChild)
{
	int* pRow = pTree[nParent];

	for (int j = 0; j < nCol; j++)
	{
		if (pRow[j] == -1)
		{
			pRow[j] = nChild;
			break;
		}
	}
}
//印出
void PrintTree(int** pTree, int nRow, int nCol)
{
	for (int i = 0; i < nRow; i++)
	{
		cout << "node(" << i << ")->";
		for (int j = 0; j < nCol; j++)
		{
			cout << pTree[i][j] << " ";
		}
		cout << endl;
	}
}

進階思考-印出路徑
https://husking-studio.com/apcs-1050305-4-2/

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *