逆序樹在求解一維數(shù)組最長升序序列問題中的應(yīng)用

摘 要： 針對一維數(shù)組中求最長升序序列問題，在研究樹形結(jié)構(gòu)和分析任務(wù)需求的基礎(chǔ)上，提出采用區(qū)別于傳統(tǒng)樹的逆序樹結(jié)構(gòu)進行計算，采用深度優(yōu)先算法策略查找路徑。逆序樹采用子節(jié)點指向父節(jié)點的節(jié)點逆序指向方式，在建樹過程中不用為每個節(jié)點考慮子節(jié)點的數(shù)量，克服了不可預(yù)見的存儲分配和節(jié)點指向問題，能有效地找出全部升序路徑，最終找出一維數(shù)組中全局最長的升序序列。在此基礎(chǔ)上實現(xiàn)的Java程序驗證了逆序樹結(jié)構(gòu)的有效性。

關(guān)鍵詞： 逆序樹； 傳統(tǒng)樹； 節(jié)點； 深度優(yōu)先； 最長升序序列

中圖分類號：TP312 文獻標(biāo)志碼：A 文章編號：1006-8228（2013）03-37-02

0 引言

在算法設(shè)計中，經(jīng)常有求解最長升序序列的問題，本文以求解一維數(shù)組中最長升序序列為例，對由n個隨機數(shù)組成的一維數(shù)組，如int array[]={3，18，7，14，10，12，23，41，16，24，59，37}，找出其中的最長升序序列，升序的各元素可以不相鄰。

1 求解分析

尋找最長的升序序列，前提是先找出所有的升序序列，再從中選出最長的序列，也就是包含節(jié)點最多的序列。根據(jù)問題的需要，初步判斷用深度優(yōu)先的策略，以樹為結(jié)構(gòu)進行查找。對一維數(shù)組中的每一個元素，以其作為根節(jié)點，搜索數(shù)組中后續(xù)比其大的元素作子節(jié)點建樹，都可能產(chǎn)生一棵枝繁葉茂的樹；從每棵樹中選出從根節(jié)點到葉子節(jié)點最長的路徑作為數(shù)組中由該元素開始的最長升序序列；遍歷所有創(chuàng)建的樹，再從這些局部最長升序序列中選出全局最長的升序序列[1]。全局最長的升序序列可能存在多個。

求解最長升序序列的過程，就是創(chuàng)建節(jié)點值遞增的樹的過程。在創(chuàng)建樹的過程中，對樹的每一個節(jié)點，不能預(yù)先判斷其有多少個子節(jié)點，或者有沒有子節(jié)點，但能清楚地確定其父節(jié)點。鑒于此，采用節(jié)點順序指向的傳統(tǒng)樹結(jié)構(gòu)不利于問題求解，確定以逆序指向的逆序樹結(jié)構(gòu)來求解問題，以深度優(yōu)先為計算策略。

1.1 傳統(tǒng)樹

樹（tree）是包含n（n>0）個元素的有窮集合[2]，其中：

⑴ 每個元素稱為節(jié)點（node）；

⑵ 有一個特定的節(jié)點被稱為根節(jié)點或樹根（root）；

⑶ 除根節(jié)點之外的其余數(shù)據(jù)元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。

樹具有以下特點：

⑴ 每個節(jié)點有零個或多個子節(jié)點；

⑵ 沒有子節(jié)點的節(jié)點稱為葉子節(jié)點；

⑶ 每個節(jié)點只有一個父節(jié)點；

⑷ 沒有父節(jié)點的節(jié)點稱為根節(jié)點。

本文將上述數(shù)據(jù)結(jié)構(gòu)教材中描述的樹稱為“傳統(tǒng)樹”，以示區(qū)別。

在傳統(tǒng)樹結(jié)構(gòu)中，一棵樹由根（root）節(jié)點開始，根節(jié)點的層數(shù)為1，根節(jié)點指向2層節(jié)點，2層節(jié)點是根節(jié)點的子（son）節(jié)點，根節(jié)點是2層節(jié)點的父（father）節(jié)點；2層中的每一個節(jié)點各自指向3層節(jié)點中自己的子節(jié)點，以此類推。

1.2 逆序樹

