宋小倩，張書茂，康 彥

(安徽城市管理職業(yè)學(xué)院 信息工程系 安徽 合肥230011)

0 引言

樹(shù)形結(jié)構(gòu)是指數(shù)據(jù)元素之間存在著一對(duì)多的樹(shù)形關(guān)系的數(shù)據(jù)結(jié)構(gòu)，是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)。樹(shù)形結(jié)構(gòu)可用于表示從屬關(guān)系，層級(jí)關(guān)系等。本文介紹一種從普通Java 對(duì)象中建立樹(shù)形結(jié)構(gòu)的算法。

1 樹(shù)形結(jié)構(gòu)的算法設(shè)計(jì)

1.1 場(chǎng)景介紹

在教師信息系統(tǒng)中，基本信息模塊中需要填寫各種地址，包含戶口所在地地址、家庭詳細(xì)地址和當(dāng)前居住地詳細(xì)地址等。如果這些地址直接由輸入框輸入，則無(wú)法保證信息填寫的信息準(zhǔn)確性，另外在后續(xù)需要根據(jù)省、市、縣等各類條件生成報(bào)表信息時(shí)會(huì)無(wú)法處理。因此，通過(guò)以樹(shù)形形式提供選擇框供選擇，這樣上面的信息準(zhǔn)確性、后續(xù)條件過(guò)濾時(shí)出現(xiàn)的問(wèn)題都可以避免。

而地址的原始數(shù)據(jù)與頁(yè)面中樹(shù)的展示格式相差較遠(yuǎn)。如何高效地根據(jù)原始數(shù)據(jù)生成樹(shù)形結(jié)構(gòu)便成為該模塊中非常重要的問(wèn)題。如果處理不好就會(huì)在使用樹(shù)進(jìn)行選擇的時(shí)候出現(xiàn)卡頓現(xiàn)象，影響用戶體驗(yàn)。下面詳細(xì)介紹一種高效地在內(nèi)存中構(gòu)建完整樹(shù)形結(jié)構(gòu)的算法，供大家借鑒學(xué)習(xí)。

數(shù)據(jù)本身存儲(chǔ)在數(shù)據(jù)庫(kù)中，需要顯示時(shí)則從數(shù)據(jù)庫(kù)加載數(shù)據(jù)后進(jìn)行顯示。需要建立樹(shù)形結(jié)構(gòu)的時(shí)候，可以從最頂級(jí)節(jié)點(diǎn)開(kāi)始按級(jí)查找下級(jí)所有子節(jié)點(diǎn)來(lái)構(gòu)建樹(shù)形結(jié)構(gòu)［1］。優(yōu)點(diǎn):不需要一次性構(gòu)建整個(gè)樹(shù)形結(jié)構(gòu)。缺點(diǎn):每次展開(kāi)某節(jié)點(diǎn)時(shí)，都需要去數(shù)據(jù)庫(kù)查詢?cè)摴?jié)點(diǎn)的所有子節(jié)點(diǎn)。數(shù)據(jù)庫(kù)壓力非常大，同時(shí)會(huì)導(dǎo)致界面操作出現(xiàn)卡頓現(xiàn)象。

可以考慮將樹(shù)形結(jié)構(gòu)需要的數(shù)據(jù)一次性加載到內(nèi)存當(dāng)中，在內(nèi)存中構(gòu)建樹(shù)形結(jié)構(gòu)的所有節(jié)點(diǎn)結(jié)構(gòu)然后再顯示。這樣既可以減輕數(shù)據(jù)庫(kù)壓力，又可以增強(qiáng)用戶體驗(yàn)［2］。

如圖1給出省市縣鎮(zhèn)村的部分?jǐn)?shù)據(jù)。其中code 列為身份證識(shí)別碼，first 列為省，second 為市，third 為縣，fourth 為鎮(zhèn)，fifth 為村。現(xiàn)在即要在這種數(shù)據(jù)對(duì)象中構(gòu)建省市縣鎮(zhèn)村多級(jí)樹(shù)形結(jié)構(gòu)。

因?yàn)槊考?jí)結(jié)構(gòu)都是文本數(shù)據(jù)，無(wú)法直接通過(guò)上一級(jí)節(jié)點(diǎn)直接得到下一級(jí)節(jié)點(diǎn)數(shù)據(jù)，更無(wú)法直接通過(guò)下一級(jí)節(jié)點(diǎn)得到上一級(jí)節(jié)點(diǎn)數(shù)據(jù)。比如通過(guò)“鎮(zhèn)”列得到“村”列時(shí)，必須保證“鎮(zhèn)”列所屬的“省、市、縣”是一致的。這樣從省到村上下級(jí)關(guān)系來(lái)構(gòu)建樹(shù)形結(jié)構(gòu)，則查詢每個(gè)節(jié)點(diǎn)(除最后一級(jí)節(jié)點(diǎn)外)的所有子節(jié)點(diǎn)都需要遍歷整份數(shù)據(jù)。假設(shè)整份數(shù)據(jù)有N 條，則需要遍歷數(shù)據(jù)N^5 次，即遍歷算法復(fù)雜度至少O(N^5)。如果數(shù)據(jù)為100 條則需要100^5=100 億次。這種算法必然是不可行的。

