[發明專利]一種基于分類特性和平衡二叉樹的數據存儲、查詢方法

有效

• 申請號: 201110403732.1
• 申請日: 2011-12-07
• 公開（公告）號: CN102521334A
• 公開（公告）日: 2012-06-27
• 發明（設計）人: 韓一石;孫運龍;王建華;黃明政
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

1.一種基于分類特性和平衡二叉樹的數據存儲、查詢方法，其特征在于，包括以下步驟：

1.1構建平衡二叉樹，創建結點；

1.2按照遍歷的規則，動態地將數據信息存儲到相應結點；

1.3輸入需要查詢的信息，動態遍歷平衡二叉樹，直到找到所需的數據信息或遍歷完平衡二叉樹返回查找失敗。

2.根據權利要求1所述的基于分類特性和平衡二叉樹的數據存儲、查詢方法，其特征在于，所述平衡二叉樹為有序的，可以按照中序、前序或后序的遍歷規則，動態地將數據信息存儲到相應結點。

3.根據權利要求1所述的基于分類特性和平衡二叉樹的數據存儲、查詢方法，其特征在于，所述步驟1.1，按如下方法實現：首先按照平衡二叉樹的建樹規則構建一個節點數為n，樹高為log₂n的平衡二叉樹，然后增加結點，每一個結點代表一個特征類C₁、C₂、C₃、C₄……C_N，每個結點包含一類細化的信息。

4.根據權利要求1所述的基于分類特性和平衡二叉樹的數據存儲、查詢方法，其特征在于，結點數據以C語言或C++語言的形式存儲。

5.根據權利要求1所述的基于分類特性和平衡二叉樹的數據存儲、查詢方法，其特征在于，所述步驟1.2，對數據信息的插入，可以按照中序、前序或后序的遍歷規則對結點進行數據信息的插入，同時調整平衡二叉樹的樹形結構，可分為利用C++語言形式實現和利用C語言形式實現：

①?C++語言形式實現：采用C++語言中VECTOR類作為結點中數據存儲結構，當有數據信息需要存儲時，首先判斷平衡二叉樹是否為空；若是，則新建一個根結點并將數據信息保存到根結點同時返回保存成功；若否，則遍歷平衡二叉樹，判斷其是否屬于已存儲結點；若是，則按照存儲信息的規則，將需要保存的信息保存到相應結點，并返回保存成功；若否，則執行步驟1.1，再將所需保存的數據信息保存到新建結點中，最后由返回函數將保存結果返回供上層調用；

②?C語言實現：利用結構體變量構建一個結構體struct，所有結點采用雙向鏈表的存儲結構，將對結點的所有操作定義為結構體的成員變量，當有數據信息需要保存時，首先判斷平衡二叉樹是否為空；若是，則新建一個根結點并將數據信息保存到根結點同時返回保存成功；若否，則遍歷平衡二叉樹，判斷是否為已存儲結點類；若是，則調用結構體的保存成員對象執行相應的保存操作并返回保存成功；若否，則執行步驟1.1，再將所需保存的數據信息保存到新建結點類中，最后由返回函數將保存結果返回供上層調用。

6.根據權利要求1至5中任何一項所述的基于分類特性和平衡二叉樹的數據存儲、查詢方法，其特征在于，所述步驟1.3中結點數據信息的查詢，通過將結點中的數據信息讀取到緩沖區中，利用二分法查找，可分為利用C++語言形式實現和利用C語言形式實現：

①?C++語言實現：當輸入查詢信息時，首先判斷平衡二叉樹是否為空；若是，則直接返回樹為空；若否，則遍歷平衡二叉樹，判斷是否為已存儲結點；若是，則繼續訪問結點信息，并將結點信息加載到緩存.區，利用二分法進行查找，并將查詢結果給返回函數供上層調用；若否，則返回無結點類給返回函數；

②?C語言實現：利用結構體變量去構建一個結構體struct，所有結點采用雙向鏈表的存儲結構，將對結點的所有操作定義為結構體的成員對象；當需要查詢數據信息時，首先判斷平衡二叉樹是否為空；若是，則直接返回樹為空；若否，則遍歷平衡二叉樹，判斷是否為已存儲結點；若是，則調用結構體的查詢操作成員對象執行相應的查詢操作，繼續訪問結點類中的細化信息，直到查詢到所需結果或查詢完所有記錄信息，并將查詢結果賦給返回函數供上層調用；若否，則返回無結點類給返回函數供上層調用。