這里求解最長升序序列，即尋找樹中的最長路徑。對樹中的每一個節(jié)點，并不能預(yù)先確定選擇數(shù)組中哪一個數(shù)為其子節(jié)點會產(chǎn)生最長路徑，因此只有選擇數(shù)組中序號在其后、值比其大的全部的數(shù)來創(chuàng)建子節(jié)點，進而產(chǎn)生全部可能的路徑，再從中選出最長的路徑。這種情況下，采用傳統(tǒng)樹的父節(jié)點指向子節(jié)點的順序方式，需要占用大量的存儲空間來記錄每個節(jié)點的子節(jié)點及其編號，更需要動態(tài)增量空間來記錄子節(jié)點的子節(jié)點[3]?？紤]到每一個節(jié)點的父節(jié)點是確定并且惟一的，采取子節(jié)點指向父節(jié)點的逆序方式，樹中節(jié)點的指向順序與傳統(tǒng)的父節(jié)點指向子節(jié)點相反，本文將這種節(jié)點逆序指向的樹稱為逆序樹，將節(jié)點所在的層數(shù)稱為節(jié)點的深度[4]。

用逆序樹求解最長路徑，克服了傳統(tǒng)樹父節(jié)點對多個子節(jié)點的復(fù)雜指向問題，避免了為不可預(yù)見的子節(jié)點動態(tài)分配存儲空間的問題，能獲得比傳統(tǒng)樹更高的效率。以文中求解問題的簡略搜索路徑為例，傳統(tǒng)樹與逆序樹結(jié)構(gòu)對比如圖1、圖2所示。

1.3 深度優(yōu)先

本問題求解的是最長升序序列，采用逆序樹結(jié)構(gòu)，尋找樹中最長的路徑，也就是尋找深度最大的節(jié)點。采用深度優(yōu)先策略[5]，從樹中根節(jié)點出發(fā)，沿每一條路徑找到葉子節(jié)點，再回退到上一層節(jié)點，沿另外的分枝路徑尋找下一層節(jié)點，直至找到葉子節(jié)點……。創(chuàng)建樹的過程，即是遞歸地為每一個節(jié)點尋找子節(jié)點的過程；對數(shù)組中的每一個元素，動態(tài)地創(chuàng)建子樹，最終完成整棵樹的創(chuàng)建。在遞歸過程中，對節(jié)點深度進行計算和選擇性存儲，只選擇那些深度更大的葉子節(jié)點及其到根節(jié)點的完整路徑進行存儲。存儲的過程只關(guān)注節(jié)點深度，不關(guān)注廣度。

2 算法設(shè)計

定義全局變量Ldepth，記錄最大的節(jié)點深度；定義全局變量count_longest，計數(shù)最長路徑。在逆序樹中，為樹的節(jié)點定義節(jié)點類Node，在Node中記錄該節(jié)點的父節(jié)點Node father，存儲該節(jié)點元素的值value=array[i]，記錄節(jié)點元素值在數(shù)組中的下標(biāo)tid=i，記錄該節(jié)點的深度depth=father.depth+1，構(gòu)造尋找子節(jié)點的方法Seekson（Node nn，int array[]）。Seekson（）是一個遞歸查找兒子節(jié)點的方法，每找到一個葉子節(jié)點，即終止該條路徑查找，比較該葉子節(jié)點的depth與Ldepth，如果depth大于或等于Ldepth則記錄該節(jié)點，再回退到上一級節(jié)點尋找另外的分枝路徑。最終輸出最長的路徑。

3 程序?qū)崿F(xiàn)

該算法用Java編程實現(xiàn)[6]：

4 結(jié)束語

本文利用逆序樹結(jié)構(gòu)，較好地解決了求解一維數(shù)組的最長升序序列問題。相對于傳統(tǒng)樹，逆序樹依靠其節(jié)點逆序指向的特征，能更加有效地解決需要動態(tài)分配存儲的問題，所給出的程序執(zhí)行效率很高。

參考文獻：

[1] 王敏.基于遍歷搜索二叉樹中最長路徑的算法研究[J].現(xiàn)代電子技

術(shù)，2010.34（8）：54-55

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，1997.

[3] 劉胡瑤.異構(gòu)信息資源庫的構(gòu)建及其關(guān)鍵技術(shù)實現(xiàn)[J].計算機輔助設(shè)

計與圖形學(xué)學(xué)報，2005.17（3）： 578-583

[4] 王建新.最長路徑問題研究進展[J].計算機科學(xué)，2009.36（12）：1-4

[5] 王曉東.計算機算法設(shè)計與分析[M].電子工業(yè)出版社，2005.

[6] 柯林斯.數(shù)據(jù)結(jié)構(gòu)與Java類集框架[M].高等教育出版社，2002.