圖1 省市縣鎮(zhèn)村數(shù)據(jù)(部分)

1.2 算法設(shè)計(jì)

圖1這種數(shù)據(jù)在日常生活中是非常常見(jiàn)的。如果算法設(shè)計(jì)不當(dāng)，則會(huì)得到O(N^5)的算法復(fù)雜度，在程序設(shè)計(jì)中必然無(wú)法接受。

分析這種方法的不合理的原因，主要有以下幾點(diǎn):

(1)每個(gè)節(jié)點(diǎn)都是無(wú)狀態(tài)的。即每個(gè)節(jié)點(diǎn)都不是自說(shuō)明的，而是由前面幾級(jí)節(jié)點(diǎn)共同控制才能保證唯一性［3］。

(2)每次遍歷數(shù)據(jù)都沒(méi)有對(duì)數(shù)據(jù)進(jìn)行緩存。因?yàn)闆](méi)有緩存上一次讀取的數(shù)據(jù)，導(dǎo)致處理任何一個(gè)節(jié)點(diǎn)的下一級(jí)節(jié)點(diǎn)時(shí)都需要再完整遍歷一次整份數(shù)據(jù)。

為了解決節(jié)點(diǎn)的無(wú)狀態(tài)問(wèn)題，可以對(duì)每級(jí)節(jié)點(diǎn)進(jìn)行編碼，比如first 可以編碼為01，second 節(jié)點(diǎn)編碼為0101，third 節(jié)點(diǎn)編碼為010101，fourth 節(jié)點(diǎn)編碼為01010101，fifth 節(jié)點(diǎn)編碼為0101010101。這種方法的優(yōu)點(diǎn)是每個(gè)節(jié)點(diǎn)都是有狀態(tài)的。缺點(diǎn)是每個(gè)節(jié)點(diǎn)在構(gòu)建時(shí)需要先編碼。

本文設(shè)計(jì)的算法則是對(duì)上述方法進(jìn)行改進(jìn)，即對(duì)每級(jí)節(jié)點(diǎn)做到狀態(tài)自說(shuō)明。方法即是在每級(jí)節(jié)點(diǎn)中記錄上一級(jí)節(jié)點(diǎn)文本。比如記錄“合肥市”則記錄為“安徽@合肥”，“瑤海區(qū)”則記錄為“安徽@合肥@瑤海區(qū)”，之后節(jié)點(diǎn)依次類推(假設(shè)分隔符號(hào)為“@”)。如圖2為優(yōu)化后的記錄方式。這些記錄只在內(nèi)存中進(jìn)行構(gòu)建，不真正修改數(shù)據(jù)庫(kù)。

從圖中可以看出，該種處理方式是一種以空間換時(shí)間的解決方案?？梢越鉀Q節(jié)點(diǎn)的無(wú)狀態(tài)問(wèn)題，但仍然無(wú)法解決需要多次遍歷數(shù)據(jù)的問(wèn)題。還需要對(duì)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行緩存。

圖2 優(yōu)化后的記錄方式

在讀取數(shù)據(jù)過(guò)程中要對(duì)層級(jí)關(guān)系進(jìn)行存儲(chǔ)，因?yàn)槭褂脠D2的優(yōu)化后記錄方式，再也不用擔(dān)心節(jié)點(diǎn)名稱重復(fù)的問(wèn)題了。

如何預(yù)處理一遍數(shù)據(jù)則建立上下級(jí)層級(jí)關(guān)系呢?使用一個(gè)關(guān)系容器(假設(shè)名稱為dataMap)記錄上下級(jí)層級(jí)關(guān)系，所有層級(jí)關(guān)系存儲(chǔ)在同一個(gè)關(guān)系容器當(dāng)中。如first 與second，second 與third 等都存儲(chǔ)起來(lái)，過(guò)濾掉重復(fù)的記錄［4］。

關(guān)系容器記錄后效果如下(“=＞”或“/”符號(hào)只用于說(shuō)明上下級(jí)關(guān)系，不代碼具體存儲(chǔ)方式):

安徽=＞安徽@合肥市/ 安徽@蕪湖市...

安徽@合肥市=＞安徽@合肥市@瑤海區(qū)

安徽@合肥市@瑤海區(qū)=＞安徽@合肥市@瑤海區(qū)@磨店鄉(xiāng)

安徽@合肥市@瑤海區(qū)@磨店鄉(xiāng)=＞安徽@合肥市@瑤海區(qū)@磨店鄉(xiāng)@富郢社區(qū)居委會(huì)/ 安徽@合肥市@瑤海區(qū)@磨店鄉(xiāng)@瓦廟社區(qū)居委會(huì)...

上面僅解決了如何記錄數(shù)據(jù)和存儲(chǔ)數(shù)據(jù)，還沒(méi)有真正地建立樹(shù)形結(jié)構(gòu)。

有了上述的數(shù)據(jù)，再來(lái)建立樹(shù)形結(jié)構(gòu)則非常方便了。假設(shè)需要生成的樹(shù)形結(jié)構(gòu)數(shù)據(jù)如圖3的JSON格式。

