生物分類二歧檢索表的建立與檢索算法設(shè)計問題描述分類檢索表

1、生物分類二歧檢索表的建立與檢索 算法設(shè)計一、問題描述： 分類檢索表是以區(qū)分生物為目的而編制的表。 目前， 常用的是二歧分類檢索表。 這種檢 索表把同一類別的動植物， 根據(jù)一對或幾對相對性狀的區(qū)別， 分成相對應(yīng)的兩個分支。 接著， 再根據(jù)另一對或幾對相對性狀， 把上面的每個分支再分成相對應(yīng)的兩個分支， 好似二歧式分 枝一樣，如此，逐級排列下去，直到編制出包括全部生物類群的分類檢索表。檢索表分為兩種：定距式檢索表和平行式檢索表，分別為例1 、例 2例 1 ：1 植物體無根、莖、葉的分化，無胚 。2 植物體不為藻類和菌類所組成的共生體。3 植物體內(nèi)有葉綠素和其他色素，為自養(yǎng)生活方式 藻類植物門3 植

2、物體內(nèi)無葉綠素和其他色素，為異養(yǎng)生活方式 菌類植物門2 植物體為藻類和菌類所組成的共生體 地衣植物門1 植物體有根、莖、葉的分化，有胚 。4 植物體有莖、葉而無真根 苔蘚植物門4植物體有莖、葉面有真根5 產(chǎn)生孢子 蕨類植物門5 產(chǎn)生種子 種子植物門例 2 ：1 植物體無根、莖、葉的分化，無胚 21 植物體有根、莖、葉的分化，有胚 42 由藻類和菌類所組成的共生體 地衣植物門2 非藻類和菌類所組成的共生體 33 植物體有葉綠素或其他色素，為自養(yǎng)生活方式 藻類植物門3 植物體無葉綠素或其他色素，為異養(yǎng)生活方式 菌類植物門4 植物體有莖、葉，而無真根 苔蘚植物門4 植物體有莖、葉，而有真根 55 產(chǎn)

3、生孢子 蕨類植物門5 產(chǎn)生種子 種子植物門二、生物分類檢索表與二叉樹 生物分類檢索表是二叉樹的思想在生物學(xué)中的具體表達(dá)， 但是和二叉樹有一點(diǎn)不同的就 是二叉樹存在一個根節(jié)點(diǎn)， 而檢索表并不存在根節(jié)點(diǎn)。 當(dāng)然， 我們可以人為的加上一個根節(jié) 點(diǎn)，例如針對上面的例子，就可以把根節(jié)點(diǎn)設(shè)置為：植物界。 將檢索表用二叉樹的形式來表 達(dá)，我們會發(fā)現(xiàn)： 該二叉樹的所有的樹葉節(jié)點(diǎn)都存儲的是具體的種屬信息， 而所有分支節(jié)點(diǎn) 都存儲的是生物的性狀特征。根據(jù)上面的例子，如圖 1 所示。圖1生物檢索表的二叉樹表達(dá)形式二、算法設(shè)計從而實現(xiàn)對生物檢，輸出它的檢索路本算法實現(xiàn)兩個目標(biāo)， 第一個是根據(jù)已有的生物檢索表建立二叉樹

4、, 索表的數(shù)字化管理；第二個是根據(jù)給定的一個分類單元如蕨類植物門 徑。檢索表二叉樹的建立，采用左右指針表示法的鏈接表示方式。創(chuàng)立結(jié)構(gòu)體數(shù)據(jù)類型，包含一個儲存信息的變量，以及指向左子樹的指針和右子樹的指針?？紤]到正常的檢索順序， 應(yīng)該從根節(jié)點(diǎn)開始建立， 即按照檢索表，從第一級的分類性狀開始，依次向下，直到具體的 某一個分類單元。如此，即建立了生物檢索表的二叉樹。檢索路徑獲取的算法，首先使用后根周游序列進(jìn)行周游。由于儲存有具體分類單元信息的節(jié)點(diǎn)的特性為沒有左子樹和右子樹，因而可根據(jù)這一特點(diǎn)對節(jié)點(diǎn)進(jìn)行判斷，將滿足這一特點(diǎn)的節(jié)點(diǎn)所儲存的信息與需要進(jìn)行檢索的信息進(jìn)行比照，如果相互匹配，那么開始進(jìn)行檢索路徑的分析。從該節(jié)點(diǎn)開始，進(jìn)行中根周游，依次向上找到其父節(jié)點(diǎn)、父節(jié)點(diǎn)的父節(jié)點(diǎn) 由 于要與通常的生物學(xué)中的檢索路徑的表達(dá)方式相一致，即從第一級的分類性狀開始，而在周游過程中是從第n級的分類性