□李彥霖 舒新峰

(西安郵電大學(xué) 計算機學(xué)院，陜西 西安 710121)

在當(dāng)今大數(shù)據(jù)和人工智能時代的軟件系統(tǒng)開發(fā)、算法設(shè)計與開發(fā)中，經(jīng)常需要處理大規(guī)模具有遞歸關(guān)系的數(shù)據(jù)或結(jié)構(gòu)。如JSON結(jié)構(gòu)數(shù)據(jù)、XML數(shù)據(jù)文件、數(shù)據(jù)庫多表查詢等輸出的樹狀數(shù)據(jù)文件，若使用簡單的線性結(jié)構(gòu)、集合結(jié)構(gòu)構(gòu)造、處理該類文件、數(shù)據(jù)，則無法描述其中數(shù)據(jù)元素之間具有的邏輯關(guān)系，因此常常需要軟件開發(fā)從業(yè)人員具備樹狀結(jié)構(gòu)的建模設(shè)計實現(xiàn)相關(guān)API的開發(fā)能力。

N叉樹在不同環(huán)境中被廣泛使用，如使用N叉樹對計算機網(wǎng)絡(luò)問題提出高效解決方案[1]，使用樹狀聯(lián)合查找結(jié)構(gòu)優(yōu)化查找樹算法[2]，解析JSON格式的數(shù)據(jù)為樹狀模型[3]，在機器學(xué)習(xí)領(lǐng)域使用N叉樹結(jié)構(gòu)設(shè)計和實現(xiàn)支持向量機等，在經(jīng)濟學(xué)領(lǐng)域[4]也廣泛運用N叉樹結(jié)構(gòu)設(shè)計解決方案。N叉樹結(jié)構(gòu)一直存在于各領(lǐng)域研究中。

一、樹狀結(jié)構(gòu)研究存在的問題

當(dāng)下應(yīng)用領(lǐng)域?qū)叉樹自身模型的建模與研究較淺，缺乏具有通用性的N叉樹規(guī)范建模方式和相關(guān)面向?qū)ο笤O(shè)計模式，N叉樹具體語言環(huán)境下的實現(xiàn)方式尚未得到足夠重視，缺乏一套高效、規(guī)范的算法解決N叉樹結(jié)構(gòu)模型構(gòu)造和訪問等關(guān)鍵性問題。故立足于N叉樹本身的建模和實現(xiàn)，Java語言面向?qū)ο髾C制已被業(yè)界廣泛熟練使用，應(yīng)用于極大比例(60%以上)的軟件開發(fā)中，占有最重要地位。因其具有無關(guān)性、面向?qū)ο筇匦缘葍?yōu)勢，N叉樹在未來仍會長期處于軟件開發(fā)領(lǐng)導(dǎo)地位。基于Java設(shè)計、仿真、實現(xiàn)一種具有通用性、可用性、高效性的N叉樹數(shù)據(jù)結(jié)構(gòu)是樹狀結(jié)構(gòu)研究領(lǐng)域的重要問題。它是對Java軟件開發(fā)行業(yè)從業(yè)人員、學(xué)者的實踐要求。

在不同開發(fā)語言下的N叉樹需要具體的設(shè)計、仿真、實現(xiàn)方式。遞歸結(jié)構(gòu)的N叉樹又需要遞歸結(jié)構(gòu)的設(shè)計模式和算法，這一方向的理論、實踐需要進一步研究與補充。于是基于Java、面向?qū)ο笤O(shè)計模式、遞歸N叉樹結(jié)構(gòu)、遞歸算法，設(shè)計、仿真、實現(xiàn)一套對N叉樹模型構(gòu)造、訪問、搜索等算法的解決方案十分必要。

二、樹狀結(jié)構(gòu)的本質(zhì)分析

樹狀數(shù)據(jù)結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)；它是一種數(shù)據(jù)元素之間存在一對多關(guān)系的數(shù)據(jù)結(jié)構(gòu)。二叉樹是其中最為常用的一種樹。廣義上講，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹狀數(shù)據(jù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)都可用樹狀數(shù)據(jù)結(jié)構(gòu)來形象表示。

