手把手教你写二叉查找树

01

—

认识二叉查找树

二叉树的结点用对象表示，每个结点有一个key，左孩子和右孩子指针，每个结点不能多于2个孩子，二叉树的一个重要应用是它们在查找中的应用。二叉查找树的性质是：对于二叉树的结点X，它的左子树的关键字小于结点X的关键字，右子树的关键字大于等于结点X的关键字。下图是二叉查找树的经典示意图。

二叉查找树示意图

02—

二叉树的实现

二叉查找树每一个结点有一个关键字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分别是左孩子指针和右孩子指针。下面我们声明二叉查找树操作函数。

extern binary_tree_node_t *new_binary_tree_node(data_type_t data); //新建一个二叉树结点
extern void free_binary_tree_node(binary_tree_node_t *node); //释放二叉树结点内存
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则是释放二叉查找树结点内存，函数定义分别如下。
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;
}

在释放二叉查找树结点内存函数中我们看到释放结点前先将左孩子和右孩子指针置为NULL再释放内存。

• 二叉查找树插入结点

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;
    }
}

这里根据二叉查找树的性质，从根结点遍历二叉树，小于当前结点关键字则往左孩子方向遍历，若左孩子指针是空指针则左孩子指针指向新结点，大于等于当前结点关键字则往右孩子方向遍历，若右孩子指针是空指针则右孩子指针指向新结点。

• 二叉查找树查找结点
  

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;
}还是按照二叉查找树的性质，给定关键字，从二叉查找树根结点遍历整棵树，关键字小于当前结点关键字则往左孩子方向遍历，大于当前结点关键字则往右孩子方向遍历，当前关键字与给定关键字相等则找到目标结点，最后若找不到给定关键字结点则返回空指针。

• 二叉查找树删除结点

删除结点是二叉查找树比较难理解的一个点，在动手实现代码之前，我们先来理顺删除结点的逻辑，只要理清了写代码就轻松不少，有些人可能还是不太理解，那么我建议你自己用笔和纸画一下二叉查找树，看着图写代码。

被删除的结点分为3类。

1. 被删除结点是根结点

2. 被删除结点是叶子结点

3. 被删除结点非根结点和非叶子结点

  

  被删除结点非根结点，那么要考虑一种情况

1. 被删除结点是其父节点的左孩子，其父节点的左孩子指针指向新结点即可。

2. 被删除结点是其父亲结点的右孩子，其符父结点的右孩子指针指向新结点即可。

  除了叶子结点外，我们还要讨论一种情况。

1. 目标结点只有左孩子

2. 目标结点只有右孩子

3. 目标结点有左孩子和右孩子

  每一种情况我们分开讨论。

  1、被删除结点是根结点且没有孩子

  这种情况比较好理解，就是二叉查找树只有一个结点，只要删除根结点即可。

  2、被删除结点是根结点且只有左孩子

  删除根节点，用原根节点的左孩子成为新的根结点即可。

  3、被删除结点是根结点且只有右孩子

  删除根节点，用原根结点的右孩子成为新的根节点即可。

  4、被删除结点是根结点且有左孩子和右孩子

 随机选取左孩子或者右孩子成为新根结点，但是有一个地方要注意，就是根节点   的孩子结点也可能有孩子结点，这里我们假设使用根结点的左孩子成为新结点来   讨论。根结点的左孩子成为了新根结点，由于根结点的右子树结点所有关键字大   于或等于根结点左子树的关键字，所以需要保存原根结点的左孩子的右子树根结点，将新根结点的右孩子结点指针指向原根结点的右子树，最后遍历新根结点的右子树的直到最左叶子结点，将最左叶子结点的左结点指针指向保存的原根结点的左孩子 的右子树根结点。若要取右孩子成为新根结点，按照这个思路分析即可。

  5、被删除结点是叶子结点

  叶子结点没有孩子，所以只要删除即可，其父结点更新孩子结点指针即可。

  6、被删除结点非根结点且非叶子结点，只有左孩子

  使左子树的根结点代替被删除结点的位置，跟新被删除结点的父节点孩子指针即    可。

  7、被删除结点是非根结点且非叶子结点，只有右孩子

  使右子树的根结点代替被删除结点的位置，更新被删除结点的父结点的孩子指针    即可。

  8、被删除结点是非根结点且非叶子结点，有左孩子和右孩子

  为了保持尽可能的公平，不至于让二叉查找树像一个链表，我们每次删除结点时    随机采用左孩子结点或者右孩子结点代替被删除结点的位置。其实这里和删除根    结点且根结点有左孩子和右孩子很相似，区别就是根结点没有父结点。在讲解删    除根结点时我们讲解了用左孩子结点代替被删除结点的位置，这次我们讲解右        孩子结点替换被删除结点的情况。

  被删除结点的右孩子代替被删除结点的位置，根据二叉查找树的性质，这个时候    需要保存被删除结点的右孩子的左子树根结点，同时将右孩子的左孩子结点指向    被删除结点的左子树根结点。最后从被删除结点的左子树根结点遍历直到到达最    右结点，将最右结点的右孩子结点指针指向被删除结点的右孩子的左子树根结        点。在用被删除结点的左子树根结点或右子树根结点代替被删除结点时，分别需要调整被删除结点的孩子结点和父结点指针，因此我们定义两个函数用于调整二叉查找树的结点。//向左旋转
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