APCS程式檢測 -實作題1061028 第3題 樹狀圖分析

APCS程式檢測 -實作題1061028 第3題 樹狀圖分析

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

雖然已經先準備好了樹的資料結構，但仔細看題目卻發現一個問題，我們的資料結構裡的節點編號是從 0 開始算的，但這題的節點編號是從 1 開始，在不影響資料結構邏輯與題意的前提下，我們用函式來處理編號轉換的問題。

//處理轉換
void AddChild2(int** pTree, int nRow, int nCol, int nParent2, int nChild2);
int FindRoot2(int** pTree, int nRow, int nCol);
int Distance2(int** pTree, int nRow, int nCol, int nNode2);
void PrintTree2(int** pTree, int nRow, int nCol);	//印出

//處理轉換
void AddChild2(int** pTree, int nRow, int nCol, int nParent2, int nChild2)
{
	AddChild(pTree, nRow, nCol, nParent2 - 1, nChild2 - 1);
}
int FindRoot2(int** pTree, int nRow, int nCol)
{
	int nRootOrigin = FindRoot(pTree, nRow, nCol);
	return nRootOrigin + 1;
}
int Distance2(int** pTree, int nRow, int nCol, int nNode2)
{
	return Distance(pTree, nRow, nCol, nNode2 - 1);
}
void PrintTree2(int** pTree, int nRow, int nCol)
{
	for (int i = 0; i < nRow; i++)
	{
		cout << "node(" << i+1 << ")->";
		for (int j = 0; j < nCol; j++)
		{
			cout << pTree[i][j]+1 << " ";
		}
		cout << endl;
	}
}

完整程式碼

#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 AddChild2(int** pTree, int nRow, int nCol, int nParent2, int nChild2);
int FindRoot2(int** pTree, int nRow, int nCol);
int Distance2(int** pTree, int nRow, int nCol, int nNode2);
void PrintTree2(int** pTree, int nRow, int nCol);	//印出

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

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

	//找出 k 的最大值
	int nMaxK = 0;
	int k = 0;
	for (int i = 0; i < (int)vecInput.size(); i++)
	{
		stringstream delim(vecInput[i]);
		string pch;
		getline(delim, pch, ' ');
		k = stoi(pch);
		if (k > nMaxK)
			nMaxK = k;
	}

	//開始建構樹
	int nTreeRow = n;
	int nTreeCol = nMaxK;

	//宣告
	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++)
	{
		stringstream delim(vecInput[i]);
		string pch;
		getline(delim, pch, ' ');
		k = stoi(pch);
		for (int j = 0; j < k; j++)
		{
			getline(delim, pch, ' ');
			AddChild2(pTree, nTreeRow, nTreeCol, i + 1, stoi(pch));
		}
	}

	//印出檢查
	//PrintTree2(pTree, nTreeRow, nTreeCol);

	//印出根節點
	int nRoot = FindRoot2(pTree, nTreeRow, nTreeCol);
	cout << nRoot << endl;

	//高度總和
	int nDepthSum = 0;
	for (int i = 0; i < nTreeRow ; i++)
		nDepthSum += Distance2(pTree, nTreeRow, nTreeCol, i + 1);
	cout << nDepthSum << endl;

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

	system("pause");
	return 0;
}

//處理轉換
void AddChild2(int** pTree, int nRow, int nCol, int nParent2, int nChild2)
{
	AddChild(pTree, nRow, nCol, nParent2 - 1, nChild2 - 1);
}
int FindRoot2(int** pTree, int nRow, int nCol)
{
	int nRootOrigin = FindRoot(pTree, nRow, nCol);
	return nRootOrigin + 1;
}
int Distance2(int** pTree, int nRow, int nCol, int nNode2)
{
	return Distance(pTree, nRow, nCol, nNode2 - 1);
}
void PrintTree2(int** pTree, int nRow, int nCol)
{
	for (int i = 0; i < nRow; i++)
	{
		cout << "node(" << i+1 << ")->";
		for (int j = 0; j < nCol; j++)
		{
			cout << pTree[i][j]+1 << " ";
		}
		cout << endl;
	}
}
//取得某節點的高度
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;
	}
}