【解題】樹狀結構展示 - Tree

台北市96學年度高中資訊學科能力競賽 - 樹狀結構展示 (Tree)


問題描述

　　樹狀結構為一種程式設計者常用的資料結構，但較不容易在畫面上展示。常見的樹狀結構展示方式為「樹根在左、樹枝朝右」的橫向目錄型式，但其實若能以「樹根在上、樹枝朝下」的直向表示法，更能展現樹狀結構的精神。而要在電腦的二維螢幕上畫出美觀的樹狀結構，必須計算其中各個節點的座標位置。以下圖的樹狀結構為例，在一般文字模式的螢幕上(一個位置一個字元)，其畫出來的樣子如下所示。其中名稱為N-1的節點，其起始座標為(5, 3)，名稱為N-2的節點，其起始座標為(22, 3)，名稱為N-1-1的節點，其起始座標為(1, 6)，其餘依此類推。



　　根據上例的表示方法，請寫一程式讀入如下格式的樹狀結構後，轉換為直向的樹狀結構，輸出每個節點的二維座標位置。

　　在將輸入轉換成直向的樹狀圖時，為求美觀，轉換時必須符合下列規則：
　　　1. 節點以其名稱輸出。所有的距離、位置、寬度，都以「字元數」計算。
　　　2. 同一階層的節點有相同垂直位置。
　　　3. 同一階層的節點間必須求出最小間隔，但至少距離一個空白字元。
　　　4. 若某一節點有多個子節點，則其水平位置必需在所有子節點的總寬度的正中央。其計算公式為：(L_S + L_E + L) / 2。

　　其中：
　　　S：本身節點的起始水平位置；當S 無法整除時，取其四捨五入值。
　　　L_S：第一個子節點的起始水平位置。
　　　L_E：最後一個子節點的最後水平位置。
　　　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);
    }
}