□李彥霖 舒新峰

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

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

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

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

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

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

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

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

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

(一)二叉樹(shù)

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

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

(二)N叉樹(shù)

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

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

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

1.B樹(shù)

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

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

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

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

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

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

4.抽象語(yǔ)法樹(shù)

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

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

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

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

(一)設(shè)計(jì)方案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(三)N叉樹(shù)的遍歷

算法2.N叉樹(shù)前序遍歷法

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

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

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

圖5 N叉樹(shù)前序遍歷法

算法3.N叉樹(shù)中序遍歷法

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

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

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

算法4.N叉樹(shù)后序遍歷法

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

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

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

(四)N叉樹(shù)的搜索

算法5.N叉樹(shù)搜索法

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

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

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

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

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

圖6 N叉樹(shù)搜索法

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

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

圖7 測(cè)試用例

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

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

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

五、結(jié)論

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