01

—

認識二叉查找樹

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

二叉查找樹示意圖

02—

二叉樹的實現(xiàn)

二叉查找樹每一個結(jié)點有一個關(guān)鍵字key，左孩子和右孩子，因此我們定義一個結(jié)構(gòu)體類型描述二叉查找樹結(jié)點。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是結(jié)點關(guān)鍵字，left和right分別是左孩子指針和右孩子指針。下面我們聲明二叉查找樹操作函數(shù)。

extern?binary_tree_node_t *new_binary_tree_node(data_type_t?data); //新建一個二叉樹結(jié)點
extern?void?free_binary_tree_node(binary_tree_node_t?*node); //釋放二叉樹結(jié)點內(nèi)存
extern?void?binary_tree_insert(binary_tree_node_t?**root, data_type_t?data); //二叉查找樹插入一個結(jié)點
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); //在二叉查找樹中查找一個結(jié)點
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); //后序遍歷

• 新建結(jié)點和釋放結(jié)點
  
  

new_binary_tree_node是新建一個二叉查找樹結(jié)點，free_binary_tree_node則是釋放二叉查找樹結(jié)點內(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;
}

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

• 二叉查找樹插入結(jié)點

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ù)二叉查找樹的性質(zhì)，從根結(jié)點遍歷二叉樹，小于當前結(jié)點關(guān)鍵字則往左孩子方向遍歷，若左孩子指針是空指針則左孩子指針指向新結(jié)點，大于等于當前結(jié)點關(guān)鍵字則往右孩子方向遍歷，若右孩子指針是空指針則右孩子指針指向新結(jié)點。

• 二叉查找樹查找結(jié)點
  

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;
}還是按照二叉查找樹的性質(zhì)，給定關(guān)鍵字，從二叉查找樹根結(jié)點遍歷整棵樹，關(guān)鍵字小于當前結(jié)點關(guān)鍵字則往左孩子方向遍歷，大于當前結(jié)點關(guān)鍵字則往右孩子方向遍歷，當前關(guān)鍵字與給定關(guān)鍵字相等則找到目標結(jié)點，最后若找不到給定關(guān)鍵字結(jié)點則返回空指針。

• 二叉查找樹刪除結(jié)點

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

被刪除的結(jié)點分為3類。

1. 被刪除結(jié)點是根結(jié)點

2. 被刪除結(jié)點是葉子結(jié)點

3. 被刪除結(jié)點非根結(jié)點和非葉子結(jié)點

??

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

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

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

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

1. 目標結(jié)點只有左孩子

2. 目標結(jié)點只有右孩子

3. 目標結(jié)點有左孩子和右孩子

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

? 1、被刪除結(jié)點是根結(jié)點且沒有孩子

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

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

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

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

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

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

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

??5、被刪除結(jié)點是葉子結(jié)點

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

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

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

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

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

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

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

??被刪除結(jié)點的右孩子代替被刪除結(jié)點的位置，根據(jù)二叉查找樹的性質(zhì)，這個時候? ? 需要保存被刪除結(jié)點的右孩子的左子樹根結(jié)點，同時將右孩子的左孩子結(jié)點指向? ? 被刪除結(jié)點的左子樹根結(jié)點。最后從被刪除結(jié)點的左子樹根結(jié)點遍歷直到到達最? ? 右結(jié)點，將最右結(jié)點的右孩子結(jié)點指針指向被刪除結(jié)點的右孩子的左子樹根結(jié)? ? ? ? 點。在用被刪除結(jié)點的左子樹根結(jié)點或右子樹根結(jié)點代替被刪除結(jié)點時，分別需要調(diào)整被刪除結(jié)點的孩子結(jié)點和父結(jié)點指針，因此我們定義兩個函數(shù)用于調(diào)整二叉查找樹的結(jié)點。//向左旋轉(zhuǎn)
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; //目標結(jié)點的右子結(jié)點代替目標結(jié)點
????temp_node = tree_root->left; //保存目標右子結(jié)點的左子結(jié)點
????left = tree_root->right->left;
????//遍歷目標結(jié)點的左子結(jié)點的最右結(jié)點
????while(left != NULL?