什么是二叉查找树？

小咪咪 2022-02-23 15:05 266阅读 0赞

## 树简介 ##

对于树的基本认识，我们很容易通过我们平常所见到的树来理解：一棵树，有一个根，根往上又会分叉出大树枝，大树枝又会分叉出小树枝，以此往复，直到最后是叶子。而作为数据结构的树也是类似的，只不过我们通常将它倒着画。树的应用也相当广泛，例如在文件系统，数据库索引中的应用等。本文会对树的基本概念做介绍，但重点介绍二叉查找树。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 现实中的树

## 树的定义 ##

树是**一种无向图，其中任意两个节点间存在唯一一条路径**。树常常用一种递归的方式来定义，它是一种数据结构，要么为空，要么具有一个值并且有零个或多个孩子，而每个孩子又是树。

例如下图一棵树，任意两个节点间只有一条路径可到达：

![640?wx\_fmt=png][640_wx_fmt_png] 树  
图一：树

但下图并非树：

![640?wx\_fmt=png][640_wx_fmt_png 1] 非树  
图二：非树

因为从节点root到节点b并非只有一条路径。

## 树的种类 ##

我们可能已经听过很多树的名词，例如，红黑树，霍夫曼树，B树，B+树，平衡二叉树等等，而本文将要介绍二叉查找树，很多其他树都是它的变种，不像链表的线性访问，**二叉查找树的大部分操作时间复杂度都为O(logN)。**

## 常见名词解释 ##

在学习二叉查找树之前，必须要先了解一些名词，我们借助下面的图来了解，如果已经清楚了可以跳过此节。

介绍树的基本名词：

*  根节点：root节点没有父节点，我们把它称为**根节点**
 *  父节点：如b节点的父节点为root节点
 *  子节点：在图三中，root有三个孩子，分别是b，c，d，它们都是root的子节点
 *  兄弟节点：b有两个兄弟节点，c，d，**因为它们有相同的父节点root**
 *  叶子节点:e f等节点，**它们没有子节点**，因此是叶子节点。
 *  树的深度:树的深度等于它的最深的树叶的深度，而树叶的深度为从根到本叶子节点的路径长（边数）。根节点的深度为0，例如，图三树的深度root->b->e（也可选其他树叶的深度）为2。
 *  树的层：树的深度+1，根节点的层为1。
 *  二叉树：如图四，**每个节点最多两个子节点**，

![640?wx\_fmt=png][640_wx_fmt_png] 树  
图三：树

![640?wx\_fmt=png][640_wx_fmt_png 2] 二叉树  
图四：二叉树

## 二叉查找树 ##

二叉树是一种树的特殊形式，它的每个节点最多两个孩子节点，分别为左孩子和右孩子。而二叉查找树在此基础上，还有一个特点，就是**每个节点比它左子树的节点值都要大，而比右子树的节点值都要小**。

## 二叉查找树操作 ##

二叉查找树常见操作有插入，查找，删除以及遍历。而实际上二叉查找树既可以使用数组来实现，也可以使用链表，本文采用链表来实现。另外本文也排除了两个节点存在相同值的情况。

#### 节点定义 ####

我们使用一个结构体来定义它：

typedef struct Tree_Node
    {
         
        ElementType value;   //节点值
        struct Tree_Node *left; //左节点
        struct Tree_Node *right; //右节点
    }TreeNode;

#### 二叉查找树的插入 ####

我们以数据 10,5,19，4,8，13,24为例，来看看二叉查找树的插入流程是怎样的。