樹狀結(jié)構(gòu)是一種層次的嵌套結(jié)構(gòu)。 一個樹狀結(jié)構(gòu)的上層和下層有相同或者相似的結(jié)構(gòu)， 所以這種結(jié)構(gòu)絕大多數(shù)都可以用遞歸表示。經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的各種樹狀圖是一種典型的樹狀結(jié)構(gòu)：一顆樹可以簡單的表示為根和子樹。子樹又有自己的子樹，子樹和子樹的子樹結(jié)構(gòu)相似或者完全相同。

(一)二叉樹

二叉樹(Binary tree)是樹狀結(jié)構(gòu)的一個重要類型。很多數(shù)據(jù)、實際問題都可以抽象構(gòu)造為二叉樹模型。二叉樹結(jié)構(gòu)特點是每個結(jié)點最多只能有兩棵子樹，有左右之分，每個父節(jié)點最多有兩個子節(jié)點。二叉樹廣泛被應(yīng)用在不同功能的算法中，如紅黑二叉樹一般情況下具有較線性結(jié)構(gòu)更高查找效率。

但是二叉樹模型受限于每個父節(jié)點最多只能有兩個子節(jié)點，故很多情況下無法完成針對軟件設(shè)計和理論研究的實際需求。經(jīng)典數(shù)據(jù)結(jié)構(gòu)中對二叉樹的理論、實踐深度不足以滿足當(dāng)今大數(shù)據(jù)、人工智能潮流和高級編程語言環(huán)境下，現(xiàn)代大型軟件系統(tǒng)的模型構(gòu)造、算法設(shè)計等模塊對樹狀結(jié)構(gòu)的軟件開發(fā)要求。故需涉及N叉樹的概念并“基于Java環(huán)境設(shè)計，仿真和實現(xiàn)一種具有通用性的N叉樹數(shù)據(jù)結(jié)構(gòu)”。

(二)N叉樹

二叉樹中每個父節(jié)點最多有兩個子節(jié)點，如果一顆樹的每個父節(jié)點可以有兩個以上的子節(jié)點，那么這個樹稱為N階的多叉樹，或者稱為N叉樹。如下圖所描述是一顆高度為5，寬度為3的N叉樹，其中N=3，故仍可稱圖1所示結(jié)構(gòu)為一顆三叉樹結(jié)構(gòu)。

圖1 N叉樹的邏輯結(jié)構(gòu)

(三)N叉樹的應(yīng)用

1.B樹

B樹(B-tree)是由Bayer和McCreight在1972年提出的數(shù)據(jù)結(jié)構(gòu)。B樹索引是數(shù)據(jù)庫中存取、查樹不同，B樹功能在于實現(xiàn)系統(tǒng)大塊數(shù)據(jù)進行高效率讀寫操作。B樹是一顆查找樹，但不同于二叉查找樹，它規(guī)定一個節(jié)點可以擁有多于2個子節(jié)點，B樹就是一種樹狀數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用，且是一種N叉樹結(jié)構(gòu)，可以完成存儲、排序數(shù)據(jù)，并且允許以O(shè)(log n)的時間復(fù)雜度運行進行查找、順序讀取、插入和刪除的數(shù)據(jù)結(jié)構(gòu)。B-tree算法可以用于文件讀寫操作時候提高定位記錄的效率，減少運行時間，加快存取速度。當(dāng)今在數(shù)據(jù)庫和文件系統(tǒng)中應(yīng)用仍然十分廣泛。

2-3-4樹是一顆階為4的B樹，可以完成B樹的大部分功能，并且可以用做字典。

2.JSON數(shù)據(jù)的分析

JSON(JavaScript?Object Notation, JS 對象簡譜) 是一種當(dāng)今特別流行的輕量級的數(shù)據(jù)交換格式，是一種樹狀結(jié)構(gòu)的數(shù)據(jù)，幾乎應(yīng)用于所有Java開發(fā)的BS軟件系統(tǒng)中。JSON基于ECMAScript(歐洲計算機協(xié)會JavaScript規(guī)范)的一個子集，采用樹狀結(jié)構(gòu)的文本格式來存儲和表示數(shù)據(jù)，類似XML文件，但比XML風(fēng)格更簡約規(guī)范。簡潔和清晰的層次結(jié)構(gòu)使得 JSON 成為理想的數(shù)據(jù)交換語言，易于人閱讀和編寫，同時也易于機器解析和生成，并有效地提升網(wǎng)絡(luò)傳輸效率。基于Java設(shè)計與仿真實現(xiàn)的N叉樹結(jié)構(gòu)適用于建模、分析、解釋JSON類型結(jié)構(gòu)數(shù)據(jù)、各類XML文件。

