APCS程式檢測 -實作樹資料結構

APCS程式檢測 -實作樹資料結構

畢竟 APCS 是給高中生的題目，又有時間的限制，用指標和類別方式來實作的話，我覺得會花上很多時間，所以我決定使用二維陣列的方式來實作樹的資料結構，會比較簡單。用指標和類別方式來實作的程式碼連結在文章最下面。

如果不清楚二維陣列，可以先來這裡看看
https://husking-studio.com/cpp-2d-array/

主程式-完成樹的基本結構和基本功能

#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);	//印出

//
void Test01();
void Test02();

int main()
{
	Test01();
	Test02();

	system("pause");
	return 0;
}
void Test01()
{

}
void Test02()
{

}
//取得某節點的高度
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)
{
	//在整個二維陣列中沒出現的數字就是根節點，因為它不會是任何節點的子節點

	//宣告一個布林值陣列，數量是節點數量，如果這個節點本身是子節點，就設為 true
	bool* bIsChildNode = new bool[nRow];
	for (int i = 0; i < nRow; i++)
		bIsChildNode[i] = false;

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

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

	delete[] bIsChildNode;

	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;
	}
}

其實樹的功能還要加入取得第幾個子節點、取得父節點..等等的功能，但因為目前遇到的題目還用不到，各位可自行練習添加。另外，也因為是使用二維陣列的儲存方法，取得父節點的功能會稍麻煩一點。

參考題目 「實作題1050305 第4題 血緣關係」 來測試結構

測試程式1

void Test01()
{
	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);

	//
	int nRoot = FindRoot(pTree, nTreeRow, nTreeCol);
	cout << "root = " << nRoot << endl;

	//
	int nDepth = Distance(pTree, nTreeRow, nTreeCol, nRoot);
	cout << "depth = " << nDepth << endl;

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

執行結果

測試程式2

void Test02()
{
	int nTreeRow = 4;
	int nTreeCol = 2;

	//宣告
	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, 2, 3);

	//
	PrintTree(pTree, nTreeRow, nTreeCol);

	//
	int nRoot = FindRoot(pTree, nTreeRow, nTreeCol);
	cout << "root = " << nRoot << endl;

	//
	int nDepth = Distance(pTree, nTreeRow, nTreeCol, nRoot);
	cout << "depth = " << nDepth << endl;

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

執行結果

實作題
APCS程式檢測 -實作題1061028 第3題 樹狀圖分析
https://husking-studio.com/apcs-1061028-3/

實作題
APCS程式檢測 -實作題1050305 第4題 血緣關係
https://husking-studio.com/apcs-1050305-4/

延伸閱讀
用指標、類別、template 製作的樹資料結構
https://husking-studio.com/cpp-data-structure-tree-01/