摘? 要：針對(duì)結(jié)構(gòu)復(fù)雜、聯(lián)通算法難以實(shí)現(xiàn)的層級(jí)結(jié)構(gòu)聯(lián)通性問(wèn)題，提出了利用樹(shù)結(jié)構(gòu)的最長(zhǎng)路徑算法解決層級(jí)結(jié)構(gòu)型數(shù)據(jù)的方法。本研究以傳統(tǒng)城堡防護(hù)問(wèn)題為例，找出中間相隔的城墻數(shù)量最多的兩個(gè)點(diǎn)，即層級(jí)結(jié)構(gòu)的聯(lián)通厚度。通過(guò)數(shù)據(jù)結(jié)構(gòu)分析，將城堡各區(qū)域轉(zhuǎn)化為樹(shù)結(jié)構(gòu)，驗(yàn)證了樹(shù)結(jié)構(gòu)的最長(zhǎng)路徑即為層級(jí)結(jié)構(gòu)的聯(lián)通厚度，最終巧妙實(shí)現(xiàn)將層級(jí)結(jié)構(gòu)轉(zhuǎn)換為樹(shù)結(jié)構(gòu)，并利用樹(shù)結(jié)構(gòu)的遍歷分析尋找到樹(shù)的最長(zhǎng)路徑遞歸算法，解決了樹(shù)節(jié)點(diǎn)到節(jié)點(diǎn)的最長(zhǎng)路徑，最終實(shí)現(xiàn)層級(jí)結(jié)構(gòu)各層的聯(lián)通路徑建設(shè)規(guī)劃，為層級(jí)結(jié)構(gòu)問(wèn)題的解決找到突破口與參考性。

關(guān)鍵詞：層級(jí)結(jié)構(gòu);生成樹(shù)結(jié)構(gòu);聯(lián)通算法;最長(zhǎng)路徑

中圖分類(lèi)號(hào)：TP399? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Research on the Connectivity of Hierarchical Structured Data

HE Junzhong

（Longnan Teachers College， Chengxian 742500， China）

lnszhjztg@163.com

Abstract： Aiming at the problem of hierarchical structure connectivity that is difficult to achieve with the complex structure， this paper， proposes a method of using the longest path algorithm of the tree structure to solve the problem of hierarchical structure data. This research takes traditional castle protection problem as an example. It is necessary to find the two points， between which there is the largest number of walls， namely the connectivity thickness of the hierarchical structure. Through data structure analysis， each area of the castle is transformed into a tree structure to verify that the longest path of the tree structure is the connectivity thickness of the hierarchical structure. Finally， hierarchical structure is ingeniously transformed into tree structure， and the traversal of the tree structure is used to analyze and find the longest path recursive algorithm of the tree. It solves the longest path from the tree node to the node. Finally， the proposed method realizes the connection path construction planning of each layer in the hierarchical structure， and makes breakthroughs and provides references for solving hierarchical structure problems.

Keywords： hierarchical structure; spanning tree structure; connectivity algorithm; longest path

1? ?引言（Introduction）

在無(wú)法利用線性結(jié)構(gòu)表示的數(shù)據(jù)中，層級(jí)結(jié)構(gòu)最常見(jiàn)。數(shù)據(jù)間存在上下級(jí)關(guān)系或包含關(guān)系時(shí)，就會(huì)產(chǎn)生層級(jí)結(jié)構(gòu)。世界杯決賽的對(duì)陣表、公司或?qū)W校的組織結(jié)構(gòu)圖、網(wǎng)店商品的分類(lèi)標(biāo)準(zhǔn)等，都具有層級(jí)結(jié)構(gòu)。表示層級(jí)結(jié)構(gòu)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)就是樹(shù)（tree）。若某一概念包含另一概念，就將兩個(gè)概念連接為上下級(jí)形式。這種從一個(gè)上級(jí)概念分割出許多從屬概念的形狀與樹(shù)非常相似，都可以轉(zhuǎn)化為樹(shù)結(jié)構(gòu)解決。