3.數(shù)據(jù)庫相關(guān)應(yīng)用

Java系統(tǒng)開發(fā)中數(shù)據(jù)庫存儲的絕大多數(shù)都是樹狀數(shù)據(jù)，系統(tǒng)大都需要實現(xiàn)數(shù)據(jù)庫中樹狀數(shù)據(jù)的建模、查找、訪問等功能，那么在軟件開發(fā)中將其轉(zhuǎn)換為物理上的樹狀結(jié)構(gòu)需要有力的N叉樹模型支持，基于Java設(shè)計與仿真實現(xiàn)的N叉樹結(jié)構(gòu)及其算法適用于分析解釋從數(shù)據(jù)庫中提取的具有復(fù)雜層次關(guān)系的樹狀結(jié)構(gòu)數(shù)據(jù)。

4.抽象語法樹

在計算機科學(xué)中，抽象語法樹(Abstract Syntax Tree,AST)，或簡稱語法樹(Syntax tree)，是源代碼語法結(jié)構(gòu)的一種抽象表示。顧名思義，抽象語法樹也是一種樹狀結(jié)構(gòu)，樹上每一個節(jié)點代表源代碼中的某一種結(jié)構(gòu)。

語法分析器(parser)通常是作為編譯器或解釋器的組件出現(xiàn)的，它的作用是進行語法檢查,并構(gòu)建由輸入的單詞組成的數(shù)據(jù)結(jié)構(gòu)(一般是語法分析樹、抽象語法樹等層次化的數(shù)據(jù)結(jié)構(gòu))。語法分析器通常使用一個獨立的詞法分析器從輸入字符流中分離出一個個的“單詞”，并將單詞流作為其輸入。軟件開發(fā)中，語法分析器分析的結(jié)果是抽象語法樹?；贘ava設(shè)計與仿真實現(xiàn)的N叉樹結(jié)構(gòu)適用于語法分析器的構(gòu)造，根據(jù)編譯環(huán)境的語法要求生成各類語言的抽象語法樹。

三、基于Java的通用性N叉樹設(shè)計與實現(xiàn)

目前廣泛使用的N叉樹結(jié)構(gòu)建模方式較機械，一般使用人工關(guān)聯(lián)父子節(jié)點。由于父子節(jié)點類型不同，每一個不同類型的節(jié)點都需要人工做處理，在實體類設(shè)計時候要編寫大量不同的實體類，其內(nèi)部具有復(fù)雜的關(guān)聯(lián)關(guān)系，這使大型程序的模型層設(shè)計更為復(fù)雜，因此需利用面向?qū)ο髾C制解決問題，將N叉樹模型和具體的類型分離，使用Obj類代表所有具體類，如學(xué)校、班級、學(xué)生等不同類型的類，使用一個Obj類保存對具體類的引用或?qū)㈩惖男畔⑻崛〕鰜?，插入Obj類的引用中，然后在N叉樹父子節(jié)點上進行設(shè)計就可全部使用同一種節(jié)點類型，實現(xiàn)N叉樹的遞歸結(jié)構(gòu)，從而為使用遞歸算法高效地解決后續(xù)構(gòu)造、遍歷、搜索等不同問題而提供便利。

(一)設(shè)計方案

NTreeOprt類代表N叉樹操作API集合，擁有初始化N叉樹的樹根的成員變量，該類提供多叉樹的前序、中序、后序遍歷，根據(jù)節(jié)點保存的數(shù)據(jù)Obj對象對不同信息進行查找。

