節(jié)點(diǎn)具有相關(guān)性的樹形結(jié)構(gòu)的驗(yàn)證方法

吳潔明，李碩征，史建宜

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

0 引 言

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

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

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

1 相關(guān)研究

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

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

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

2 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

3 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 時(shí)間開銷

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

5 實(shí)例研究

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

圖3 待測樹T

待測樹T的驗(yàn)證過程如下:

（1）驗(yàn)證x0，通過。

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

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

（4）驗(yàn)證x5，由于x1已存在，故通過驗(yàn)證。

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

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

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

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

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

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

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

6 結(jié)束語

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

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

［1］PAN Yan.Introduction to the design and analysis of algorithms［M］.2nd ed.Beijing:Tsinghua University Press，2007（in Chinese）.［潘彥.算法設(shè)計(jì)與分析基礎(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版.北京:機(jī)械工業(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］.計(jì)算機(jī)工程與設(shè)計(jì)，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］.計(jì)算機(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é)報(bào)，1997，23（1）:68－73.］

［6］YAN Weimin，WU Weimin.Introduction to data structures（C）［M］.Beijing:Tsinghua University Press，2007（in Chinese）.［嚴(yán)蔚敏，吳偉民.數(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é)報(bào)，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］.計(jì)算機(jī)工程與設(shè)計(jì)，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］.計(jì)算機(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ù)與實(shí)踐［M］.北京:電子工業(yè)出版社，2006:100－121.］