完全多叉树的叶子节点构造搜索模型的算法与应用

魏宾宾

摘要：设计了完全多叉树的存储结构和遍历算法，并设计了根据子节点搜索整个完全多叉树算法，最后给出了一个实际的完全三叉树的应用例子。

关键词：完全多叉树存储结构；完全多叉数遍历算法；完全多叉树叶子节点构造搜索模型

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）10-2436-03

Abstract： This paper design the storage structure and traversal algorithm of Multi-tree and give the algorithm based leaf node of Complete Multi-tree to construct search model. Finally the paper give us an application of the algorithm.

Key words： the storage of multi-tree； the traversal algorithm of multi-tree； based leaf node of Complete Multi-tree to construct search model

二叉树是数据结构中非常重要的一种非线性数据结构，在我国研究二叉树的课本和算法都比较多，但是研究多叉树的算法和应用却不是很多。文献[1]给出了三叉树的结构，周游，抽象数据类型，三叉树的实现展开。文献[2]主要提出了“儿子-兄弟链表”存储三叉树方法，并讨论了其算法及效率。文献[3]通过“儿子-兄弟链表”存储多叉树，并对其遍历运算进行了详细的探究。该文主要围绕完全多叉树的定义，存储，算法和应用展开。为需要用完全多叉树解决的问题提供算法支持和解决思路。

1 完全多叉树的定义

定义 完全多叉树t是元素的有限非空集合。这些元素中有一个元素被称为根，其余的元素被分成一些树，它们称为t的子树。它满足如下条件：这棵树正好包含个元素（n=2，3，4……，h=1，2，3，……）n表示多叉树每个有根子树的个数，h代表整棵树的深度。

下图给出了一个深度为3的完全二叉树和三叉树。

以上给出了完全3叉树和4叉树的递归遍历算法，完全多叉树可以参照3叉树和四叉树的遍历算法。

4 完全多叉树的叶子结点构造搜索模型的算法

第一步，遍历整个完全多叉树。

第二步，当遍历到每一个叶子结点的时候，将遍历到的子节点存入的一个数组中，数组的长度为。

第三步，根据数组中的每一个结点可以通过找父节点的方式来搜索整个完全多叉树。

5 完全多叉树的应用例子

本文通过一个例子来说明完全三叉树的应用。

解决的问题：在123456789插入加号或减号使其表达式最后的和为100。

解决的方案：首先将问题抽象为：在123456789任意的两个数之间中可以加入加号减号和空号。所有的可能性可以用一个完全三叉树来存储，通过使用完全三叉树叶子结点搜索模型的算法可以获得所有的可能性操作。然后对所有的操作可能性进行计算，当计算的结果等于100时，再将结果输出。

计算的关键算法如下：

1） 对所有的为空号的操作进行计算，算法如图3所示。

2） 对加号和减号的处理算法基本一致，图4只列出遇到加号的处理算法。

3）加号和减号处理过之后如果sum等于100，即可把结果输出。

4）算法实现之后得到的结果如下：

6 结束语

本文给出了完全多叉树的定义，存储，遍历算法。提出了一种完全多叉树叶子结点构造搜索模型的算法，并给出了一个通过这种算法解决的问题。该文也给出了这个问题的整体解决思路，解决算法和实验结果。为需要用完全多叉树解决的问题提供算法支持和解决思路。

参考文献：

[1] 张乃孝.三叉树结构及其实现[J].计算机研究与发展，1993：50-54， 41.

[2] 毛国君，杨涤非.一种三叉树的存储结构及其基本操作的实现[J].计算机研究与发展，1994，31（5）：62-65.

[3] 林桂伍.多叉树结构及其实现[J].福州大学学报（自然科学版），1995，23（1）：16-19.

[4] Sartaj Sahni.数据结构、算法与应用（Java 语言描述）[M].孔芳，高伟，译.北京：中国水利水电出版社，2007：315-318.

[5] 袁玲，邓小燕.一种基于多叉树的检索方法及其应用[J].计算技术与自动化，2011，30（3）：139-141.

[6] 盛魁.二叉树的遍历探究与应用[J].电脑知识与技术，2008，3（5）：1014-1015，1034.