*  插入节点值10，由于原先无节点，因此10作为根节点
 *  插入节点值5，与根节点比较，比根节点小，因此将插入到左子树，而19比根节点大，将插入右子树。  
    
    
    ![640?wx\_fmt=png][640_wx_fmt_png 3] 二叉查找树插入
    
      
    
    
    图五：二叉查找树插入1
    
      
    
 *  节点值4，与根节点10比较，比根节点小，因此将插入到左子树，继续与5比较，比5小，将插入左子树；节点8，与根节点10比较，比根节点小，因此插入到左子树，与5比较，比5大，因此插入到右子树。  
    
    
    ![640?wx\_fmt=png][640_wx_fmt_png 4] 二叉查找树插入
    
      
    
    
    图六：二叉查找树插入2
    
      
    
 *  节点值13，与根节点比较，比根节点大，因此将插入到右子树，继续与19比较，比19小，因此插入到左子树；节点值24，与根节点比较，比根节点大，因此将插入到右子树，与19比较，比19大，因此插入到右子树。
    
    ![640?wx\_fmt=png][640_wx_fmt_png 5]
    
    二叉查找树插入
    
      
    
    
    图七：二叉查找树插入3

最终完成了所有元素的插入。而观察插入后的二叉树可以发现，每个节点都要比左子树的值大，而比右子树的值小。另外，我们在插入的时候不断地与节点值比较，比它大，则将插入右子树，而比它小，则将插入左子树，因此这个过程非常容易用递归来实现。

/*将value插入到树中*/
    TreeNode *insertTree(ElementType value,TreeNode *tree)
    {
        
        if(NULL == tree)
        {
        
            /*创建一个节点*/
            tree = malloc(sizeof(TreeNode));
            if(NULL == tree)
            {
        
                printf("malloc failed\n"); 
                return NULL;
            }
            else
            {
        
                /*将节点信息存储在此叶子节点中*/
                printf("insert %d to tree\n",value);
                tree->value = value;
                tree->left = NULL;
                tree->right = NULL;
    
            }
        }
        /*比当前节点小，则插入到左子树*/
        else if(value < tree->value)
        {
        
            tree->left = insertTree(value,tree->left);
        }
        /*比当前节点大，则插入到右子树*/
        else if(value > tree->value)
        {   
            tree->right = insertTree(value,tree->right);
        }
        return tree;
    }

#### 二叉查找树的查找 ####

实际上，我们在做插入操作的时候，已经在做查找动作了，因为为了将一个元素插入到正确的位置，我们需要从根节点开始，不断比较其值和要插入（查找）的值的大小，如果比该节点值小，则说明该值需要插入到左子树，否则插入到右子树，并且递归调用，最终找到插入的位置。

查找的思路有点像二分查找，我们知道根节点左子树的值都比根节点值小，而右子树的值都比根节点的值要大，以此递归调用，可以很容易找到：

/*查找值为value的节点*/
    TreeNode *findTree(ElementType value,TreeNode *tree)
    {
        
        if(NULL == tree)
        {
        
            /*最后一层还没有找到*/
            return NULL;
        }
        /*从左子树查找*/
        if(value < tree->value)
        {
        
            return findTree(value,tree->left);
        }
        /*从右边子树查找*/
        else if(value > tree->value)
        {
        
            return findTree(value,tree->right);
        }
            /*找到*/
        else
            return tree;
    
    }

#### 二叉查找树的删除 ####

相对来说，删除要比插入和查找复杂很多。因为它需要考虑很多情况：

*  删除的节点为叶子节点，直接删除
 *  删除的节点有一个子节点，可以将该子节点作为其父节点的子节点
 *  删除的节点有两个子节点，我们可以采取这样的策略：用右子树最小值代替该节点，并递归删除那个节点值。需要递归删除是因为这个最小值的节点可能还有右子树，因此需要做同样的删除操作（它不会有左子树，因为它自己的值最小）。

第一种情况很容易理解，我们来看第二种和第三种情况。

先看第三种情况，假如我们要从前面的二叉树中删除节点值为10的节点。首先我们可以找到节点值为10的节点的右子树的最小值，为13，因此，将13代替节点值为10的节点值，而幸运的是，节点值为13的节点没有右子树，因此释放根节点的内存，完成删除操作。删除前后如图所示：

![640?wx\_fmt=png][640_wx_fmt_png 6] 二叉查找树删除

