【数据结构】二叉搜索树（Binary Search Tree）基本介绍

前言

一、什么是二叉搜索树

概念及其介绍

前言

最近正在学习数据结构，听的是mycodeschool.com中程序员Harsha Suryanarayana的课程，二叉搜索树是数据结构中的重点，并且比较难理解，所以我会按照这位老师的讲法把二叉搜索树这一部分以博客的形式记录下来，加深理解学习。如果有错误的地方，希望大家可以指出，帮助我改正，十分感谢。

一、什么是二叉搜索树

概念及其介绍

二叉搜索树（英语：Binary Search Tree，BST），也称为二叉查找树、二分搜索树、有序二叉树或排序二叉树。满足以下几个条件：

若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

它的左、右子树也都是二叉搜索树（因此可以使用递归实现）。

如下图所示：

适用说明

二分搜索树有着高效的插入、删除、查询操作。

平均时间的时间复杂度为 O(log n)，最差情况为 O(n)。二分搜索树与堆不同，不一定是完全二叉树，底层不容易直接用数组表示故采用链表来实现二分搜索树。

	查找元素	插入元素	删除元素
普通数组	O(n)	O(n)	O(n)
顺序数组	O(logn)	O(n)	O(n)
二分搜索树	O(logn)	O(logn)	O(logn)

二、C语言实例代码

1. 创建节点

首先，我们需要定义一个节点结构，如下图所示，并创建一个新的节点。

//定义二叉搜索树的节点结构
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

//创建一个新的节点,返回一个指针
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

2. 插入节点

插入节点的过程是递归的。我们从根节点开始，根据键值的大小决定是向左子树还是右子树插入。

//插入一个节点到二叉搜索树中，返回根节点的地址
struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {   //如果树是空的，创建一个新节点，把它设置为根节点
        root = createNode(data);
        return root;
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

//主函数
int main()
{
    struct Node* root = NULL;//创建一个空的树
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
}

3. 查找节点

查找节点的过程也是递归的。我们从根节点开始，根据键值的大小决定是向左子树还是右子树查找。

//在二叉树中查找一个节点，返回一个指针
struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }

    if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}

4.主函数

最后我们编写一个主函数来测试这些功能

//主函数
int main() {
    struct Node* root = NULL;//创建一个空的树
    insert(root, 20);//在二叉树中插入一个节点
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
   
    int key = 40;//在二叉树中查找值为40的节点
    if (search(root, key) != NULL) {
        printf("%d 存在于二叉搜索树中。\n", key);
    }
    else {
        printf("%d 不存在于二叉搜索树中。\n", key);
    }

    key = 10;//在二叉树中查找值为10的节点
    if (search(root, key) != NULL) {
        printf("%d 存在于二叉搜索树中。\n", key);
    }
    else {
        printf("%d 不存在于二叉搜索树中。\n", key);
    }

    return 0;
}

三、内存中的栈与堆讲解

内存四区

系统分配给一个程序的内存，在经典的架构中可以被分为四部分，如下图所示，

代码区（Code)：用来存放程序的指令

全局区（Static/Global)：用于存放全局变量和静态变量以及常量

栈区（Stack): 暂存空间，用来执行函数，暂存所有的局部变量和函数参数以及函数调用后返回的地址

堆区（Heap): 自由储存空间，由程序员来进行分配，灵活性大，但其分配的速度较慢，地址不连续，容易碎片化

程序运行时栈和堆的变化

程序首先进入main函数，栈中开辟出一部分空间给main函数，程序运行到第一行创建一个root指针指向空，运行到第二行main函数运行暂停，程序进入insert函数，分配栈帧给insert函数，在insert函数中因为root是空的，所以程序进入createNode函数，分配栈帧给createNode函数，insert函数停止运行，在堆中创建一个新的节点，栈中创建一个newNode指针指向这个节点，并给节点赋值，如下图所示。

createNode函数结束，分配给它的栈帧将会被收回，将root指针返回给insert函数，继续运行insert函数，root指向节点，insert函数运行结束，栈帧收回，返回root指针，此时main函数中root指针指向节点。

程序继续执行下一行，main函数暂停，分配给insert函数所需的栈帧，root不为空，比较数据的大小，然后进行函数递归，root左节点再插入一个节点，新的root为空，再进入createNode函数创建一个新的节点，返回节点的指针。

creatNode函数栈帧被收回，继续执行insert，root指向新节点，insert函数暂停，返回到第一层insert函数，root地址返回给root->left,root->left指向新节点，也就是root指向的地址为200节点的左孩节点地址为150，因此这两个节点连接起来了，最后insert函数结束，控制返回到main这一行，此时二叉树成功插入两个节点。接下来程序执行过程和上面类似，就不再模拟演示了。

结语

十分感谢大家能看到这里，这篇博客主要是对二叉搜索树进行一些基本介绍，和讲解它的运行逻辑，希望能对初学者带来一些帮助，也希望大家能提出宝贵的建议，下一篇将会解决二叉搜索树的一些问题和它的简单使用。