吳潔明，李碩征，史建宜

（北方工業(yè)大學(xué)信息工程學(xué)院，北京100144）

0 引 言

實際應(yīng)用中，經(jīng)常利用樹形結(jié)構(gòu)反映現(xiàn)實中的組織結(jié)構(gòu)關(guān)系。但是，如果這些組織中的實體之間具有很強的相關(guān)性，即各實體之間具有較強的相互影響，那么映射形成的樹形結(jié)構(gòu)的各個節(jié)點的取值就會也具有相關(guān)性。這對進一步應(yīng)用造成了一定困難。為了解決這一問題，為了解決這個問題，本文提出了一種基于樹形結(jié)構(gòu)的驗證方法。

樹形結(jié)構(gòu)能夠很好地反映現(xiàn)實中的某些組織關(guān)系，如組織結(jié)構(gòu)等，而且具有便于查詢、層級關(guān)系清晰等優(yōu)點［1］。因此在實際應(yīng)用中，經(jīng)常將項目的各數(shù)據(jù)實體或元素（下文中統(tǒng)稱為元素）映射成樹形結(jié)構(gòu)，各元素映射成樹中的各節(jié)點。期望可以通過樹形機構(gòu)層級關(guān)系清晰的優(yōu)勢，結(jié)合增、刪、改、查等操作以解決實際問題。然而，在實際應(yīng)用中經(jīng)常會遇到符合樹形結(jié)構(gòu)的各元素之間具有相關(guān)性的情況，即某一個元素是否出現(xiàn)或者取值情況，對其他元素是否出現(xiàn)或取值產(chǎn)生影響。因而，在使用各元素執(zhí)行進一步操作的之前需要對各元素的正確性及合法性進行驗證。

本文提出的這種基于樹形結(jié)構(gòu)的驗證方法，可以通過驗證現(xiàn)實中各實體映射出的樹形結(jié)構(gòu)中各節(jié)點取值的正確性，進而驗證各個元素映射成的樹形結(jié)構(gòu)的正確性。文章首先簡要介紹了樹形結(jié)構(gòu)的部分相關(guān)算法，在此基礎(chǔ)上對算法進行了詳細描述并分析了該算法的時間開銷，然后通過一個實例介紹了算法的使用，最后對本文進行了總結(jié)和展望。

1 相關(guān)研究

作為一種十分重要的數(shù)據(jù)結(jié)構(gòu)，樹型結(jié)構(gòu)可以很方便的反映現(xiàn)實世界的組織結(jié)構(gòu)，因此得到了廣泛深入的研究和使用。在數(shù)據(jù)查找算法中，樹形結(jié)構(gòu)具有十分重要的作用。在計算機科學(xué)中，查找樹是最重要的一類數(shù)據(jù)結(jié)構(gòu)，是一種具有查找、插入和刪除操作的元素集合［1］。除二叉查找樹外，B樹、AVL樹和2－3樹等也是這方面研究的重點［2］。

由于樹本身就是連通的無回路圖，因此可以應(yīng)用樹形結(jié)構(gòu)輔助研究圖的問題，例如圖的遍歷算法、最短路徑算法等問題［2］。

在數(shù)據(jù)挖掘方面，F(xiàn)P＿Growth算法中需要構(gòu)建FP－tree幫助壓縮數(shù)據(jù)庫。FP－Tree蘊涵了目標(biāo)數(shù)據(jù)中所有的頻繁項集。因此，其后的頻繁項集的挖掘只需要將FP－growth算法應(yīng)用到FP－tree上［3，4］。本文正是借鑒了這種思想，把各元素間的關(guān)系映射成樹形結(jié)構(gòu)，從而利用樹形結(jié)構(gòu)的特點，借鑒已有的對于樹形結(jié)構(gòu)的研究成果解決元素相關(guān)性驗證的問題。

2 預(yù)備知識

本文中所指的樹形結(jié)構(gòu)的節(jié)點相關(guān)性，是指在某一個具體的樹形結(jié)構(gòu)中，一個節(jié)點對其他同級或不同級的節(jié)點造成的影響。包括:其他節(jié)點是否出現(xiàn)、該節(jié)點處的取值變化等。一個節(jié)點可以對與其同級的節(jié)點、較小層級的節(jié)點或較大層級的節(jié)點造成影響。本文中涉及的相關(guān)性有如下幾條說明需要注意。

