01

—

認識二叉查找樹

二叉樹的結點用對象表示，每個結點有一個key，左孩子和右孩子指針，每個結點不能多于2個孩子，二叉樹的一個重要應用是它們在查找中的應用。二叉查找樹的性質是：對于二叉樹的結點X，它的左子樹的關鍵字小于結點X的關鍵字，右子樹的關鍵字大于等于結點X的關鍵字。下圖是二叉查找樹的經(jīng)典示意圖。

二叉查找樹示意圖

02—

二叉樹的實現(xiàn)

二叉查找樹每一個結點有一個關鍵字key，左孩子和右孩子，因此我們定義一個結構體類型描述二叉查找樹結點。typedef?int?data_type_t;

typedef?struct?binary_tree_node{
????data_type_t?data;
????struct?binary_tree_node?*left;
????struct?binary_tree_node?*right;
}binary_tree_node_t;data是結點關鍵字，left和right分別是左孩子指針和右孩子指針。下面我們聲明二叉查找樹操作函數(shù)。

extern?binary_tree_node_t *new_binary_tree_node(data_type_t?data); //新建一個二叉樹結點
extern?void?free_binary_tree_node(binary_tree_node_t?*node); //釋放二叉樹結點內(nèi)存
extern?void?binary_tree_insert(binary_tree_node_t?**root, data_type_t?data); //二叉查找樹插入一個結點
extern?void?binary_tree_delete(binary_tree_node_t?**root, data_type_t?data); //銷毀二叉查找樹
extern?binary_tree_node_t *binary_tree_find(binary_tree_node_t?*root, data_type_t?data); //在二叉查找樹中查找一個結點
extern?void?binary_tree_destroy(binary_tree_node_t?*root); //銷毀二叉樹
extern?void?binary_tree_print(binary_tree_node_t?*root); //后序遍歷打印
extern?void?preorder_traversal_binary_tree(binary_tree_node_t?*root); //前序遍歷
extern?void?middle_order_traversal_binary_tree(binary_tree_node_t?*root); //中序遍歷
extern?void?postorder_traversal_binary_tree(binary_tree_node_t?*root); //后序遍歷

• 新建結點和釋放結點
  
  

new_binary_tree_node是新建一個二叉查找樹結點，free_binary_tree_node則是釋放二叉查找樹結點內(nèi)存，函數(shù)定義分別如下。
binary_tree_node_t?*new_binary_tree_node(data_type_t?data){
????binary_tree_node_t?*tree_node = (binary_tree_node_t?*)malloc(sizeof(binary_tree_node_t));
????if(!tree_node){
????????return?NULL;
????}
????tree_node->data = data;
????tree_node->left = NULL;
????tree_node->right = NULL;

????return?tree_node;
}

void?free_binary_tree_node(binary_tree_node_t?*node){
????if(node == NULL){
????????return;
????}
????node->right = NULL;
????node->left = NULL;
????free(node);
????node = NULL;
}

在釋放二叉查找樹結點內(nèi)存函數(shù)中我們看到釋放結點前先將左孩子和右孩子指針置為NULL再釋放內(nèi)存。

• 二叉查找樹插入結點

void binary_tree_insert(binary_tree_node_t **root, data_type_t data){
????if(root == NULL){
????????return;
????}
????if(*root == NULL){
????????return;
????}
????binary_tree_node_t *tree_node = new_binary_tree_node(data);
????if(tree_node == NULL){
????????return;
????}
????binary_tree_node_t *tree_root = *root;

????while(tree_root != NULL){
????????if(data < tree_root->data){
????????????if(tree_root->left == NULL){
????????????????break;
????????????}
????????????tree_root = tree_root->left;
????????}else{
????????????if(tree_root->right == NULL){
????????????????break;
????????????}
????????????tree_root = tree_root->right;
????????}
????}
????if(data < tree_root->data){
????????tree_root->left = tree_node;
????}else{
????????tree_root->right = tree_node;
????}
}

這里根據(jù)二叉查找樹的性質，從根結點遍歷二叉樹，小于當前結點關鍵字則往左孩子方向遍歷，若左孩子指針是空指針則左孩子指針指向新結點，大于等于當前結點關鍵字則往右孩子方向遍歷，若右孩子指針是空指針則右孩子指針指向新結點。

• 二叉查找樹查找結點
  

binary_tree_node_t *binary_tree_find(binary_tree_node_t *root, data_type_t data){
????if(root == NULL){
????????return?NULL;
????}

????while(root != NULL){
????????if(root->data == data){
????????????break;
????????}else?if(data < root->data){
????????????root = root->left;
????????}else{
????????????root = root->right;
????????}
????}

????return?root;
}還是按照二叉查找樹的性質，給定關鍵字，從二叉查找樹根結點遍歷整棵樹，關鍵字小于當前結點關鍵字則往左孩子方向遍歷，大于當前結點關鍵字則往右孩子方向遍歷，當前關鍵字與給定關鍵字相等則找到目標結點，最后若找不到給定關鍵字結點則返回空指針。

