C++ 簡單二叉樹類實現與使用指南

簡介

本文介紹一個基於數組實現的簡單二叉查找樹類 CSimpleBinaryTree，適用於數據較少變動、頻繁查找的場景。原文出自 CodeGuru，由 DigitalConvict 供稿。

核心特性

• 基於數組的緊湊存儲，支持動態擴縮容
• 提供線性查找（小數據量）與二分查找（大數據量）自動切換
• 支持重複鍵值配置（m_bAllowDuplicates）
• 內建自動擴縮容機制（觸發閾值 + 比例增減）
• 提供標準容器風格接口：增、刪、查、遍歷

主要接口詳解

初始化

// 基礎初始化
btree.Initialise(MAXELEMS, sizeof(CSomeObject));

// 指定比較函數
btree.Initialise(MAXELEMS, sizeof(CSomeObject), someCompareFunction);

// 完整參數：含自動擴縮容閾值
btree.Initialise(MAXELEMS, sizeof(CSomeObject), someCompareFunction,
                 nGrowTrigger, nGrowByValue, nShrinkTrigger, nShrinkByValue);

比較函數簽名：int (*)(const void*, const void*)，返回負/零/正表示小於/等於/大於。

添加元素

CSomeObject obj;
int nResult = btree.AddItem(&obj);           // 返回索引或錯誤碼
int nResult = btree.AddItem(&obj, pNewObj);  // 可選輸出新建對象指針

返回值：成功返回索引（≥0），失敗返回 DUPLICATE_FOUND、OUT_OF_MEMORY、TREE_IS_FULL。

刪除元素

BOOL bResult = btree.RemoveItem(nIndex);  // 成功返回 TRUE

刪除後，後續元素前移，樹大小遞減。注意：刪除操作可能觸發整樹遍歷，效率較低。

查找元素

int nIndex = btree.FindItem(pObj);           // 僅返回索引
int nIndex = btree.FindItem(pObj, pFoundObj); // 同時返回找到的對象指針

查找策略：元素數 < 閾值（默認 10）用線性查找，否則用二分查找。允許重複時，樹僅在查找時按需排序（延遲平衡），提升插入性能。

動態擴縮容

// 手動調整容量
btree.ReSize(300);

// 自動擴縮容（默認開啟 m_bAutoResize = TRUE）
// 參數以「當前元素數百分比」表示
// 例：擴容觸發 90%，擴容幅度 50% → 90%滿時容量增至 1.5 倍

其他常用方法

使用建議

• 數據量大且頻繁增刪時，考慮使用標準庫 std::map/std::set 或平衡樹（AVL、紅黑樹）
• 僅作靜態查找的有序數據，本類結構緊湊、查找快，是輕量級選擇
• 自動擴縮容參數需根據業務訪問模式調整，避免頻繁 ReSize 影響性能

源碼獲取

文末提供完整源碼下載，可直接集成到 VC6 及以上項目中。