樹狀結(jié)構(gòu)是一種層次嵌套的結(jié)構(gòu)，每一層都有相同或者相似的結(jié)構(gòu)，于是在樹狀結(jié)構(gòu)節(jié)點類NTreeNode類構(gòu)造上需要采用遞歸的結(jié)構(gòu)，每一層模型都含有一個對下層模型的引用，且這兩層模型的類型相同，于是使用Arraylist〈NTreeNode〉集合Arraylist〈NTreeNode〉集合treenodes保存x(x=0,1,2,…,N)個NTreeNode節(jié)點，將其關(guān)聯(lián)到NTreeNode本身中，使用可動態(tài)擴展的Arraylist集合來描述每一個NTreeNode節(jié)點下可以擁有多個NTreeNode類型的子節(jié)點，每一個NTreeNode節(jié)點下又包含Arraylist〈NTreeNode〉集合，以此種設(shè)計模式實現(xiàn)N叉樹遞歸結(jié)構(gòu)。

綜上所述，NTreeNode類設(shè)計可以實現(xiàn)在構(gòu)造N叉樹和訪問N叉樹過程中，同一層引用之間的變量替換，便于使用遞歸算法簡單高效地開發(fā)相關(guān)API。

Obj類保存NTreeNode代表的數(shù)據(jù)信息。例如，學(xué)校->班級->學(xué)生，城市->區(qū)域->人口等此類樹狀關(guān)系，由于多叉樹在實際問題中每層節(jié)點保存的信息類型并不可能完全一致，如學(xué)校與班級、學(xué)生等均類型各異，于是在Obj類中可以按照需求增加不同類型的成員變量，不局限于字符串類型，這具有良好的可擴展性和描述性，但由于具體類型組織的樹狀結(jié)構(gòu)只能用經(jīng)典、低效的關(guān)聯(lián)模型，手動進行一一關(guān)聯(lián)不能使用遞歸算法來實現(xiàn)對其的操作，故不使用Obj類作為N叉樹節(jié)點類型。

對N叉樹結(jié)構(gòu)研究的核心是N叉樹模型構(gòu)造方法，通過高效算法在Java環(huán)境下建立通用性強的N叉樹，使其邏輯結(jié)構(gòu)與物理結(jié)構(gòu)相統(tǒng)一是工程人員在實際軟件開發(fā)中遇到的重要問題。提供一種純遞歸結(jié)構(gòu)的前序按需求動態(tài)構(gòu)造N叉樹節(jié)點的方法，可應(yīng)用于多種樹狀模型數(shù)據(jù)的解析、存儲、建模流程中，具有實用性、高效性、通用性。

N叉樹建模工作通過圖2類圖直觀可見，由于篇幅所限，下列僅詳解N叉樹構(gòu)造方法、以及N叉樹遍歷方式、N叉樹查找三類算法。

圖2 基于Java的N叉樹設(shè)計模型

(二)N叉樹的構(gòu)造

遞歸算法(recursion algorithm)在計算機科學(xué)中是指一種通過重復(fù)將問題分解為同類子問題而解決問題的方法。遞歸式方法可以被用于解決很多的計算機科學(xué)問題，因此它是計算機科學(xué)中十分重要的一個概念。絕大多數(shù)編程語言支持函數(shù)的自調(diào)用，在這些語言中函數(shù)可以通過調(diào)用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環(huán)，因此在很多函數(shù)編程語言(如Scheme)中習(xí)慣用遞歸來實現(xiàn)循環(huán)。遞歸算法的執(zhí)行效率一般遠(yuǎn)高于循環(huán)，許多二重循環(huán)、三重循環(huán)的問題如果使用遞歸算法設(shè)計解決，會大大提高程序運行效率。運行效率是Java語言開發(fā)的大型系統(tǒng)軟件開發(fā)中至關(guān)重要的評價標(biāo)準(zhǔn)，用遞歸算法解決軟件開發(fā)中的許多細(xì)節(jié)問題可實現(xiàn)更好的效果。N叉樹是一種遞歸結(jié)構(gòu)，一般情況來講遞歸結(jié)構(gòu)都可以使用遞歸算法實現(xiàn)構(gòu)造、訪問、搜索等功能。

算法1. N叉樹構(gòu)造法

Step1. 聲明N叉樹樹根NTreeNode類型root節(jié)點，分配內(nèi)存，轉(zhuǎn)Step2；