2? ?問(wèn)題概述（Problem overview）

在古代，為保護(hù)城堡，防止敵入侵，更好地守衛(wèi)和保護(hù)更多領(lǐng)地，城堡中心都建有多層城墻，如圖1所示。其中主建筑的Strawgoh要塞達(dá)到了這種建城模式的極致。巨大的圓形外墻包含若干圓形內(nèi)墻，所有城墻均未設(shè)置城門(mén)。因此，要想進(jìn)出必須使用梯子，在要塞內(nèi)部從某地移動(dòng)到另一地也需要耗費(fèi)大量時(shí)間。為此，城主決定挖幾條地道，以連接來(lái)往不便的幾個(gè)地方。為了設(shè)計(jì)出合適的建設(shè)計(jì)劃，需要找出中間相隔的城墻數(shù)量最多的兩個(gè)點(diǎn)。例如，圖1中的兩個(gè)星號(hào)表示的地點(diǎn)相隔了5 層城墻[1]。

給出城墻信息時(shí)，編寫(xiě)程序計(jì)算出從某地移動(dòng)到另一地需要翻過(guò)的城墻最多會(huì)有幾層。此問(wèn)題表面上看起來(lái)與樹(shù)結(jié)構(gòu)并無(wú)直接關(guān)系，但由“所有城墻不會(huì)相交或相接”可知，城墻有很規(guī)則的層次結(jié)構(gòu)，層級(jí)關(guān)系較為明確，從而可以將城墻間的包含關(guān)系轉(zhuǎn)化為樹(shù)結(jié)構(gòu)求解。

圖2（a）是表示各數(shù)據(jù)結(jié)構(gòu)關(guān)系的樹(shù)結(jié)構(gòu)圖。結(jié)構(gòu)圖中的每個(gè)方框表示1 種數(shù)據(jù)結(jié)構(gòu)，上面的方框表示上級(jí)概念，下面的方框表示從屬概念。若某一概念包含另一概念，就將兩個(gè)概念連接為上下級(jí)形式。這種從一個(gè)上級(jí)概念分割出許多從屬概念的形狀與樹(shù)非常相似（雖然上下顛倒），故稱(chēng)為“樹(shù)”，如圖2（b）所示。層級(jí)結(jié)構(gòu)與人類(lèi)的生活關(guān)系非常密切，所以得到了廣泛應(yīng)用。

為此，給城墻分割的各個(gè)“區(qū)域”標(biāo)上序號(hào)。將圍繞當(dāng)前區(qū)域的城墻序號(hào)用作該區(qū)域序號(hào)，得到圖3（a）。通過(guò)這種連接就能把包含關(guān)系表示為樹(shù)結(jié)構(gòu)，如圖3（b）所示。如果兩個(gè)區(qū)域不被同一城墻分割，那么它們不會(huì)在樹(shù)結(jié)構(gòu)中相互連接。例如，1 號(hào)區(qū)域間接包含3 號(hào)區(qū)域，所以并沒(méi)有在樹(shù)結(jié)構(gòu)中直接相連。

轉(zhuǎn)化為樹(shù)結(jié)構(gòu)后，從一個(gè)區(qū)域移動(dòng)到相鄰其他區(qū)域的過(guò)程將對(duì)應(yīng)于樹(shù)結(jié)構(gòu)中沿著樹(shù)的邊從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)的過(guò)程。因此，兩個(gè)區(qū)域間經(jīng)過(guò)的最多城墻數(shù)問(wèn)題就能變換成在樹(shù)結(jié)構(gòu)中尋找相隔最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)的問(wèn)題。此時(shí)，連接兩個(gè)節(jié)點(diǎn)的各邊就是樹(shù)的路徑[1]。

3? ?樹(shù)的最長(zhǎng)路徑（The longest path of the tree）

上述建模過(guò)程將問(wèn)題變換為“找出給定樹(shù)結(jié)構(gòu)中最長(zhǎng)路徑”的問(wèn)題。而求樹(shù)的最長(zhǎng)路徑并不難，求解關(guān)鍵在于需要明白最長(zhǎng)路徑的兩端必須是根節(jié)點(diǎn)或葉節(jié)點(diǎn)。