在圖3中，對(duì)于每級(jí)節(jié)點(diǎn)記錄文本數(shù)據(jù)(text)和子節(jié)點(diǎn)數(shù)據(jù)(children)。如果該層節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)僅記錄text 而不記錄children。

圖3 需要的樹(shù)形結(jié)構(gòu)數(shù)據(jù)

2 算法實(shí)現(xiàn)

第1 部分已經(jīng)非常清晰地將算法設(shè)計(jì)出來(lái)了，下面使用Java 來(lái)實(shí)現(xiàn)該算法。

2.1 算法的Java 實(shí)現(xiàn)

優(yōu)化數(shù)據(jù)記錄實(shí)現(xiàn)如圖4所示。其中，srcList 是源數(shù)據(jù)，可以從數(shù)據(jù)庫(kù)中加載或在程序中模擬。nodeList 是需要構(gòu)建樹(shù)的節(jié)點(diǎn)名稱。dataMap 用于記錄節(jié)點(diǎn)與下級(jí)節(jié)點(diǎn)的map 數(shù)據(jù)。rootList 用于記錄根節(jié)點(diǎn)數(shù)據(jù)。cnMap 用于記錄每個(gè)節(jié)點(diǎn)所有子節(jié)點(diǎn)數(shù)量。

詢多個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)據(jù)的實(shí)現(xiàn)如圖5所示。其中map 為圖4中輸出的dataMap。keyList 為多個(gè)節(jié)點(diǎn)的名稱。cnMap 為圖4中輸出的cnMap。

圖6為構(gòu)建樹(shù)形結(jié)構(gòu)程序的入口。輸入?yún)?shù)為srcList，可以從數(shù)據(jù)庫(kù)中加載或在程序中模擬。nodeList 是需要構(gòu)建樹(shù)的節(jié)點(diǎn)名稱，傳入想要構(gòu)建樹(shù)的字段即可［5］。

圖4 優(yōu)化數(shù)據(jù)記錄的實(shí)現(xiàn)

圖5 遞規(guī)查詢多個(gè)子節(jié)點(diǎn)的實(shí)現(xiàn)

圖6 構(gòu)建樹(shù)形結(jié)構(gòu)的實(shí)現(xiàn)

2.2 實(shí)現(xiàn)效率和效果

在Java 中實(shí)現(xiàn)該算法是非常高效的，構(gòu)建樹(shù)的效率也是非常高的。

使用全國(guó)的省市縣鎮(zhèn)村的數(shù)據(jù)來(lái)構(gòu)建樹(shù)，原始數(shù)據(jù)有70 萬(wàn)條左右。在Windows8 中構(gòu)建該樹(shù)的5 級(jí)結(jié)構(gòu)只需要5 秒左右。

如果使用安徽省的數(shù)據(jù)來(lái)測(cè)試，原始數(shù)據(jù)是2 萬(wàn)條左右。構(gòu)建該樹(shù)的5 級(jí)結(jié)構(gòu)只需要0.2 秒左右。

顯示的效果如圖7所示。左邊的圖即是普通的樹(shù)形結(jié)構(gòu)顯示，右邊的圖中每級(jí)節(jié)點(diǎn)顯示時(shí)加入了其對(duì)應(yīng)的所有子節(jié)點(diǎn)個(gè)數(shù)。

圖7 樹(shù)形結(jié)構(gòu)顯示效果

3 結(jié) 語(yǔ)

本文描述了從普通對(duì)象中建立樹(shù)形結(jié)構(gòu)的一種算法設(shè)計(jì)，并使用Java 語(yǔ)言進(jìn)行了實(shí)現(xiàn)。如果需要建立相關(guān)樹(shù)形結(jié)構(gòu)會(huì)非常方便。

通過(guò)使用文中所述的根據(jù)對(duì)象集合建立樹(shù)形結(jié)構(gòu)算法，即可高效地創(chuàng)建頁(yè)面中需要的樹(shù)形結(jié)構(gòu)，提升頁(yè)面展現(xiàn)效果，有效地解決了系統(tǒng)中多處地址選擇問(wèn)題，達(dá)到了預(yù)期效果。另外，文中對(duì)該算法也使用高效的方法進(jìn)行實(shí)現(xiàn)，如果需要建立相關(guān)樹(shù)形結(jié)構(gòu)直接借鑒即可。

［1］嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu):2 版［M］.北京:清華大學(xué)出版社，2012.

［2］Thomas H.Cormen 等.算法導(dǎo)論:3 版［M］.北京:機(jī)械工業(yè)出版社，2013.

［3］嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)題集(C 語(yǔ)言版)［M］.北京:清華大學(xué)出版社，2011.

［4］韋斯等.數(shù)據(jù)結(jié)構(gòu)與算法分析:Java 語(yǔ)言描述［M］.北京:機(jī)械工業(yè)出版社，2009.

［5］王希軍.java 程序設(shè)計(jì)案例教程［M］.北京:北京郵電大學(xué)出版社，2012.