台北市96學年度高中資訊學科能力競賽 - 樹狀結構展示 (Tree)
問題描述
樹狀結構為一種程式設計者常用的資料結構，但較不容易在畫面上展示。常見的樹狀結構展示方式為「樹根在左、樹枝朝右」的橫向目錄型式，但其實若能以「樹根在上、樹枝朝下」的直向表示法，更能展現樹狀結構的精神。而要在電腦的二維螢幕上畫出美觀的樹狀結構，必須計算其中各個節點的座標位置。以下圖的樹狀結構為例，在一般文字模式的螢幕上(一個位置一個字元)，其畫出來的樣子如下所示。其中名稱為N-1的節點，其起始座標為(5, 3)，名稱為N-2的節點，其起始座標為(22, 3)，名稱為N-1-1的節點，其起始座標為(1, 6)，其餘依此類推。
根據上例的表示方法，請寫一程式讀入如下格式的樹狀結構後，轉換為直向的樹狀結構，輸出每個節點的二維座標位置。
在將輸入轉換成直向的樹狀圖時，為求美觀，轉換時必須符合下列規則：
1. 節點以其名稱輸出。所有的距離、位置、寬度，都以「字元數」計算。
2. 同一階層的節點有相同垂直位置。
3. 同一階層的節點間必須求出最小間隔，但至少距離一個空白字元。
4. 若某一節點有多個子節點，則其水平位置必需在所有子節點的總寬度的正中央。其計算公式為：(LS + LE + L) / 2。
其中：
S：本身節點的起始水平位置；當S 無法整除時，取其四捨五入值。
LS：第一個子節點的起始水平位置。
LE：最後一個子節點的最後水平位置。
L：本身子節點的長度。
輸入檔格式(C:\tree\input.txt)
1. 輸入為多行字串，每一行代表一個由根節點到本身節點的路徑，節點名稱由英文、數字與可列印符號表示，而上、下節點之間以冒號隔開。
2. 所有的輸入依照深度優先演算法(Depth-First)列出，不會有如下情形：
N-1
N-1:N-1-1
N-2
N-1:N-1-2
3. 輸入格式一定正確，不需考慮輸入格式錯誤情形。
輸出檔格式 (C:\tree\output.txt)
1. 輸出時，先輸出每個節點的路徑，其順序輸入相同。
2. 每個路徑後面，空一格後加上括號，括號內第一個值為該節點的起始水平座標位置，第二個值為其垂直座標位置。
3. 水平與垂直座標位置均以字元數計算，由1 開始。如上例中的節點N-1，其起始水平座標位置為5，則輸出5，垂直座標為3，則輸出3。
輸入檔範例1
N-1
N-1:N-1-1
N-1:N-1-2
N-1:N-1-2:N-1-2-1
N-2
N-2:N-2-1
N-2:N-2-1:N-2-1-1
N-2:N-2-2
N-2:N-2-3
輸出檔範例1
N-1 (5,3)
N-1:N-1-1 (1,6)
N-1:N-1-2 (7,6)
N-1:N-1-2:N-1-2-1 (6,9)
N-2 (22,3)
N-2:N-2-1 (15,6)
N-2:N-2-1:N-2-1-1 (14,9)
N-2:N-2-2 (21,6)
N-2:N-2-3 (27,6)
輸入檔範例2
A
A:AB
A:AC
a
a:ab
a:ac
輸出檔範例2
A (3,3)
A:AB (1,6)
A:AC (4,6)
a (9,3)
a:ab (7,6)
a:ac (10,6)
解題思考
這題老實說比較麻煩，我的作法是把問題分成兩個部份：儲存輸入資料，以及處理解析後的資料(也就是得出題目要求的節點座標)。
要如何根據輸入，將必要的資料儲存在變數呢？在一次讀取檔案的一整行之後，根據題意，我們把這筆資料根據":"作字串切割。這些切割出來的內容，就是一個節點的名稱以及它的節點路徑。
假若這一行的字串共切割成n個部份，則第1個到第n-1個部份即為節點路徑，而最後一個部份就是節點名稱了。至於資料的儲存，就只要根據切割出來的節點路徑，找到其父節點並新增節點資料就可以了。
現在，我們已經能將資料正確的存入結構中了。接著要怎麼得知節點座標呢？
首先，因為每一階層的節點都需要有最小間隔，且至少要距離一個空白，所以我們需要一些變數來存取每個階層的"邊界"。接著，我們就照著深度優先、遞迴的方式，來放置每個節點。
我們舉題目的範例1來看，請看下圖：
第一層目前的邊界為0，因此節點"N-1"暫時放置在第一格的位置，並將邊界加上L+1(節點長度+間隔的空格)。
第二層目前的邊界為0，因此節點"N-1-1"暫時放置在第一格的位置，並將邊界加上L+1。所以"N-1-2"放置於第七格，並同樣再將邊界加上L+1。
第三層目前的邊界為0，因此節點"N-1-2-1"暫時放置在第一格的位置，並將邊界加上L+1。
由"N-1-2-1"節點的位置回推"N-1-2"的節點位置(利用題目給予的公式)：結果小於最小間隔，故將"N-1-2-1"節點調整到配合"N-1-2"節點的位置。
由"N-1-1"與"N-1-2"節點的位置回推"N-1"的節點位置：結果大於其目前的位置，故將"N-1"節點調整到配合"N-1-1"與"N-1-2"節點的位置。
只要能讓程式重複以上步驟，就能夠達成題目的要求了。最後再利用深度優先的方式輸出結果，這題就完成了！
參考解答(C++)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define _GET_MAX_ 256
using namespace std;
struct node
{
int s; // 座標起始點
string name; // 節點名稱
vector<node> childen; // 子節點
};
int move(node &, int);
void show(node &, int, string, ofstream &);
vector<int> border;
int main(void)
{
ifstream in("C:/tree/input.txt");
ofstream out("C:/tree/output.txt", ios_base::trunc);
// 建立一個"虛擬根"作存取起始點
node root;
root.s = 0;
cout << "讀入資料 . . ." << endl;
char get[_GET_MAX_];
while (in.getline(get, _GET_MAX_))
{
// 建立一個節點指標, 指向根節點
node *tree = &root;
string str = get;
string sub;
int start = 0, end;
while (1)
{
// 根據冒號擷取資料
end = str.find(":", start);
sub = str.substr(start, end - start);
// 路徑結束, 跳出
if (end == string::npos) { break; }
// 尋找節點路徑
for (vector<node>::iterator it = (*tree).childen.begin();
it < (*tree).childen.end(); it++)
{
if ((*it).name == sub)
{
// 更新節點指標為此節點
tree = &(*it);
break;
}
}
start = end + 1;
}
// 新增一個節點, 使之為當前節點的子節點
node newnode;
newnode.name = sub;
newnode.s = 1;
(*tree).childen.push_back(newnode);
}
in.close();
// 呼叫遞迴函式處理資料並印出結果
move(root, 0);
show(root, 0, "", out);
out.close();
cout << "輸出資料在 ouput.txt" << endl;
system("pause");
}
int move(node &tree, int level)
{
for (vector<node>::iterator it = tree.childen.begin();
it < tree.childen.end(); it++)
{
// 此層級邊界不存在就新增一個
if (border.size() <= level) { border.push_back(0); }
// 保持節點間隔
(*it).s += *(border.begin() + level);
*(border.begin() + level) += (*it).name.size() + 1;
// 假如有子節點
if ((*it).childen.size())
{
// 呼叫遞迴函式得出偏移量, 以更新起始座標及邊界
int p = move(*it, level + 1);
(*it).s += p;
*(border.begin() + level) += p;
}
}
int m = ((*tree.childen.begin()).s + (*(tree.childen.end() - 1)).s
+ (*(tree.childen.end() - 1)).name.size() - tree.name.size()) / 2;
if (m < tree.s)
{
// 偏移量為負, 修正子節點座標及邊界
for (vector<node>::iterator it = tree.childen.begin();
it < tree.childen.end(); it++)
{
(*it).s += tree.s - m;
}
*(border.begin() + level) += tree.s - m;
return 0;
}
// 返回父節點偏移量
return m - tree.s;
}
void show(node &tree, int level, string str, ofstream &out)
{
if (level)
{
// 印出當前節點座標
cout << str << tree.name << " (" << tree.s << ", " << 3 * level << ")" << endl;
out << str << tree.name << " (" << tree.s << ", " << 3 * level << ")" << endl;
str += tree.name + ":";
}
// 遞迴呼叫函式顯示結果
for (vector<node>::iterator it = tree.childen.begin();
it < tree.childen.end(); it++)
{
show(*it, level + 1, str, out);
}
}