說明1:樹形結(jié)構(gòu)中各節(jié)點都或者會對其他節(jié)點產(chǎn)生影響或者受其他節(jié)點的影響。其中根節(jié)點影響所有其子節(jié)點的出現(xiàn)情況，葉子節(jié)點受其所有祖先節(jié)點的影響。

說明2:設(shè)xi、xj，是兩個節(jié)點，若xi的存在情況（或取值）會影響xj的存在情況（或取值），并且xj是比xi層級較高的節(jié)點，那么xi不在以xj為根節(jié)點的子樹上。也就是說，本文提出的驗證方法不考慮于輸出對輸入有反饋存在的情況。

對于實際業(yè)務(wù)中，數(shù)據(jù)或元素根據(jù)是否會受到其他數(shù)據(jù)或元素的影響可以分為基本元素和條件元素。其中，基本元素的取值或是否存在不受其他的元素或數(shù)據(jù)的影響，而條件元素的取值或是否存在則要受到這種影響。此外，實際業(yè)務(wù)中元素的取值是否可以為空也是需要考慮的情況，通常稱之為選擇性。根據(jù)不同的選擇性，可以將元素分為必選元素和可選元素兩類［5］?？蛇x元素的取值不可為空，而必選元素的取值則可以為空。

將以上各種情況映射到樹形結(jié)構(gòu)中，可以將所有的節(jié)點分為基本必備節(jié)點、基本可選節(jié)點、條件必備節(jié)點和條件可選節(jié)點四類。對于一棵樹來說，只有其根節(jié)點是基本節(jié)點，而且是基本必備節(jié)點，其他各個節(jié)點都是條件節(jié)點。對于森林來說，每棵樹的根節(jié)點都是基本必備節(jié)點。這是因為，一棵樹中至少要有根節(jié)點存在，并且可以只有根節(jié)點而沒有其他節(jié)點。

對于節(jié)點x，y，節(jié)點集合X，Y，x∈X，y∈Y，設(shè)D（x）表示節(jié)點x存在的充分條件，若對于集合Y中任意一節(jié)點y，滿足y＝D（x），表示只有在集合Y中各節(jié)點存在的情況下，節(jié)點x才存在。

設(shè)P（x）表示節(jié)點x存在的時候能夠存在的節(jié)點。若對于集合Y中任意一節(jié)點y，滿足y＝P（x），則節(jié)點x存在的情況下，結(jié)合Y中的節(jié)點y才有可能存在。

由上面兩個設(shè)定可知，y＝P（D（x））以及P－1（x）＝D（x）。

3 算法描述

因為森林是由多個樹組成的，相當(dāng)于包含一個或多個樹的集合，所以只考慮一個樹的情況。此外，由于是驗證某一樹形結(jié)構(gòu)的合法性，則必然會存在一個標(biāo)準(zhǔn)的結(jié)構(gòu)，我們把這個標(biāo)準(zhǔn)結(jié)構(gòu)也表示成樹的形式，并稱之為標(biāo)準(zhǔn)樹。與之相對應(yīng)的，把需要驗證的樹形結(jié)構(gòu)稱為待測樹。

首先，根據(jù)標(biāo)準(zhǔn)的組織結(jié)構(gòu)生成標(biāo)準(zhǔn)樹。在實際應(yīng)用中，樹形結(jié)構(gòu)通常用于表示組織結(jié)構(gòu)情況，樹的節(jié)點表示組織中的某一元素。因此生成的標(biāo)準(zhǔn)樹中保留節(jié)點名稱和元素名稱相同。這一步中最大的問題在于如何處理條件節(jié)點，因為在樹的定義中，并沒有考慮節(jié)點可能為空的情況，而且在實際中各節(jié)點的取值也有可能出現(xiàn)變化。我們的解決方法是增加虛節(jié)點，將各個可能的取值看作是多個不同的虛節(jié)點。此外，若某一節(jié)點的取值為空，則認為該節(jié)點不存在。例如圖1中所示的樹中，節(jié)點b的取值可能為0和1兩種情況，則在b右側(cè)增加一個節(jié)點，節(jié)點名稱不變且新增節(jié)點和原節(jié)點名稱相同，值分別為0和1，如圖2所示。通過增加這種虛節(jié)點的方式，將標(biāo)準(zhǔn)結(jié)構(gòu)映射成標(biāo)準(zhǔn)樹。若待測樹中，某一個節(jié)點為空，則該節(jié)點及以其為根節(jié)點的子樹不可能存在。這樣，將節(jié)點取值的問題轉(zhuǎn)化成節(jié)點是否為空，即節(jié)點是否存在的問題。若圖1中的樹的節(jié)點b的取值為0，則只需要在圖2的樹形結(jié)構(gòu)中去掉節(jié)點b（1）的分支即可。需要注意的是，在生成虛節(jié)點的時候，以該節(jié)點為根節(jié)點的子樹也要復(fù)制到新的虛節(jié)點下面。