假設(shè)，既不是根節(jié)點(diǎn)也不是葉節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)（Internal Node）是路徑終點(diǎn)，而內(nèi)部節(jié)點(diǎn)總是連接兩條以上的邊。因?yàn)榇斯?jié)點(diǎn)不是根節(jié)點(diǎn)，所以會(huì)有連向父節(jié)點(diǎn)的邊;又不是葉節(jié)點(diǎn)，所以會(huì)有連向子節(jié)點(diǎn)的邊。因此，以?xún)?nèi)部節(jié)點(diǎn)為終點(diǎn)的路徑必定至少存在1條未使用的邊。利用此邊就能生成更長(zhǎng)的路徑，所以它不可能是最長(zhǎng)路徑[2]。

由此可知，最長(zhǎng)路徑會(huì)是如下兩種路徑中的較大值：最長(zhǎng)的根—葉路徑長(zhǎng)度和最長(zhǎng)的葉—葉路徑長(zhǎng)度。

此時(shí)，最長(zhǎng)的根—葉路徑長(zhǎng)度等于樹(shù)的高度，我們已經(jīng)知道求解方法?，F(xiàn)在只要求出最長(zhǎng)的葉—葉路徑長(zhǎng)度，就能得出答案。

葉—葉路徑的形式總是從葉節(jié)點(diǎn)到達(dá)某個(gè)節(jié)點(diǎn)后，又回到另一個(gè)葉節(jié)點(diǎn)。例如，圖2（b）中連接3和4的路徑，首先從3到達(dá)1之后，又返回4;而連接3和7的路徑，首先從3到達(dá)0之后，又返回7。這種先上升后下降的路徑中，處在上下轉(zhuǎn)換位置的節(jié)點(diǎn)就是此路徑的頂端節(jié)點(diǎn)。因此，在樹(shù)的遍歷過(guò)程中找出將各節(jié)點(diǎn)用作頂端節(jié)點(diǎn)的最長(zhǎng)葉—葉路徑，選擇其中的最大值即可[3]。

該如何求將給定節(jié)點(diǎn)用作頂端節(jié)點(diǎn)的最長(zhǎng)葉—葉路徑呢？這種路徑的形態(tài)是：當(dāng)前節(jié)點(diǎn)的后代節(jié)點(diǎn)中，從一側(cè)上升到該節(jié)點(diǎn)，然后從另一側(cè)下降。此時(shí)，上升部分和下降部分的長(zhǎng)度等于將各自的后代節(jié)點(diǎn)用作根節(jié)點(diǎn)的子樹(shù)高度加1。因此，先計(jì)算出各子樹(shù)的高度后，找出最高的兩個(gè)子樹(shù)就能求出最長(zhǎng)葉—葉路徑。

這些過(guò)程相當(dāng)于求樹(shù)的高度的運(yùn)算過(guò)程。因此，變換一下求樹(shù)高的遞歸函數(shù)就能求出此題。代碼1表示解決此問(wèn)題的遞歸調(diào)用函數(shù)。代碼中，已找出的最長(zhǎng)路徑的長(zhǎng)度會(huì)保存到全局變量longest，而height（）函數(shù)通過(guò)更新此變量完成操作。另外，利用最高的兩個(gè)子樹(shù)的高度求出將當(dāng)前節(jié)點(diǎn)用作頂端節(jié)點(diǎn)的葉—葉路徑中的最長(zhǎng)路徑[4]。

代碼1：找出樹(shù)結(jié)構(gòu)中最長(zhǎng)路徑的遞歸算法。

struct Treellode {

vector children;

};

// 保存已找出的最長(zhǎng)葉—葉路徑的長(zhǎng)度

int longest;

//返回將root用作根節(jié)點(diǎn)的子樹(shù)的高度

