01

—

認(rèn)識(shí)二叉查找樹

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

二叉查找樹示意圖

02—

二叉樹的實(shí)現(xiàn)

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

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

new_binary_tree_node是新建一個(gè)二叉查找樹結(jié)點(diǎn)，free_binary_tree_node則是釋放二叉查找樹結(jié)點(diǎn)內(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é)點(diǎn)內(nèi)存函數(shù)中我們看到釋放結(jié)點(diǎn)前先將左孩子和右孩子指針置為NULL再釋放內(nèi)存。

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

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é)點(diǎn)遍歷二叉樹，小于當(dāng)前結(jié)點(diǎn)關(guān)鍵字則往左孩子方向遍歷，若左孩子指針是空指針則左孩子指針指向新結(jié)點(diǎn)，大于等于當(dāng)前結(jié)點(diǎn)關(guān)鍵字則往右孩子方向遍歷，若右孩子指針是空指針則右孩子指針指向新結(jié)點(diǎn)。

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

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é)點(diǎn)遍歷整棵樹，關(guān)鍵字小于當(dāng)前結(jié)點(diǎn)關(guān)鍵字則往左孩子方向遍歷，大于當(dāng)前結(jié)點(diǎn)關(guān)鍵字則往右孩子方向遍歷，當(dāng)前關(guān)鍵字與給定關(guān)鍵字相等則找到目標(biāo)結(jié)點(diǎn)，最后若找不到給定關(guān)鍵字結(jié)點(diǎn)則返回空指針。

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

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

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

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

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

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

??

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

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

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

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

1. 目標(biāo)結(jié)點(diǎn)只有左孩子

2. 目標(biāo)結(jié)點(diǎn)只有右孩子

3. 目標(biāo)結(jié)點(diǎn)有左孩子和右孩子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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