基于Java的N叉树结构仿真与实现

□李彦霖 舒新峰

(西安邮电大学 计算机学院，陕西 西安 710121)

在当今大数据和人工智能时代的软件系统开发、算法设计与开发中，经常需要处理大规模具有递归关系的数据或结构。如JSON结构数据、XML数据文件、数据库多表查询等输出的树状数据文件，若使用简单的线性结构、集合结构构造、处理该类文件、数据，则无法描述其中数据元素之间具有的逻辑关系，因此常常需要软件开发从业人员具备树状结构的建模设计实现相关API的开发能力。

N叉树在不同环境中被广泛使用，如使用N叉树对计算机网络问题提出高效解决方案[1]，使用树状联合查找结构优化查找树算法[2]，解析JSON格式的数据为树状模型[3]，在机器学习领域使用N叉树结构设计和实现支持向量机等，在经济学领域[4]也广泛运用N叉树结构设计解决方案。N叉树结构一直存在于各领域研究中。

一、树状结构研究存在的问题

当下应用领域对N叉树自身模型的建模与研究较浅，缺乏具有通用性的N叉树规范建模方式和相关面向对象设计模式，N叉树具体语言环境下的实现方式尚未得到足够重视，缺乏一套高效、规范的算法解决N叉树结构模型构造和访问等关键性问题。故立足于N叉树本身的建模和实现，Java语言面向对象机制已被业界广泛熟练使用，应用于极大比例(60%以上)的软件开发中，占有最重要地位。因其具有无关性、面向对象特性等优势，N叉树在未来仍会长期处于软件开发领导地位。基于Java设计、仿真、实现一种具有通用性、可用性、高效性的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 成为理想的数据交换语言，易于人阅读和编写，同时也易于机器解析和生成，并有效地提升网络传输效率。基于Java设计与仿真实现的N叉树结构适用于建模、分析、解释JSON类型结构数据、各类XML文件。

3.数据库相关应用

Java系统开发中数据库存储的绝大多数都是树状数据，系统大都需要实现数据库中树状数据的建模、查找、访问等功能，那么在软件开发中将其转换为物理上的树状结构需要有力的N叉树模型支持，基于Java设计与仿真实现的N叉树结构及其算法适用于分析解释从数据库中提取的具有复杂层次关系的树状结构数据。

4.抽象语法树

在计算机科学中，抽象语法树(Abstract Syntax Tree,AST)，或简称语法树(Syntax tree)，是源代码语法结构的一种抽象表示。顾名思义，抽象语法树也是一种树状结构，树上每一个节点代表源代码中的某一种结构。

语法分析器(parser)通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查,并构建由输入的单词组成的数据结构(一般是语法分析树、抽象语法树等层次化的数据结构)。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。软件开发中，语法分析器分析的结果是抽象语法树。基于Java设计与仿真实现的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叉树模型在软件开发中的应用提供了强大实践支撑。