int height（TreeNode* root）{

//計(jì)算將各子節(jié)點(diǎn)用作根節(jié)點(diǎn)的子樹(shù)高度

vector heights;

for（int i=0;i < root->children.size（）;++i）

heights.push_back（height（root->children[i]））;

//沒(méi)有子節(jié)點(diǎn)就返回0

if（heights.empty（）） return 0;

sort（heights.begin（），heights.end（））;

//考慮將root用作頂端節(jié)點(diǎn)的路徑

if（heights.size（）>=2）

longest=max（longest，2+heights[heights.size（）-2]+

heights[heights.size（）-1];

//將子樹(shù)高度加1以算出樹(shù)的高度

return heights.back（）+1;

}

//計(jì)算兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離

int solve（TreeNode* root）{

longest=0;

//選擇樹(shù)的高度和最長(zhǎng)葉—葉路徑中更大的值

int h=height（root）;

return max（longest，h）;

}

其中height（）函數(shù)在處理整個(gè)樹(shù)結(jié)構(gòu)的過(guò)程中會(huì)耗費(fèi)時(shí)間，若是忽略子樹(shù)高度的排序時(shí)間O（nlgn），就會(huì)與樹(shù)的遍歷時(shí)間相同，都是O（n）[5]。

4? ?算法的實(shí)現(xiàn)（Algorithm implementation）

此問(wèn)題的實(shí)際實(shí)現(xiàn)方法可分為兩部分：從輸入值生成樹(shù)結(jié)構(gòu);在生成的樹(shù)結(jié)構(gòu)中求出最長(zhǎng)路徑。求最長(zhǎng)路徑的部分如前所述，接下來(lái)介紹樹(shù)結(jié)構(gòu)生成過(guò)程。

最直觀的生成樹(shù)結(jié)構(gòu)的方法是從樹(shù)的根節(jié)點(diǎn)開(kāi)始生成。第0 號(hào)城墻是包含其他所有城墻的外墻，所以它會(huì)成為樹(shù)的根節(jié)點(diǎn)。找出第0 號(hào)城墻的下一層城墻，并通過(guò)遞歸調(diào)用生成將各城墻用作根節(jié)點(diǎn)的子樹(shù)。代碼2是將給定序號(hào)的城墻用作根節(jié)點(diǎn)并生成樹(shù)結(jié)構(gòu)的getTree（）函數(shù)[6]。

代碼2：生成表示給出城墻中各區(qū)域的樹(shù)結(jié)構(gòu)。

//生成將root城墻用作根節(jié)點(diǎn)的樹(shù)

TreeNode* getTree（int root）{

TreeNode* ret=new Treenode（）;

for（int ch=0;ch

//如果ch城墻直接包含于root城墻，那么生成樹(shù)后再添加到后代目錄

if（isChild（root，ch））

ret->children.push_back（getTree（ch））;

return ret;

}

getTree（）中的isChild（）函數(shù)可用多種方法實(shí)現(xiàn)。不過(guò)，實(shí)現(xiàn)此函數(shù)最簡(jiǎn)單的方法是，根據(jù)其他城墻的信息判斷是否存在于兩個(gè)城墻之間。例如，圖2（a）中，第0 號(hào)城墻和第4 號(hào)城墻之間存在第1 號(hào)城墻，因此，第4 個(gè)區(qū)域并沒(méi)有直接包含于第0 號(hào)區(qū)域。代碼3表示實(shí)現(xiàn)這種簡(jiǎn)單方法的isChild（）函數(shù)[7]。

代碼3：確認(rèn)某個(gè)城墻是否包含且直接包含于另一城墻的函數(shù)。

//輸入數(shù)據(jù)

int n，y[100]，x[100]，radius[100];

//返回x^2

int sqr（int x）{

return x*x;

}

//返回兩個(gè)城墻a和b的圓心點(diǎn)距離的平方值

int sqrdist（int a，int b）{

return sqr（y[a]-y[b]）+sqr（x[a]-x[b]）;

}

//確認(rèn)城墻a是否包含城墻b

bool encloses（int a，int b）{

return radius[a]>radius[b] &&

sqrdist（a，b）

}