圖1 一個簡單的樹型結(jié)構(gòu)

生成標(biāo)準(zhǔn)樹后，按照樹的廣度優(yōu)先遍歷順序為標(biāo)準(zhǔn)樹中各個節(jié)點排序［6－8］，包括上一步生成的虛節(jié)點。從根節(jié)點開始，自上至下逐層排序；在同一層中按照從左到右的順序?qū)?jié)點進行排序。這樣一來較高層級的節(jié)點的序號小于較低層級節(jié)點的序號；同一層級中，左側(cè)節(jié)點的序號小于右側(cè)節(jié)點的序號。設(shè)標(biāo)準(zhǔn)樹為t，則t＝｛x0，x1，…，xn｝。xi表示樹中的節(jié)點，n＋1為節(jié)點總數(shù)，i∈｛0～n｝表示各節(jié)點的序號。同時，根據(jù)標(biāo)準(zhǔn)情況記錄各節(jié)點的名稱和取值以及各個節(jié)點出現(xiàn)的充分條件，即記錄節(jié)點xi和其對應(yīng)的D（xi）。

圖2 生成虛節(jié)點后的樹形結(jié)構(gòu)

采用深度優(yōu)先遍歷的方法，遍歷標(biāo)準(zhǔn)樹和待測樹。在此過程中，通過節(jié)點名稱，驗證各個節(jié)點的父節(jié)點是否正確。由于待測樹和標(biāo)準(zhǔn)樹在實際應(yīng)用中，應(yīng)該表示的是同一組織結(jié)構(gòu)，因此，待測樹和標(biāo)準(zhǔn)樹中對應(yīng)節(jié)點的名稱應(yīng)該相同。又因為之前生成的虛節(jié)點的根節(jié)點沒有變化，所以虛節(jié)點不影響這步驗證的正確性。

在這一次遍歷中還要為待測樹中各節(jié)點生成序號。生成的方法是根據(jù)名稱同標(biāo)準(zhǔn)樹中對應(yīng)節(jié)點的序號相匹配。若同一名稱可以在標(biāo)準(zhǔn)樹中找到多個節(jié)點，則進一步比較節(jié)點的取值。例如標(biāo)準(zhǔn)樹中的節(jié)點xi和xj的名稱都為a，值分別為0和1，待測樹中某一節(jié)點的名稱為a，值為1，則該節(jié)點的序號為j，節(jié)點表示為xj’。由之前記錄的xi和D（xi），可以得到對應(yīng)的xi’和D（xi’）。

驗證完待測樹中各節(jié)點的父節(jié)點后，還需要進一步驗證各節(jié)點之間的相關(guān)性。按照廣度優(yōu)先遍歷的順序再一次遍歷待測樹，并記錄待測樹中的各節(jié)點的序號。在遍歷過程中完成對整個待測樹各節(jié)點相關(guān)性的驗證。具體方法如下:

（1）刪除待測樹的根節(jié)點，整個待測樹變成待測森林。待測森林中各個新生成的待測樹的根節(jié)點均變成基本節(jié)點（仍然不能區(qū)分是必備節(jié)點或者可選節(jié)點）。

（2）按照從左到右的順序，驗證各個新生成的待測樹的根節(jié)點。設(shè)集合X’＝｛x1’，x2’，…，xm’｝是D（xi’）的解的集合，則節(jié)點xj’∈X’存在，是節(jié)點xi’存在充分條件。當(dāng)m＜i時，若集合X’中各元素表示的節(jié)點都已遍歷到，則xi’通過驗證。當(dāng)m＞i時，若xj’∈X’的序號j＜i，只需判斷節(jié)點xj’在xi’之前是否遍歷到即可；若j＞i，則將節(jié)點xj’視為基本必備節(jié)點，同時認為xi’通過驗證。若xi－1’＝P（xk’），且i－1＞k，xi－1’不存在，則當(dāng)遍歷到xi’時，就可以認為待測樹不符合標(biāo)準(zhǔn)結(jié)構(gòu)，xk’和以其為根節(jié)點的子樹不應(yīng)該在待測樹中存在。

