基于Java的N叉樹結構仿真與實現

□李彥霖 舒新峰

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

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

N叉樹在不同環境中被廣泛使用，如使用N叉樹對計算機網絡問題提出高效解決方案[1]，使用樹狀聯合查找結構優化查找樹算法[2]，解析JSON格式的數據為樹狀模型[3]，在機器學習領域使用N叉樹結構設計和實現支持向量機等，在經濟學領域[4]也廣泛運用N叉樹結構設計解決方案。N叉樹結構一直存在于各領域研究中。

一、樹狀結構研究存在的問題

當下應用領域對N叉樹自身模型的建模與研究較淺，缺乏具有通用性的N叉樹規范建模方式和相關面向對象設計模式，N叉樹具體語言環境下的實現方式尚未得到足夠重視，缺乏一套高效、規范的算法解決N叉樹結構模型構造和訪問等關鍵性問題。故立足于N叉樹本身的建模和實現，Java語言面向對象機制已被業界廣泛熟練使用，應用于極大比例(60%以上)的軟件開發中，占有最重要地位。因其具有無關性、面向對象特性等優勢，N叉樹在未來仍會長期處于軟件開發領導地位?；贘ava設計、仿真、實現一種具有通用性、可用性、高效性的N叉樹數據結構是樹狀結構研究領域的重要問題。它是對Java軟件開發行業從業人員、學者的實踐要求。

在不同開發語言下的N叉樹需要具體的設計、仿真、實現方式。遞歸結構的N叉樹又需要遞歸結構的設計模式和算法，這一方向的理論、實踐需要進一步研究與補充。于是基于Java、面向對象設計模式、遞歸N叉樹結構、遞歸算法，設計、仿真、實現一套對N叉樹模型構造、訪問、搜索等算法的解決方案十分必要。

二、樹狀結構的本質分析

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

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

(一)二叉樹

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

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

(二)N叉樹

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

圖1 N叉樹的邏輯結構

(三)N叉樹的應用

1.B樹

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

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

2.JSON數據的分析

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

3.數據庫相關應用

Java系統開發中數據庫存儲的絕大多數都是樹狀數據，系統大都需要實現數據庫中樹狀數據的建模、查找、訪問等功能，那么在軟件開發中將其轉換為物理上的樹狀結構需要有力的N叉樹模型支持，基于Java設計與仿真實現的N叉樹結構及其算法適用于分析解釋從數據庫中提取的具有復雜層次關系的樹狀結構數據。

4.抽象語法樹

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

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

三、基于Java的通用性N叉樹設計與實現

目前廣泛使用的N叉樹結構建模方式較機械，一般使用人工關聯父子節點。由于父子節點類型不同，每一個不同類型的節點都需要人工做處理，在實體類設計時候要編寫大量不同的實體類，其內部具有復雜的關聯關系，這使大型程序的模型層設計更為復雜，因此需利用面向對象機制解決問題，將N叉樹模型和具體的類型分離，使用Obj類代表所有具體類，如學校、班級、學生等不同類型的類，使用一個Obj類保存對具體類的引用或將類的信息提取出來，插入Obj類的引用中，然后在N叉樹父子節點上進行設計就可全部使用同一種節點類型，實現N叉樹的遞歸結構，從而為使用遞歸算法高效地解決后續構造、遍歷、搜索等不同問題而提供便利。

(一)設計方案

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

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

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

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

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

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

圖2 基于Java的N叉樹設計模型

(二)N叉樹的構造

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

算法1. N叉樹構造法

Step1. 聲明N叉樹樹根NTreeNode類型root節點，分配內存，轉Step2；

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

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

Step4.(遞歸出口)NTreeNode1節點無合法ID，轉Step5；

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

Step6.(循環出口)若No，跳出當前循環，程序結束。

圖3所示為上述算法在Java環境下的仿真與實現代碼，JDK環境1.7，集成開發環境Eclipse2021。

圖3 基于Java的N叉樹構造法

算法1提出的N叉樹構造法是一種使用完全遞圖3基于Java的N叉樹構造法，速度較循環插入節點，或者手動插入構造等方式更具效率，且可以直接運用于Java應用程序算法開發中，有助于程序設計人員快速完成復雜樹狀結構從邏輯層到物理層的轉換。

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

圖4所示為N叉樹構造法中添加當前父節點下子節點的add方法。

圖4 N叉樹構造法中的add方法

(三)N叉樹的遍歷

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

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

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

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

圖5 N叉樹前序遍歷法

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

Step1. 獲取NTreeNodeRoot節點；

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

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

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

Step1. 獲取NTreeNodeRoot節點；

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

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

(四)N叉樹的搜索

算法5.N叉樹搜索法

Step1. 判斷當前節點NTreeNodeRoot的ID是否合法，若Yes，轉Step2；

Step2. 判斷當前節點保存的Obj對象ID和name，name，與函數參數中的ID和name進行匹配，若Yes，輸出Yes和當前節點信息，程序停止運行；若No，不輸出，轉Step3；

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

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

圖6所示為上述N叉樹搜索法在Java環境下的仿真與實現。

圖6 N叉樹搜索法

四、實際應用分析

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

圖7 測試用例

圖8所示為對圖7樹狀結構測試用例構造N叉樹，再進行前序遍歷訪問的仿真實現結果。

圖8 N叉樹構造法仿真結果 圖9 N叉樹搜索法仿真實現結果

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

五、結論

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