Step2. 進入Init()函數(shù)，實際參數(shù)為root對象，保存回溯點為root，按照需求向該對象關(guān)聯(lián)的子集合nodes中添加一個新的NTreeNode1節(jié)點，轉(zhuǎn)Step3；

Step3.(循環(huán)入口)開始循環(huán)遍歷root的nodes集合，判斷NTreeNode1節(jié)點是否有合法ID，若Yes，該節(jié)點是一個合法節(jié)點，(遞歸入口)使用NTreeNode1節(jié)點代替Step1中的root對象，遞歸進入Step1-Step3步驟執(zhí)行；

Step4.(遞歸出口)NTreeNode1節(jié)點無合法ID，轉(zhuǎn)Step5；

Step5. 判斷root節(jié)點下的NTreeNode1子節(jié)點是否有其他兄弟節(jié)點，若Yes，在root節(jié)點下按照需求添加一個兄弟節(jié)點NTreeNode2；

Step6.(循環(huán)出口)若No，跳出當(dāng)前循環(huán)，程序結(jié)束。

圖3所示為上述算法在Java環(huán)境下的仿真與實現(xiàn)代碼，JDK環(huán)境1.7，集成開發(fā)環(huán)境Eclipse2021。

圖3 基于Java的N叉樹構(gòu)造法

算法1提出的N叉樹構(gòu)造法是一種使用完全遞圖3基于Java的N叉樹構(gòu)造法，速度較循環(huán)插入節(jié)點，或者手動插入構(gòu)造等方式更具效率，且可以直接運用于Java應(yīng)用程序算法開發(fā)中，有助于程序設(shè)計人員快速完成復(fù)雜樹狀結(jié)構(gòu)從邏輯層到物理層的轉(zhuǎn)換。

構(gòu)造法中的動態(tài)構(gòu)造回溯點的分支節(jié)點是該算法的一個核心點，多類實際應(yīng)用場景中都涉及此類問題。例如，在對數(shù)據(jù)庫多張表中多個字段進行訪問時，例如年級-班級-學(xué)生-學(xué)生成績。每訪問到一條分支，進入該分支訪問子字段，直到訪問到葉子字段開始回溯，此時若存在回溯點的其他分支，按照需求的動態(tài)創(chuàng)建多個兄弟節(jié)點，繼續(xù)進行分支訪問和動態(tài)構(gòu)造節(jié)點。

圖4所示為N叉樹構(gòu)造法中添加當(dāng)前父節(jié)點下子節(jié)點的add方法。

圖4 N叉樹構(gòu)造法中的add方法

(三)N叉樹的遍歷

算法2.N叉樹前序遍歷法

Step1. 判斷當(dāng)前節(jié)點NTreeNodeRoot的ID是否合法，若Yes，輸出節(jié)點信息；節(jié)點的子節(jié)點集合nodes，循環(huán)遍歷nodes，(遞歸入口)保存回溯點NTreeNodeRoot，使用每一個nodes中的NTreeNode節(jié)點代替Step1中NTreeNodeRoot，遞歸執(zhí)行Step1-Step2；

Step3.(遞歸出口)若Step1判斷為No，回溯到最后一個回溯點。

圖5所示為上述N叉樹前序遍歷法在Java環(huán)境下的仿真實現(xiàn)代碼。

圖5 N叉樹前序遍歷法

算法3.N叉樹中序遍歷法

Step1. 獲取NTreeNodeRoot節(jié)點；

Step2.(循環(huán)入口)提取當(dāng)前NTreeNodeRoot節(jié)點的子節(jié)點集合nodes，循環(huán)遍歷nodes，判斷當(dāng)前節(jié)點NTreeNodeRoot的ID是否合法，若Yes，輸出節(jié)點信息；(遞歸入口)保存回溯點NTreeNodeRoot，使用每一個nodes中的NTreeNode節(jié)點代替Step1中NTreeNodeRoot，遞歸執(zhí)行Step1-Step2；

Step3.(遞歸出口)若Step1判斷為No，回溯到最后一個回溯點。

算法4.N叉樹后序遍歷法

Step1. 獲取NTreeNodeRoot節(jié)點；

