一種處理樹型結構數據的方法及系統的製作方法

2023-06-05 05:20:01 1

專利名稱：一種處理樹型結構數據的方法及系統的製作方法
技術領域：
本發明涉及數據處理技術，特別是涉及一種處理樹型結構數據的方法及系統。
背景技術：
在計算機應用中，經常需要處理樹型結構的數據，如公司內部組織結構、 產品分類、論壇帖子、郵件列表等等。參照圖1,是樹型結構數據的示例圖， 例如有一個論壇系統需要把主帖及相應的跟帖按照樹型的結構顯示出來，通過 帖子標題的縮進來體現帖子間的父子關係，為用戶更清晰地展示出帖子間的關 系。顯示效果如圖1所示，每條數據記錄為樹的一個結點，其中主帖為根結點， 所有跟帖為子結點。上例中，在資料庫設計時，記錄帖子信息的數據表至少包括以下欄位帖 子ID(id)，主帖ID (mainld)，父帖ID (parentld)，帖子標題(topic),帖 子內容(content),如圖2所示。其中，所述帖子ID為帖子創建時的序列號； 跟帖的標題可能與主帖的標題相同，也可能不同。目前，按照樹型結構顯示某個主帖及相應跟帖的方法是先從資料庫中讀 出mainld等於指定主帖ID的所有帖子(即所述主帖和它的所有跟帖)，並按 照讀取順序存入一個列表。由於帖子在資料庫中的存儲通常按照創建的先後順 序排列，所以列表中的帖子並不按照樹型結構排列。因此，下一步是使用遞歸 算法遍歷所述帖子列表，並在頁面上分層次顯示帖子。下面給出了一段實現所 述遞歸算法的示例代碼，能夠得到樹型結構排列的帖子序列，按照圖l所示效 果輸出顯示。void printPosts〖List posts,long rootld,int leve"LH for(int i=0;i《posts.size ;i++H Post post = (Post)posts.get〖i); if (post. parentld==rootldH print(post-topic,level)-printPosts(posts,post id,level+1)j但是，由於遞歸算法自身存在的計算性能問題，採用遞歸遍歷的方法處理 樹型結構的數據時速度較慢，而且當層次較多的情況下尤其明顯。例如一棵帖子樹總共有M個帖子，分為N層，則用遞歸算法顯示所述帖子數總共計算M木 N次，當N^N數量巨大時，需要耗費很多計算時間，造成系統不能及時響應 用戶查看數據的需求。 發明內容本發明所要解決的技術問題是提供一種處理樹型結構數據的方法及系統， 以解決採用遞歸遍歷的方法處理顯示樹型結構的數據速度較慢的問題。為解決上述技術問題，本發明提供了一種處理樹型結構數據的方法，包括 在結點數據中記錄用於標識數據層次關聯關係的信息； 讀取同 一棵樹的所有結點數據；根據所述數據層次關聯關係，對結點數據進行排序後得到數據列表；順序掃描所述列表並輸出。其中，所述排序是對標識數據層次關聯關係的信息所對應的ASCII編碼 值，按照ASCII編碼表的排序規則進行排序。其中，所述數據關聯關係以數字/字母與非數字/字母字符的組合表示。 優選的，根據非數字/字母字符的個數，判斷輸出數據時需要縮進的空格數。優選的，每棵樹的根結點數據設置相同的數字/字母。 本發明還提供了一種處理樹型結構數據的系統，包括 排序因子構造單元，用於對應每個結點數據，構造標識數據層次關聯關係 的排序因子；數據獲取單元，用於讀取同一棵樹的所有結點數據；排序單元，用於根據所述排序因子，對結點數據進行排序後得到數據列表；輸出單元，用於順序掃描所述列表並輸出。其中，所述排序單元對排序因子對應的ASCII編碼值，按照ASCII編碼表 的排序規則進行排序。其中，所述排序因子以數字/字母與非數字/字母字符的組合表示。 優選的，所述輸出單元根據非數字/字母字符的個數，判斷輸出數據時需要縮進的空格數。優選的，所述排序因子構造單元對每棵樹的根結點數據設置相同的數字/ 字母。與現有4支術相比，本發明具有以下優點本發明實施例在數據記錄中增加一個排序因子，用於標識每棵樹中各個結 點記錄的相互關聯關係，每增加一條數據記錄時構造相應的排序因子值。當需 要顯示一棵樹的所有節點記錄時，首先對所述因子值排序生成數據列表，然後 順序遍歷一次數據列表，就可以快速顯示樹型結構數據，從而P條低數據顯示的 開發複雜度，提高系統的處理效率，而且實現起來十分簡單。