（3）當(dāng)新生成的各樹的各節(jié)點遍歷完畢后，刪除各個根節(jié)點，生成新的森林和新的待測樹。

（4）重復(fù)b到c，直到原待測樹中各節(jié)點均完成遍歷。關(guān)于這個算法有以下幾點說明。

1）由于之前已經(jīng)對待測樹進行了處理，通過生成虛節(jié)點，保證在處理后的待測樹中各節(jié)點只能有單一取值，因此D（x）中不存在或的關(guān)系，全部節(jié)點為且的關(guān)系。即只有集合X’中各元素對應(yīng)的節(jié)點都存在的情況下，xi才能存在。

2）根據(jù)y＝D（x）以及x＝P（y）可知，若節(jié)點y存在是x存在的充分條件，則若節(jié)點x存在，必能推出節(jié)點y一定存在。

3）在這個算法中，不對標(biāo)準(zhǔn)樹和待測樹的節(jié)點分配序號也能完成驗證。在第二次遍歷的時候，需要比較待測樹和標(biāo)準(zhǔn)樹中各節(jié)點的名稱和值。根據(jù)上文的敘述，驗證節(jié)點x時需要查找所有的D（x）是否存在。設(shè)所有完成遍歷的節(jié)點集合為N，那么在這種情況下，每次查找都要從頭開始遍歷集合N中元素。而采用分配序號的方法，N中各元素按序號順序排列，在N中查找特定元素的算法就可以根據(jù)具體需求選取。

上面的算法可以表示成偽碼的形式:

4 時間開銷

整個算法需要對待測樹和標(biāo)準(zhǔn)樹分別進行兩次完全遍歷。因此，該方法執(zhí)行時耗費的時間必然和標(biāo)準(zhǔn)樹的節(jié)點數(shù)n以及待測樹的節(jié)點數(shù)n’有關(guān)。另外，在判斷待測樹中某一節(jié)點x的存在是否合法的時候，需要查找D（x）中各節(jié)點是否被包含在已完成遍歷的節(jié)點集合中。由于對所有節(jié)點分配了序號，因此這一步相當(dāng)于在一組已排序的數(shù)字集合中查找特點數(shù)字。其時間開銷取決于具體的查找算法。如果t（n）表示完全遍歷標(biāo)準(zhǔn)樹的時間開銷，t（n’）表示完全遍歷待測樹的時間開銷，t（i）表示查找數(shù)字i的時間開銷，則總的時間開銷T＝2t（n）＋2t（n’）＋∑t（i）。

5 實例研究

圖3所示是一個已經(jīng)完成序號分配的待測樹T，其中各節(jié)點存在的充分條件見表1。

圖3 待測樹T

待測樹T的驗證過程如下:

（1）驗證x0，通過。

（2）依次驗證x1，x2，x3，這3個節(jié)點存在的充分條件都是x0，故x1，x2，x3均通過驗證。

（3）驗證x4，D（x4）＝｛x0，x8｝，x0已通過驗證；8＞4，所以認為x4通過驗證，將x8插入待驗證的節(jié)點集合。

（4）驗證x5，由于x1已存在，故通過驗證。

（5）x6，x7的充分條件是x3，已存在，故通過驗證。

（6）D（x8）＝｛x3，x7｝，x3，x7均已存在，所以x8通過驗證。

（7）x9存在的充分條件x4已存在，故x9通過驗證。

（8）x10存在的充分條件x5已存在，故x10通過驗證。

（9）D（x11）＝｛x1，x7，x10｝，節(jié)點x1，x7，x10都已存在，所以x11通過驗證。

表1 T中各節(jié)點存在的充分條件

待測樹中節(jié)點xi存在的充分條件是D（xi）也存在。所有節(jié)點均滿足這個條件的話，我們就認為待測樹在節(jié)點相關(guān)性方面符合需求。

6 結(jié)束語

當(dāng)某一項目的所有數(shù)據(jù)項的組織結(jié)構(gòu)符合樹形結(jié)構(gòu)時，各個數(shù)據(jù)項或元素可以看作是樹的節(jié)點。若各個數(shù)據(jù)項之間具有相關(guān)性，如何驗證各個數(shù)據(jù)項的取值以及整體的組織結(jié)構(gòu)，這是實際應(yīng)用中經(jīng)常遇到的一個問題。為了解決這個問題，本文提出了一個算法。通過驗證造成某一個節(jié)點取得某一特定值的充分條件是否成立，來驗證整個結(jié)構(gòu)。

