用過(guò)平衡二叉樹(shù)的朋友都清楚，平衡二叉樹(shù)的最大優(yōu)點(diǎn)就是排序。不管是在數(shù)據(jù)插入的時(shí)候還是在數(shù)據(jù)刪除的時(shí)候，我們都要考慮到數(shù)據(jù)的排序情況。但是和數(shù)據(jù)的添加、刪除一樣重要的，還有數(shù)據(jù)的查詢(xún)。很不幸，平衡二叉樹(shù)經(jīng)常由于節(jié)點(diǎn)的添加和刪除，數(shù)據(jù)的查詢(xún)效率會(huì)變得非常低下。朋友們可以看看下面這樣的一個(gè)極端場(chǎng)景，所有分支節(jié)點(diǎn)都只有一邊存在數(shù)據(jù)：

/* 
*         7        3 
*        /           \ 
*       6             4 
*      /                \ 
*     5                  7 
*    /                    \ 
*   2                     12 
*  /                        \ 
* 1                         20 
*/  

上面的這幅圖很能說(shuō)明問(wèn)題，雖然查詢(xún)7、6很方便，但是查詢(xún)5、2、1的時(shí)候效率就非常低了，右邊的二叉樹(shù)也是這種情況。那么有沒(méi)有辦法使得數(shù)據(jù)之間的查找效率不至于相差太大呢？截止目前為止，主要有下面三種方法：

（1）哈希二叉樹(shù)

（2）avl樹(shù)

（3）紅黑樹(shù)

今天我們主要講解的內(nèi)容就是哈希樹(shù)。其他兩個(gè)內(nèi)容會(huì)在后面的博客里面介紹。

那么什么是哈希樹(shù)呢？其實(shí)也非常簡(jiǎn)單，就是我們?cè)诙鏄?shù)節(jié)點(diǎn)中添加一個(gè)next指針，同時(shí)建立一個(gè)hash表，這樣我們?cè)诓樵?xún)數(shù)據(jù)的時(shí)候就可以直接利用hash查詢(xún)代替平衡二叉樹(shù)的查詢(xún)了。一般來(lái)說(shuō)，哈希樹(shù)的節(jié)點(diǎn)應(yīng)該是這樣定義的：

typedef struct _HASH_TREE  
{  
    int data;  
    struct _HASH_TREE* next;  
    struct _HASH_TREE* left;  
    struct _HASH_TREE* right;  
}HASH_TREE;  
``

其實(shí)，相比較普通的平衡二叉樹(shù)而言，也就是多了一個(gè)next指針而已，那么這個(gè)next指針什么時(shí)候需要處理呢？主要就是在添加節(jié)點(diǎn)和刪除節(jié)點(diǎn)的時(shí)候處理。

STATUS add_node_into_tree(HASH_TREE** ppHash, int data)
{

/* add hash node into tree */  

/* add hash node into hash table */  

return TRUE;  

}

添加的代碼如此，刪除工作也比較類(lèi)似。

STATUS delete_node_from_tree(HASH_TREE* ppHash, int data)
{
HASH_TREE pNode;
/ delete hash node from tree, but not free space/

/* delete hash node from hash table */  

free(pNode);  
return TRUE;  

}

說(shuō)明：

（1）哈希二叉樹(shù)的思想比較重要，同學(xué)們最好弄清楚為什么要建立hash二叉樹(shù)？

（2）上面的代碼不是很完整，對(duì)hash表不熟悉的朋友可以參考我寫(xiě)的這一篇博客（hash表），二叉樹(shù)添加刪除不熟悉的朋友同樣可以參考我寫(xiě)的另外一篇博客（添加，刪除1，刪除2，刪除3），把兩部分代碼按照上面給出的結(jié)構(gòu)合起來(lái)基本上就可以實(shí)現(xiàn)哈希二叉樹(shù)了。