Step2.(循環(huán)入口)提取當(dāng)前NTreeNodeRoot節(jié)點的子節(jié)點集合nodes，循環(huán)遍歷nodes(遞歸入口)保存回溯點NTreeNodeRoot，使用每一個nodes中的NTreeNode節(jié)點代替Step1中NTreeNodeRoot，遞歸執(zhí)行Step1-Step2；

Step3.(遞歸出口)若Step1判斷為No，回溯到最后一個回溯點，判斷當(dāng)前節(jié)點NTreeNodeRoot的ID是否合法，若Yes，輸出節(jié)點信息。

(四)N叉樹的搜索

算法5.N叉樹搜索法

Step1. 判斷當(dāng)前節(jié)點NTreeNodeRoot的ID是否合法，若Yes，轉(zhuǎn)Step2；

Step2. 判斷當(dāng)前節(jié)點保存的Obj對象ID和name，name，與函數(shù)參數(shù)中的ID和name進行匹配，若Yes，輸出Yes和當(dāng)前節(jié)點信息，程序停止運行；若No，不輸出，轉(zhuǎn)Step3；

Step3.(循環(huán)入口)提取當(dāng)前NTreeNodeRoot節(jié)點的子節(jié)點集合nodes，循環(huán)遍歷nodes，(遞歸入口)保存回溯點NTreeNodeRoot，使用每一個nodes中的NTreeNode節(jié)點代替Step1中NTreeNodeRoot，遞歸執(zhí)行Step1-Step2；

Step4.(遞歸出口)若Step1判斷為No，回溯到最后一個回溯點。

圖6所示為上述N叉樹搜索法在Java環(huán)境下的仿真與實現(xiàn)。

圖6 N叉樹搜索法

四、實際應(yīng)用分析

圖7所示為樹狀結(jié)構(gòu)典型的一個測試用例。學(xué)校、班級、學(xué)生、學(xué)生成績四個類型之間具有樹狀層級關(guān)系，西安一中存在兩個班級，分別是一年一班、二年一班、一年一班有三個學(xué)生，對應(yīng)學(xué)號姓名分別是101-01、jack，101-02、rose，101-03、kim，為體現(xiàn)層級關(guān)系，設(shè)計jack關(guān)聯(lián)子節(jié)點為jack語文成績，不局限于該測試用例，類似該用例所示樹狀關(guān)系的模型均可使用上述算法1-5進行構(gòu)造、遍歷、搜索。樹狀結(jié)構(gòu)用途多樣，不局限于抽象構(gòu)造實體模型，非樹狀結(jié)構(gòu)的數(shù)據(jù)用樹狀結(jié)構(gòu)進行查找、排序，較常見查找、排序更高效，此類應(yīng)用亦可使用上述算法實現(xiàn)構(gòu)造、遍歷、搜索等功能。

圖7 測試用例

圖8所示為對圖7樹狀結(jié)構(gòu)測試用例構(gòu)造N叉樹，再進行前序遍歷訪問的仿真實現(xiàn)結(jié)果。

圖8 N叉樹構(gòu)造法仿真結(jié)果 圖9 N叉樹搜索法仿真實現(xiàn)結(jié)果

圖9所示為對圖7測試用例構(gòu)造的N叉樹使用N叉樹搜索法查找id為101-01、name為jack的子節(jié)點的仿真實現(xiàn)結(jié)果。

五、結(jié)論

本研究設(shè)計實現(xiàn)了一種具有實用性、通用性的N叉樹的構(gòu)造，找到了對其前序、中序、后序等三種遍歷方式以及一類通過節(jié)點保存的內(nèi)容查找指定N叉樹節(jié)點的算法；提出了一種基于Java的具有通用性的N叉樹結(jié)構(gòu)建模和解析方式，找到了一套N叉樹結(jié)構(gòu)在Java環(huán)境下解決模型構(gòu)造、遍歷、搜索等問題的完整解決方案。本研究對軟件開發(fā)中遇到寬度為N的樹狀結(jié)構(gòu)的建模與解釋有理論擴充意義，對數(shù)據(jù)庫樹狀數(shù)據(jù)建模、XML文件建模解析、JSON類型文件建模解析等領(lǐng)域具有實踐意義，為N叉樹模型在軟件開發(fā)中的應(yīng)用提供了強大實踐支撐。