C语言二叉查找树性质详解及实例代码

什么是二叉查找树？

二叉查找树，也称二叉搜索树，它是一种基于对比的动态数据结构。它的定义如下：

• 每个节点都包含一个键值，且键值唯一；
• 每个节点的左子树只包含小于当前节点的节点；
• 每个节点的右子树只包含大于当前节点的节点；
• 左右子树都是二叉搜索树；

二叉查找树的性质

二叉查找树的性质体现在它的增、删、查等操作中，具体有以下几种性质：

• 查找节点：在二叉查找树中查找一个节点，首先查找根节点，如果查找值等于根节点的键值，则查找结束；如果查找值小于根节点的键值，则在左子树中继续查找；如果查找值大于根节点的键值，则在右子树中继续查找。

• 插入节点：在二叉查找树中插入一个节点，首先查找根节点，如果查找值等于根节点的键值，则插入失败；如果查找值小于根节点的键值，则在左子树中继续查找；如果查找值大于根节点的键值，则在右子树中继续查找，直到找到一个空节点，将新节点插入到该节点处。

• 删除节点：在二叉查找树中删除一个节点，首先查找要删除的节点，如果该节点没有子节点，则直接删除；如果该节点只有一个子节点，则将该节点的子节点替换该节点；如果该节点有两个子节点，则用该节点的后继节点（即右子树中最小的节点）替换该节点，然后删除该后继节点。

• 中序遍历：中序遍历二叉查找树可以得到一个递增的有序序列。

二叉查找树实现过程

以下是C语言实现二叉查找树的过程，包括插入和查找操作。

#include <stdio.h>
#include <stdlib.h>

/* 二叉查找树定义 */
typedef struct _node {
    int key;
    struct _node *left;
    struct _node *right;
} Node, *Tree;

/* 查找节点 */
Node* search(Tree t, int key) {
    if (t == NULL) {
        return NULL;
    }

    if (key == t->key) {
        return t;
    } else if (key < t->key) {
        return search(t->left, key);
    } else {
        return search(t->right, key);
    }
}

/* 插入节点 */
Node* insert(Tree t, int key) {
    /* 建立新节点 */
    Node *p = (Node*)malloc(sizeof(Node));
    p->key = key;
    p->left = NULL;
    p->right = NULL;

    /* 查找插入位置 */
    if (t == NULL) {
        t = p;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }

    return t;
}

/* 中序遍历 */
void inorder(Tree t) {
    if (t != NULL) {
        inorder(t->left);
        printf("%d ", t->key);
        inorder(t->right);
    }
}

/* 测试入口 */
int main() {
    Tree t = NULL;

    t = insert(t, 5);
    t = insert(t, 3);
    t = insert(t, 7);
    t = insert(t, 1);
    t = insert(t, 9);

    Node *search_node = search(t, 7);
    if (search_node != NULL) {
        printf("Found node key=%d\n", search_node->key);
    } else {
        printf("Not found\n");
    }

    printf("Inorder traversal: ");
    inorder(t);

    return 0;
}

二叉查找树使用示例1

以下是一个示例代码，它演示了如何使用二叉查找树来存储整数，并输出各整数。

#include <stdio.h>
#include <stdlib.h>

/* 二叉查找树定义 */
typedef struct _node {
    int key;
    struct _node *left;
    struct _node *right;
} Node, *Tree;

/* 插入节点 */
Node* insert(Tree t, int key) {
    /* 建立新节点 */
    Node *p = (Node*)malloc(sizeof(Node));
    p->key = key;
    p->left = NULL;
    p->right = NULL;

    /* 查找插入位置 */
    if (t == NULL) {
        t = p;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }

    return t;
}

/* 中序遍历 */
void inorder(Tree t) {
    if (t != NULL) {
        inorder(t->left);
        printf("%d ", t->key);
        inorder(t->right);
    }
}

/* 测试入口 */
int main() {
    Tree t = NULL;

    t = insert(t, 5);
    t = insert(t, 3);
    t = insert(t, 7);
    t = insert(t, 1);
    t = insert(t, 9);

    printf("Inorder traversal: ");
    inorder(t);

    return 0;
}

输出结果如下：

Inorder traversal: 1 3 5 7 9

二叉查找树使用示例2

以下是一个验证二叉查找树的例子，它演示了如何判断一个树是否是二叉查找树以及如何验证一个节点是否是其子树的最大最小值之间。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* 二叉查找树定义 */
typedef struct _node {
    int key;
    struct _node *left;
    struct _node *right;
} Node, *Tree;

/* 插入节点 */
Node* insert(Tree t, int key) {
    /* 建立新节点 */
    Node *p = (Node*)malloc(sizeof(Node));
    p->key = key;
    p->left = NULL;
    p->right = NULL;

    /* 查找插入位置 */
    if (t == NULL) {
        t = p;
    } else if (key < t->key) {
        t->left = insert(t->left, key);
    } else if (key > t->key) {
        t->right = insert(t->right, key);
    }

    return t;
}

/* 中序遍历 */
void inorder(Tree t) {
    if (t != NULL) {
        inorder(t->left);
        printf("%d ", t->key);
        inorder(t->right);
    }
}

/* 验证二叉查找树 */
bool is_bst(Tree t, int min, int max) {
    if (t == NULL) {
        return true;
    }

    if (t->key <= min || t->key >= max) {
        return false;
    }

    return is_bst(t->left, min, t->key) && is_bst(t->right, t->key, max);
}

/* 测试入口 */
int main() {
    Tree t = NULL;

    t = insert(t, 5);
    t = insert(t, 3);
    t = insert(t, 7);
    t = insert(t, 1);
    t = insert(t, 9);

    printf("Inorder traversal: ");
    inorder(t);

    if (is_bst(t, INT_MIN, INT_MAX)) {
        printf("\nTree %p is a binary search tree\n", t);
    } else {
        printf("\nTree %p is NOT a binary search tree\n", t);
    }

    return 0;
}

输出结果如下：

Inorder traversal: 1 3 5 7 9 
Tree 0x7f9161401690 is a binary search tree

以上就是二叉查找树的介绍和示例代码，希望能够对读者理解和使用它有所帮助。