魏賓賓

摘要：設(shè)計(jì)了完全多叉樹的存儲(chǔ)結(jié)構(gòu)和遍歷算法，并設(shè)計(jì)了根據(jù)子節(jié)點(diǎn)搜索整個(gè)完全多叉樹算法，最后給出了一個(gè)實(shí)際的完全三叉樹的應(yīng)用例子。

關(guān)鍵詞：完全多叉樹存儲(chǔ)結(jié)構(gòu)；完全多叉數(shù)遍歷算法；完全多叉樹葉子節(jié)點(diǎn)構(gòu)造搜索模型

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

二叉樹是數(shù)據(jù)結(jié)構(gòu)中非常重要的一種非線性數(shù)據(jù)結(jié)構(gòu)，在我國(guó)研究二叉樹的課本和算法都比較多，但是研究多叉樹的算法和應(yīng)用卻不是很多。文獻(xiàn)[1]給出了三叉樹的結(jié)構(gòu)，周游，抽象數(shù)據(jù)類型，三叉樹的實(shí)現(xiàn)展開。文獻(xiàn)[2]主要提出了“兒子-兄弟鏈表”存儲(chǔ)三叉樹方法，并討論了其算法及效率。文獻(xiàn)[3]通過“兒子-兄弟鏈表”存儲(chǔ)多叉樹，并對(duì)其遍歷運(yùn)算進(jìn)行了詳細(xì)的探究。該文主要圍繞完全多叉樹的定義，存儲(chǔ)，算法和應(yīng)用展開。為需要用完全多叉樹解決的問題提供算法支持和解決思路。

1 完全多叉樹的定義

定義 完全多叉樹t是元素的有限非空集合。這些元素中有一個(gè)元素被稱為根，其余的元素被分成一些樹，它們稱為t的子樹。它滿足如下條件：這棵樹正好包含個(gè)元素（n=2，3，4……，h=1，2，3，……）n表示多叉樹每個(gè)有根子樹的個(gè)數(shù)，h代表整棵樹的深度。

下圖給出了一個(gè)深度為3的完全二叉樹和三叉樹。

以上給出了完全3叉樹和4叉樹的遞歸遍歷算法，完全多叉樹可以參照3叉樹和四叉樹的遍歷算法。

4 完全多叉樹的葉子結(jié)點(diǎn)構(gòu)造搜索模型的算法

第一步，遍歷整個(gè)完全多叉樹。

第二步，當(dāng)遍歷到每一個(gè)葉子結(jié)點(diǎn)的時(shí)候，將遍歷到的子節(jié)點(diǎn)存入的一個(gè)數(shù)組中，數(shù)組的長(zhǎng)度為。

第三步，根據(jù)數(shù)組中的每一個(gè)結(jié)點(diǎn)可以通過找父節(jié)點(diǎn)的方式來搜索整個(gè)完全多叉樹。

5 完全多叉樹的應(yīng)用例子

本文通過一個(gè)例子來說明完全三叉樹的應(yīng)用。

解決的問題：在123456789插入加號(hào)或減號(hào)使其表達(dá)式最后的和為100。

解決的方案：首先將問題抽象為：在123456789任意的兩個(gè)數(shù)之間中可以加入加號(hào)減號(hào)和空號(hào)。所有的可能性可以用一個(gè)完全三叉樹來存儲(chǔ)，通過使用完全三叉樹葉子結(jié)點(diǎn)搜索模型的算法可以獲得所有的可能性操作。然后對(duì)所有的操作可能性進(jìn)行計(jì)算，當(dāng)計(jì)算的結(jié)果等于100時(shí)，再將結(jié)果輸出。

計(jì)算的關(guān)鍵算法如下：

1） 對(duì)所有的為空號(hào)的操作進(jìn)行計(jì)算，算法如圖3所示。

2） 對(duì)加號(hào)和減號(hào)的處理算法基本一致，圖4只列出遇到加號(hào)的處理算法。

3）加號(hào)和減號(hào)處理過之后如果sum等于100，即可把結(jié)果輸出。

4）算法實(shí)現(xiàn)之后得到的結(jié)果如下：

6 結(jié)束語

本文給出了完全多叉樹的定義，存儲(chǔ)，遍歷算法。提出了一種完全多叉樹葉子結(jié)點(diǎn)構(gòu)造搜索模型的算法，并給出了一個(gè)通過這種算法解決的問題。該文也給出了這個(gè)問題的整體解決思路，解決算法和實(shí)驗(yàn)結(jié)果。為需要用完全多叉樹解決的問題提供算法支持和解決思路。

參考文獻(xiàn)：

[1] 張乃孝.三叉樹結(jié)構(gòu)及其實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展，1993：50-54， 41.

[2] 毛國(guó)君，楊滌非.一種三叉樹的存儲(chǔ)結(jié)構(gòu)及其基本操作的實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展，1994，31（5）：62-65.

[3] 林桂伍.多叉樹結(jié)構(gòu)及其實(shí)現(xiàn)[J].福州大學(xué)學(xué)報(bào)（自然科學(xué)版），1995，23（1）：16-19.

[4] Sartaj Sahni.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用（Java 語言描述）[M].孔芳，高偉，譯.北京：中國(guó)水利水電出版社，2007：315-318.

[5] 袁玲，鄧小燕.一種基于多叉樹的檢索方法及其應(yīng)用[J].計(jì)算技術(shù)與自動(dòng)化，2011，30（3）：139-141.

[6] 盛魁.二叉樹的遍歷探究與應(yīng)用[J].電腦知識(shí)與技術(shù)，2008，3（5）：1014-1015，1034.