//在"城墻"樹(shù)結(jié)構(gòu)中確認(rèn)parent是否為child的父節(jié)點(diǎn)

// parent必須直接包含 child

bool iscChild（int parent，int child）{

if（！encloses（parent，child）） return false;

for（int i=0;i

if（i ！=parent && i ！=child &&

encloses（parent，i）&& encloses（i，child））

return false;

return true;

}

通過(guò)這種實(shí)現(xiàn)方法，isChild（）函數(shù)能夠在O（n）的時(shí)間內(nèi)完成運(yùn)算。樹(shù)結(jié)構(gòu)生成過(guò)程中，每訪問(wèn)1 個(gè)節(jié)點(diǎn)，就會(huì)調(diào)用n 次isChild（）。因此，整個(gè)算法的時(shí)間復(fù)雜度為O（n2）[8]。

5? ?結(jié)論（Conclusion）

本研究根據(jù)城堡防衛(wèi)結(jié)構(gòu)圖及聯(lián)通性需求，利用層級(jí)結(jié)構(gòu)和樹(shù)結(jié)構(gòu)關(guān)系，將不容易直接解決的層級(jí)結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)化為樹(shù)結(jié)構(gòu)，從而將城堡的聯(lián)通性結(jié)構(gòu)設(shè)計(jì)轉(zhuǎn)化成了樹(shù)結(jié)構(gòu)的最長(zhǎng)路徑問(wèn)題來(lái)解決。通過(guò)尋找樹(shù)結(jié)構(gòu)的最長(zhǎng)路徑優(yōu)化算法，最終實(shí)現(xiàn)城堡的最大聯(lián)通值。同時(shí)，通過(guò)解決城堡防衛(wèi)聯(lián)通性問(wèn)題，得出利用樹(shù)結(jié)構(gòu)解決層級(jí)結(jié)構(gòu)的方法，為解決層級(jí)結(jié)構(gòu)問(wèn)題的相關(guān)研究提供了依據(jù)。

參考文獻(xiàn)（References）

[1] 計(jì)算思維百科.“要塞”的版本間的差異[EB/OL].（2016-06-02）? [2021-06-05]. https：//wiki.jsswsq.com/index.php？diff=prev&oldid=3711&title=%E8%A6%81%E5%A1%9E.

[2] RAI A K， KUMAR N. Intra-block correlation based reversible data hiding in encrypted images using parametric binary tree labeling[J]. Symmetry， 2021， 13（6）：187-189.

[3] 楊迪，馬金全，岳春生，等.面向異構(gòu)處理平臺(tái)的最長(zhǎng)路徑列表調(diào)度算法[J].信息工程大學(xué)學(xué)報(bào)，2021，22（02）：136-141，214.

[4] 王前東.一種帶匹配路徑約束的最長(zhǎng)公共子序列長(zhǎng)度算法[J].電子與信息學(xué)報(bào)，2017，39（11）：2615-2619.

[5] 潘靜靜.林區(qū)輪伐期優(yōu)化的隱式圖建模和最長(zhǎng)路徑算法[J].河南科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，37（01）：73-77，8-9.

[6] 劉劍，宋瑩，鄧立軍.基于GA與最長(zhǎng)路徑并聯(lián)通路法優(yōu)化通風(fēng)網(wǎng)絡(luò)圖繪制[J].中國(guó)安全生產(chǎn)科學(xué)技術(shù)，2014，10（11）：77-83.

[7] 王防修，周康.基于最長(zhǎng)公共子序列的隨機(jī)路徑選擇算法設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（06）：2170-2173.

[8] 張琦，金胤丞，李苗，等.Trie樹(shù)路由查找算法在網(wǎng)絡(luò)處理器中的實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2014，40（1）：98-102.

作者簡(jiǎn)介：

賀軍忠（1982-），男，碩士，副教授/網(wǎng)絡(luò)工程師.研究領(lǐng)域：網(wǎng)絡(luò)組建與信息安全，網(wǎng)絡(luò)營(yíng)銷(xiāo).