图八：二叉查找树删除1

再看第二种情况，假如此时要删除值为19的节点，从图中可知，它有一个右儿子，因此删除该节点后，需要将其父节点指向它的右儿子，删除后如下图：

![640?wx\_fmt=png][640_wx_fmt_png 7]

二叉查找树删除2

图九：二叉查找树删除2

总体来说，删除操作并不是一次简单的查找就可以完成，甚至删除会使得整个二叉树变得非常不平衡，所以如果删除次数不多，完全可以采用懒惰删除，即当节点被删除时，仅做一个标记，表明它被删除了，而不是真的从树中移除，这样虽然表面上浪费了一点空间，但是如果后面又要插入该元素值，则为新元素分配内存的开销就免了。

根据上面的分析，代码如下：

TreeNode *deleteTree(ElementType value,TreeNode *tree)
    {
        
        TreeNode *tempNode = NULL;;
        if(NULL == tree)
        {
        
            printf("not fount \n");
            return NULL;
        }
        /*比当前节点值小，从左子树查找并删除*/
        else if(value < tree->value)
        {
        
            tree->left = deleteTree(value,tree->left);
        }
        /*比当前节点值大，从右子树查找并删除*/
        else if(value > tree->value)
        {
        
            tree->right = deleteTree(value,tree->right);
        }
        /*等于当前节点值，并且当前节点有左右子树*/
        else if(NULL != tree->left  && NULL != tree->right)
        {
        
            /*用右子树的最小值代替该节点，并且递归删除该最小值节点*/
            tempNode = findMin(tree->right);
            tree->value = tempNode->value;
            tree->right = deleteTree(tree->value,tree->right);
        }
        /*要删除的节点只有一个子节点或没有子节点*/
        else
        {
        
            tempNode = tree; 
            /*要删除节点有右孩子*/
            if(NULL == tree->left)
                tree=tree->right;
            /*要删除节点有左孩子*/
            else if(NULL == tree->right)
                tree = tree->left;
            free(tempNode);
            tempNode = NULL;
        }
        return tree;
    }

## 完整代码及运行结果 ##

完整代码可阅读原文或访问  
https://www.yanbinghu.com/2019/04/07/55964.html查看  
编译运行结果：

$ gcc -o binarySearchTree binarySearchTree.c
    $ ./binarySearchTree
    insert 10 to tree
    insert 5 to tree
    insert 19 to tree
    insert 4 to tree
    insert 8 to tree
    insert 13 to tree
    insert 24 to tree
    find 13

## 总结 ##

本文简单介绍了二叉查找树的插入，查找，删除操作，其中删除操作较为复杂，需要特别注意。

## 思考 ##

如果待插入数据是已经排好序的，会发生什么情况？

关注公众号【编程珠玑】，获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。后台免费获取经典电子书和视频资源

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20220223/cbd9f106a6154a6590e327ffd6977cad.png
[640_wx_fmt_png]: /images/20220223/347cd942e8b24db3a1530a063b393997.png
[640_wx_fmt_png 1]: /images/20220223/9fe2103b01c142168a353bcaa2c6f099.png
[640_wx_fmt_png 2]: /images/20220223/a693f60224d241d4a493965376cca4e1.png
[640_wx_fmt_png 3]: /images/20220223/7ce13a056b2e411cb8c515c0a7f2c525.png
[640_wx_fmt_png 4]: /images/20220223/8085346cdaaa4bf29dc7c447f921e964.png
[640_wx_fmt_png 5]: /images/20220223/1533e5b8b7284fb2829b9e0bffa9a45e.png
[640_wx_fmt_png 6]: /images/20220223/63cf7fbb1354430c8b66febbdc8eb796.png
[640_wx_fmt_png 7]: /images/20220223/079d43e03ad847099c0098255de18eaf.png
[640_wx_fmt_jpeg 1]: /images/20220223/cedd43e04cd3429e8b4eb21e3f2544ed.png