【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
用過平衡二叉樹的朋友都清楚，平衡二叉樹的最大優點就是排序。不管是在數據插入的時候還是在數據刪除的時候，我們都要考慮到數據的排序情況。但是和數據的添加、刪除一樣重要的，還有數據的查詢。很不幸，平衡二叉樹經常由於節點的添加和刪除，數據的查詢效率會變得非常低下。朋友們可以看看下面這樣的一個極端場景，所有分支節點都只有一邊存在數據：
/*
* 7 3
* / \
* 6 4
* / \
* 5 7
* / \
* 2 12
* / \
* 1 20
*/
/*
* 7 3
* / \
* 6 4
* / \
* 5 7
* / \
* 2 12
* / \
* 1 20
*/
上面的這幅圖很能說明問題，雖然查詢7、6很方便，但是查詢5、2、1的時候效率就非常低了，右邊的二叉樹也是這種情況。那麼有沒有辦法使得數據之間的查找效率不至於相差太大呢？截止目前為止，主要有下面三種方法：
（1）哈希二叉樹
（2）avl樹
（3）紅黑樹
今天我們主要講解的內容就是哈希樹。其他兩個內容會在後面的博客裡面介紹。
那麼什麼是哈希樹呢？其實也非常簡單，就是我們在二叉樹節點中添加一個next指針，同時建立一個hash表，這樣我們在查詢數據的時候就可以直接利用hash查詢代替平衡二叉樹的查詢了。一般來說，哈希樹的節點應該是這樣定義的：
typedef struct _HASH_TREE
{
int data;
struct _HASH_TREE* next;
struct _HASH_TREE* left;
struct _HASH_TREE* right;
}HASH_TREE;
typedef struct _HASH_TREE
{
int data;
struct _HASH_TREE* next;
struct _HASH_TREE* left;
struct _HASH_TREE* right;
}HASH_TREE; 其實，相比較普通的平衡二叉樹而言，也就是多了一個next指針而已，那麼這個next指針什麼時候需要處理呢？主要就是在添加節點和刪除節點的時候處理。
STATUS add_node_into_tree(HASH_TREE** ppHash, int data)
{
/* add hash node into tree */
/* add hash node into hash table */
return TRUE;
}
STATUS add_node_into_tree(HASH_TREE** ppHash, int data)
{
/* add hash node into tree */
/* add hash node into hash table */
return TRUE;
} 添加的代碼如此，刪除工作也比較類似。
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;
}
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;
}