• 二叉查找樹刪除結點

刪除結點是二叉查找樹比較難理解的一個點，在動手實現(xiàn)代碼之前，我們先來理順刪除結點的邏輯，只要理清了寫代碼就輕松不少，有些人可能還是不太理解，那么我建議你自己用筆和紙畫一下二叉查找樹，看著圖寫代碼。

被刪除的結點分為3類。

1. 被刪除結點是根結點

2. 被刪除結點是葉子結點

3. 被刪除結點非根結點和非葉子結點

??

??被刪除結點非根結點，那么要考慮一種情況

1. 被刪除結點是其父節(jié)點的左孩子，其父節(jié)點的左孩子指針指向新結點即可。

2. 被刪除結點是其父親結點的右孩子，其符父結點的右孩子指針指向新結點即可。

? 除了葉子結點外，我們還要討論一種情況。

1. 目標結點只有左孩子

2. 目標結點只有右孩子

3. 目標結點有左孩子和右孩子

? 每一種情況我們分開討論。

? 1、被刪除結點是根結點且沒有孩子

? 這種情況比較好理解，就是二叉查找樹只有一個結點，只要刪除根結點即可。

??2、被刪除結點是根結點且只有左孩子

? 刪除根節(jié)點，用原根節(jié)點的左孩子成為新的根結點即可。

??3、被刪除結點是根結點且只有右孩子

? 刪除根節(jié)點，用原根結點的右孩子成為新的根節(jié)點即可。

??4、被刪除結點是根結點且有左孩子和右孩子

?隨機選取左孩子或者右孩子成為新根結點，但是有一個地方要注意，就是根節(jié)點? ?的孩子結點也可能有孩子結點，這里我們假設使用根結點的左孩子成為新結點來? ?討論。根結點的左孩子成為了新根結點，由于根結點的右子樹結點所有關鍵字大? ?于或等于根結點左子樹的關鍵字，所以需要保存原根結點的左孩子的右子樹根結點，將新根結點的右孩子結點指針指向原根結點的右子樹，最后遍歷新根結點的右子樹的直到最左葉子結點，將最左葉子結點的左結點指針指向保存的原根結點的左孩子?的右子樹根結點。若要取右孩子成為新根結點，按照這個思路分析即可。

??5、被刪除結點是葉子結點

? 葉子結點沒有孩子，所以只要刪除即可，其父結點更新孩子結點指針即可。

??6、被刪除結點非根結點且非葉子結點，只有左孩子

? 使左子樹的根結點代替被刪除結點的位置，跟新被刪除結點的父節(jié)點孩子指針即? ? 可。

??7、被刪除結點是非根結點且非葉子結點，只有右孩子

? 使右子樹的根結點代替被刪除結點的位置，更新被刪除結點的父結點的孩子指針? ? 即可。

? 8、被刪除結點是非根結點且非葉子結點，有左孩子和右孩子

??為了保持盡可能的公平，不至于讓二叉查找樹像一個鏈表，我們每次刪除結點時? ? 隨機采用左孩子結點或者右孩子結點代替被刪除結點的位置。其實這里和刪除根? ??結點且根結點有左孩子和右孩子很相似，區(qū)別就是根結點沒有父結點。在講解刪? ? 除根結點時我們講解了用左孩子結點代替被刪除結點的位置，這次我們講解右? ? ? ? 孩子結點替換被刪除結點的情況。

??被刪除結點的右孩子代替被刪除結點的位置，根據(jù)二叉查找樹的性質，這個時候? ? 需要保存被刪除結點的右孩子的左子樹根結點，同時將右孩子的左孩子結點指向? ? 被刪除結點的左子樹根結點。最后從被刪除結點的左子樹根結點遍歷直到到達最? ? 右結點，將最右結點的右孩子結點指針指向被刪除結點的右孩子的左子樹根結? ? ? ? 點。在用被刪除結點的左子樹根結點或右子樹根結點代替被刪除結點時，分別需要調(diào)整被刪除結點的孩子結點和父結點指針，因此我們定義兩個函數(shù)用于調(diào)整二叉查找樹的結點。//向左旋轉
static?void left_rotate(binary_tree_node_t **node, binary_tree_node_t *tree_root){
????if(node == NULL?|| tree_root == NULL){
????????return;
????}
????if(*node == NULL){
????????return;
????}
????binary_tree_node_t *temp_node = NULL;
????binary_tree_node_t *left = NULL;

????*node = tree_root->right; //目標結點的右子結點代替目標結點
????temp_node = tree_root->left; //保存目標右子結點的左子結點
????left = tree_root->right->left;
????//遍歷目標結點的左子結點的最右結點
????while(left != NULL?