圖l是現有技術中樹型結構數據的示例圖； 圖2是圖1示例中樹型結構數據的存儲結構示意圖； 圖3是本發明實施例中含有排序因子的樹型結構數據的邏輯結構示意圖； 圖4是本發明實施例所述顯示樹型結構數據的步驟流程圖； 圖5是本發明實施例中資料庫的數據存儲示意圖； 圖6是本發明實施例中按照排序因子排序後的數據列表示意圖； 圖7是本發明實施例所述顯示樹型結構數據的系統結構框圖。
具體實施方式
為使本發明的上述目的、特徵和優點能夠更加明顯易懂，下面結合附圖和具體實施方式
對本發明作進一步詳細的說明。本發明提供了 一種簡單高效的方法來顯示樹型結構數據，以下內容將以論 壇帖子的顯示為實施例進行詳細說明。為達到圖l所示的顯示效果，本發明實施例在資料庫設計時，在記錄帖子 信息的數據表中增加了一個欄位，作為在頁面上顯示帖子的一個排序因子。這 樣，所述數據表包括帖子ID ( id)、主帖ID (mainld)、父帖ID (parentld)、 帖子標題(topic)、帖子內容(content),排序因子(socter )、發帖時間 (time)、發帖者(name)等欄位，表中的每條帖子信息都記錄了所述內容。排序因子用於標識每條帖子信息與其他帖子間的關聯關係，參照圖3所 示，是含有排序因子的樹型結構數據的邏輯結構示意圖，通過所述排序因子可以獲知主帖與跟帖間的關係，以及跟帖與其他跟帖間的關係。排序因子是在帖子創建時構造的，例如每次新增一個主帖子時把這條數據記錄的sorter字 段設置為數字1，新增所述主帖的第一個跟帖時把相應的sorter欄位設置為 字符串1.1，如果再新增所述主帖的第二個跟帖則把相應欄位設置為字符串 1.2，新增第一個跟帖的跟帖時設置為1.1.1，以此類推下去，最後保存在數 據庫中的記錄如圖3所示。當一個帖子的跟帖數目較多時可以構造更長的排序因子。例如主帖的 sorter值為l,"跟帖一"的sorter值為1. Ol,"跟帖一的第一個跟帖"的sorter 值為1. 01. 01，"跟帖一的第十二個跟帖"的sorter值為1. 01. 12,以此類推。上述構造排序因子的方式是本發明的優選方案。對於樹型結構的數據，每 個主帖及其跟帖構成一棵樹，每棵樹可以有不同的排序因子表示法，如第一個 主帖及其跟帖由數字1開頭，第二個主帖及其跟帖由數字2開頭，以此類推。 但是這種表示方法並不適用於大數據量的帖子記錄，因為排序因子的第一位數 字會隨著帖子的增多而越排越大，從而增加排序因子的構造複雜度，佔用存儲 空間。由於每個主帖可以通過帖子ID加以區別，而區別每棵樹的排序因子意 義不大，所以本發明實施例優選的，對每棵樹的根結點(即每個主帖)都設置 相同的排序因子(如數字l)，設置簡單而不影響對每棵樹的數據操作。圖3所示是一個主帖及其跟帖的邏輯結構，並不代表數據的物理存儲結 構，而在實際的資料庫存儲中，所述帖子是按照帖子ID順序存儲的。所以， 從資料庫讀取某一主帖及其跟帖並顯示時，就需要根據排序因子對所有帖子進 行排序輸出。參照圖4,是本發明實施例所述顯示樹型結構數據的步驟流程圖。步驟401,當用戶登錄論壇瀏覽帖子時，頁面顯示出帖子列表，用戶選定 要查看的帖子標題，然後點擊該帖，向論壇伺服器發送顯示相應主帖及其跟帖 的請求。用戶選定的帖子可能是主帖，也可能是跟帖，下面步驟以跟帖為例進 行說明。步驟402，伺服器收到顯示某個帖子的請求，從請求中提取帖子ID等參 數。例如，請求顯示的帖子ID是78。步驟403，根據帖子ID從資料庫讀取主帖及其跟帖，讀取步驟是首先 取出與所述帖子ID對應的帖子數據，例如有這樣的SQL (結構化查詢語句)查詢select * from post where id=78;然後4艮據所述帖子數據可以得到主 帖ID ，記作rootld(rootlchPost.mainld),假設該值為10;再根據主帖ID 即rootld查詢資料庫，取得該主帖下所有的跟帖並按照sorter欄位(即排 序因子)排序，例如有這樣的SQL查詢select * from post where mainld=10 order by sorter。參照圖5，是數據存儲在資料庫的情況，是用戶發帖子的 順序，即按照帖子ID排序，因此按照讀取順序獲得的帖子在排序前即如圖5 所示。優選的，在讀取資料庫時為直接獲得主帖ID ,可以將每個帖子所屬的主 帖ID包含在請求參數中發送給伺服器，這樣伺服器就可以直接從請求中提取 主帖ID，減少了一次讀取資料庫的操作。當資料庫訪問量較大時，所述優選 方法就能夠顯著提高處理效率。步驟404，將從資料庫順序讀取的帖子按照排序因子排序，得到帖子列表。 通常， 一種簡便的排序方法是根據排序因子的構造方法及排序因子中每個字 符在ASCII編碼(美國標準信息交換碼)表中對應的ASCII編碼值，按照ASCII 編碼表的排序規則排序。即按照計算機中字符串的默認排序方法，根據字符串 中每個字符的ASCII編碼值排序。這樣，從資料庫取出來的帖子列表就是按照 要顯示的帖子順序排列的，圖5示例中排序後的帖子列表如圖6所示。舉例說明，將排序因子1與1. 1比較，先根據ASCII編碼值比較第一位都 是1,接著比較後面的字符串。由於"."字符的ASCII編碼值(46)在數字 的ASCII編碼值(48 - 57 )範圍之外，所以通過"."字符可以區別出主帖與 跟帖、跟帖與自己跟帖的關係，通過比較得出排序因子為1. 1的帖子是排序因 子為1的跟帖。同理，比較ASCII編碼值，可以得出排序因子為1.2的帖子也 是排序因子為1的跟帖，但與排序因子1. 1比較，它是第二個跟帖。以此類推， 可以得到順序排列的帖子列表。步驟405，順序掃描帖子列表，將帖子列表中的帖子信息逐個輸出顯示。 顯示效果如圖1所示，但不限於圖1的形式，可以顯示更詳細的信息，如發帖 時間等。在頁面顯示帖子信息時，通常以空格縮進的方式顯示出帖子間的層次 關係，可以採用多種方法控制每個層次需要縮進的空格數，也可以採用本領域 技術人員所熟知的其他方法顯示帖子間的層次關係。優選的，本發明實施例在輸出帖子時，充分利用排序因子的構造方式來顯示帖子間的層次關係，當顯示某個帖子時計算該帖子的sorter欄位包含字符 "."的個數，並相應縮進幾個空格。例如主帖的sorter值為1則不需要縮進， "跟帖一"的sorter值為1. 1則縮進一個空格，"跟帖一的第一個跟帖"的sorter 值為1. 1. 1則縮進兩個空格。通過上述簡單操作，順序遍歷一次數據列表，就可以快速完成樹型結構數 據的顯示功能，提高了系統的處理效率，降低了數據顯示的開發複雜度。而且， 上述方法還適用於樹型結構數據的其他後續處理，如將排序後的數據直接順序 列印、存儲，或者為後續處理提供輸出數據等。上述實施例中，排序因子是由數字與"."字符或其他非數字字符組合而 成的字符串表示，但本發明並不限定排序因子的構造方式。排序因子可以由數 字和非數字字符(如圖示中的"."字符)構成，也可以由字母和非字母字符 構成，或者由數字和字母組合而成，等等，在此不一一列舉。總之，在構造排 序因子時，只需要滿足在字符編碼排序中，用於區分樹型結構層次的字符(如 ".，，字符)所對應的編碼值(46 )，與標識數據在樹型結構中的位置的字符(如 數字)所對應的編碼值(48 - 57 )不在同一個編碼值範圍即可。而且，除上述使用ASCII編碼的字符串來構造排序因子、進行排序因子值 的比較外，使用其他的編碼也是可行的，比如使用GBK (漢字內碼擴展規範) 編碼中的一些字符來分別代替上例中的0-9這些數字，只要注意這些字符排 序的順序和數字0-9的排序順序一致即可。因此在根據排序因子進行數據排 序時，按照相對應的編碼值排序即可，排序原理同上所述。對應上述簡單高效的實現方法，本發明還提供了一種顯示樹型結構數據的 系統實施例，參照圖7所示，所述系統包括排序因子構造單元701、數據獲取 單元702、排序單元703、輸出單元7(M。以下內容也以論壇帖子為例進行說 明。由於在資料庫設計時，在記錄帖子信息的數據表中增加了一個欄位，用於 記錄每條帖子信息與其他帖子間的關聯關係，作為在頁面上顯示帖子的一個排 序因子，因此資料庫中每增加一條新的帖子記錄，就需要通過排序因子構造單 元701來構造每條記錄的排序因子。所述排序因子構造單元701在構造排序因子時，需要滿足在字符編碼排序 中，用於區分樹型結構層次的字符所對應的編碼值，與標識數據在樹型結構中 的位置的字符所對應的編碼值不在同一個編碼值範圍。所述排序因子可以由數 字和非數字字符構成，也可以由字母和非字母字符構成，或者由數字和字母組 合而成，等等。例如，以數字和"."字符構成字符串表示排序因子，每次新增一個主帖 子時把這條數據記錄的排序因子值設置為數字1，新增所述主帖的第一個跟帖 時把相應的排序因子值設置為字符串1.1，如果再新增所述主帖的第二個跟帖 則把相應排序因子值設置為字符串1.2，新增第一個跟帖的跟帖時設置為 1.1.1，以此類推下去，最後保存在資料庫中的記錄如圖3所示。而當一個帖子的跟帖數目較多時可以構造更長的排序因子。例如主帖的 排序因子值為l，"跟帖一"的排序因子值為1.01，"跟帖一的第一個跟帖"的排 序因子值為1.01.01，"跟帖一的第十二個跟帖"的排序因子值為1.01.12，以 此類推。總之，排序因子構造單元701的構造方式靈活多樣。而且優選的，為降低 構造複雜度，節省存儲空間，在構造多個主帖的排序因子時，對每個主帖都設 置相同的排序因子(如數字1)，設置簡單而不影響對每個主帖對應的樹型結 構數據的操作。數據獲取單元702,用於根據用戶發送的點擊請求，從請求中提取帖子ID 等參數，然後讀取資料庫，取出與所述帖子ID對應的帖子數據；再根據所述 帖子數據可以得到主帖ID，該帖子可能是主帖，也可能是跟帖；查詢資料庫， 將該主帖ID下的所有跟帖取出。優選的，數據獲取單元702在讀取資料庫時為直接獲得主帖ID ，可以將 每個帖子所屬的主帖ID包含在請求參數中發送給伺服器，這樣伺服器就可以 直接從請求中提取主帖ID，減少了讀取資料庫的操作次數。當資料庫訪問量 較大時，所述優選方法就能夠顯著提高處理效率。排序單元703，用於根據所述排序因子，對數據獲取單元702取出的數據 記錄進行排序。例如，按照計算機中字符串的默認排序方法，根據排序因子中 每個字符的ASCII編碼值進行排序。這樣，從資料庫取出來的帖子列表就是按照要顯示的帖子順序排列的。
而且，根據排序因子的構造方法不同，排序單元703採用的編碼排序也不 同。除使用ASCII編碼表的排序規則外，還可以使用其他的編碼，比如使用 GBK (漢字內碼擴展規範)編碼中的一些字符來分別代替上例中的0 - 9這些數 字，只要注意這些字符排序的順序和數字0-9的排序順序一致即可。因此在 根據排序因子進行數據排序時，按照相對應的編碼值排序即可，排序原理同上 所述。
輸出單元704,用於順序遍歷經排序的數據列表，將帖子列表中的帖子信 息逐個輸出顯示。在頁面顯示帖子信息時，通常以空格縮進的方式顯示出帖子 間的層次關係，可以採用多種方法控制每個層次需要縮進的空格數，也可以採 用本領域技術人員所熟知的其他方法顯示帖子間的層次關係。
優選的，所述輸出單元704充分利用排序因子的構造方式來顯示帖子間的 層次關係。在以數字和"."字符組合表示的排序因子中，當顯示某個帖子時， 計算該帖子的排序因子包含字符"."的個數，並縮進相應空格。例如主帖的排 序因子值為1則不需要縮進，"跟帖一"的排序因子值為1. 1則縮進一個空格， "跟帖一的第一個跟帖"的排序因子值為1. 1. 1則縮進兩個空格。
本發明實施例提供的顯示樹型結構數據的系統，對從資料庫取出的數據先 進行排序，然後遍歷一次數據列表，即可直接輸出按照樹型結構排列的數據記 錄，提高了系統的處理效率，降低了數據顯示的開發複雜度。而且，上述方法 還適用於樹型結構數據的其他後續處理，如將排序後的數據直接順序列印、存 儲，或者為後續處理提供輸出數據等。
以上對本發明所提供的一種處理樹型結構數據的方法及系統，進行了詳細
施例的說明只是用於幫助理解本發明的方法及其核心思想；同時，對於本領域 的一般技術人員，依據本發明的思想，在具體實施方式
及應用範圍上均會有改 變之處。綜上所述，本說明書內容不應理解為對本發明的限制。
權利要求
1. 一種處理樹型結構數據的方法，其特徵在於，包括在結點數據中記錄用於標識數據層次關聯關係的信息；讀取同一棵樹的所有結點數據；根據所述數據層次關聯關係，對結點數據進行排序後得到數據列表；順序掃描所述列表並輸出。
2、 根據權利要求1所述的方法，其特徵在於所述排序是對標識數據層 次關聯關係的信息所對應的ASCII編碼值，按照ASCII編碼表的排序規則進行 排序。
3、 根據權利要求1所述的方法，其特徵在於所述數據關聯關係以數字/ 字母與非數字/字母字符的組合表示。
4、 根據權利要求3所述的方法，其特徵在於根據非數字/字母字符的個 數，判斷輸出數據時需要縮進的空格數。
5、 根據權利要求3所述的方法，其特徵在於每棵樹的根結點數據設置 相同的數字/字母。
6、 一種處理樹型結構數據的系統，其特徵在於，包括 排序因子構造單元，用於對應每個結點數據，構造標識數據層次關聯關係的排序因子；數據獲取單元，用於讀取同一棵樹的所有結點數據；排序單元，用於根據所述排序因子，對結點數據進行排序後得到數據列表;輸出單元，用於順序掃描所述列表並輸出。
7、 根據權利要求6所述的系統，其特徵在於所述排序單元對排序因子 對應的ASCII編碼值，按照ASCII編碼表的排序規則進行排序。
8、 根據權利要求6所述的系統，其特徵在於所述排序因子以數字/字母 與非數字/字母字符的組合表示。
9、 根據權利要求8所述的系統，其特徵在於所述輸出單元根據非數字/ 字母字符的個數，判斷輸出數據時需要縮進的空格數。
10、 根據權利要求8所述的系統，其特徵在於所述排序因子構造單元對 每棵樹的根結點數據設置相同的數字/字母。
全文摘要
本發明公開了一種處理樹型結構數據的方法及系統，解決採用遞歸遍歷的方法處理顯示樹型結構的數據速度較慢的問題。所述方法包括在結點數據中記錄用於標識數據層次關聯關係的信息；讀取同一棵樹的所有結點數據；根據所述數據層次關聯關係，對結點數據進行排序後得到數據列表；順序掃描所述列表並輸出。其中，所述數據關聯關係以數字/字母與非數字/字母字符的組合表示。本發明通過遍歷一次數據列表，就可以快速顯示樹型結構數據，提高了系統的處理效率，降低了數據顯示的開發複雜度，而且實現起來十分簡單。
文檔編號G06F17/30GK101236550SQ200710007530
公開日2008年8月6日 申請日期2007年2月1日 優先權日2007年2月1日
發明者爭 楊, 毛懷源, 波 陳, 馬雲峰 申請人:阿里巴巴公司