本文提出的算法可以完成驗證工作，但是整個算法需要考慮待測樹和標(biāo)準(zhǔn)樹兩個樹形結(jié)構(gòu)。若待測樹符合需求，則整個驗證過程中，對每個樹形結(jié)構(gòu)都要完成兩次完全遍歷。此外還要進行多次的查找運算，時間開銷較大。因此下一步的工作就是探索采用恰當(dāng)?shù)姆椒ǎ热鐪p少樹的完全遍歷的次數(shù)，以減少整個算法的時間開銷。

［1］PAN Yan.Introduction to the design and analysis of algorithms［M］.2nd ed.Beijing:Tsinghua University Press，2007（in Chinese）.［潘彥.算法設(shè)計與分析基礎(chǔ)［M］.2版.北京:清華大學(xué)出版社，2007.］

［2］PAN Jingui，GU Tiecheng，LI Chengfa，et al.Introduction to algorithms［M］.2nd ed.Beijing:China Machine Press，2006（in Chinese）.［潘金貴，顧鐵成，李成法，等.算法導(dǎo)論［M］.2版.北京:機械工業(yè)出版社，2006.］

［3］CHEN Yiming，LI Zhoujun，F(xiàn)U Zigang.Constrained association rule mining algorithm based on FP－Tree［J］.Computer Engineering and Design，2007，28（9）:4450－4454（in Chinese）.［陳義明，李舟軍，傅自剛.基于FP－Tree的約束關(guān)聯(lián)規(guī)則挖掘算法［J］.計算機工程與設(shè)計，2007，28（9）:4450－4454.］

［4］ZHOU Qinliang，LI Yuchen，GONG Aiguo.New algorithms for effectively creating conditional pattern bases of FP－Tree［J］.Computer Application，2006，26（6）:1418－1421（in Chinese）.［周欽亮，李玉忱，公愛國.一種新的高效生成FPTree條件模式基的算法［J］.計算機應(yīng)用，2006，26（6）:1418－1421.］

［5］DENG Die，LIU Youcheng.Compliance test of software［J］.Journal of Beijing University of Aeronautics and Astronautics，1997，23（1）:68－73（in Chinese）.［鄧昳，劉又誠.軟件標(biāo)準(zhǔn)符合性測試［J］.北京航空航天大學(xué)學(xué)報，1997，23（1）:68－73.］

［6］YAN Weimin，WU Weimin.Introduction to data structures（C）［M］.Beijing:Tsinghua University Press，2007（in Chinese）.［嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.北京:清華大學(xué)出版社，2007.］

［7］GUO Jinhua，ZHAN Ming.On the binary tree traversal［J］.Science and Technology Information，2010（17）:65（in Chinese）.［郭金華，占明.淺議二叉樹的遍歷［J］.科技信息，2010（17）:65.］

［8］WANG Fangxiu，ZHOU Kang.Non－recursive algorithm about two binary tree traversal based on a single linked list［J］.Journal of Wuhan Polytechnic University，2012，31（4）:59－63（in Chinese）.［王防修，周康.基于單鏈表的二叉樹非遞歸遍歷算法［J］.武漢工業(yè)學(xué)院學(xué)報，2012，31（4）:59－63.］

［9］YU Yanan，ZHOU Xi.Optimization strategy in generation of path condition［J］.Computer Engineering and Design，2012，33（10）:3995－4003（in Chinese）.［于亞楠，周喜.路徑條件生成中的優(yōu)化策略［J］.計算機工程與設(shè)計，2012，33（10）:3995－4003.］

［10］ZHOU Yan，HOU Zhengfeng，HE Ling.Fast multi－pattern string matching algorithm based on sequential binary tree［J］.Computer Engineering，2010，36（17）:42－44（in Chinese）.［周燕，候整風(fēng)，何玲.基于有序二叉樹的快速多模式字符串匹配算法［J］.計算機工程，2010，36（17）:42－44.］

［11］YU Xiushan，YU Hongming.Software testing new technologies and practices［M］.Beijing:Publishing House of Electronics Industry，2006:100－121（in Chinese）.［于秀山，于洪敏，軟件測試新技術(shù)與實踐［M］.北京:電子工業(yè)出版社，2006:100－121.］