二叉查找树、二叉搜索树、二叉排序树算法分析及实现

一、几个概念

二叉树（Binary Tree），是 n（n >= 0）个结点（每个结点最多只有2棵子树）的有限集合，该集合或为空集，称为空二叉树，或由一个根节点和两颗互不相交的，称为根节点的左子树和右子树组成，且其左右子树也分别是一颗二叉树。

二叉查找树（Binary Search Tree，简称 BST），又称为二叉搜索树、有序二叉树（Ordered Binary Tree）。二叉查找树或是空二叉树，或是满足以下三个性质的二叉树。

  • 若其左子树非空，则左子树上所有节点的值都小于根节点的值
  • 若其右子树非空，则右子树上所有节点的值都大于根节点的值
  • 其左右子树也分别是一棵二叉查找树

前序遍历二叉树（Pre-order Traversal）：从根结点出发，先访问该结点，然后前序遍历该结点的左子树，再然后前序遍历该结点的右子树

中序遍历二叉树（In-order Traversal）的规则为：从根结点出发，先中序遍历该结点的左子树，然后访问该结点，再然后中序遍历该结点的右子树

后序遍历二叉树（Post-order Traversal）的规则为：从根结点出发，先后序遍历该结点的左子树，然后后序遍历该结点的右子树，再然后访问该结点

二叉链表：是二叉树的一种链式存储结构，其中每个结点包含三个字段：一个数据字段(data)和两个指针字段(*lchild、*rchild)，分别指向该结点的左孩子和右孩子。如果某个结点没有左孩子或右孩子，那么对应的指针字段为NULL。

用 C 语言可以表述为：

typedef struct BST_node {
    int data;
    struct BST_node *lchild, *rchild;
}*BST;

二、二叉查找树的特性

通过中序遍历二叉查找树，得到的序列是有序的递增序列

如下图所示的一颗二叉查找树，其中序遍历的序列为：{3,6,8,10,15,20}

三、二叉查找树的查找

因为通过中序遍历二叉查找树，得到的序列是有序的递增序列，因此二叉查找树的查找跟二分查找法类似。

假设有一棵二叉查找树：T，每个结点有数据字段（data），有两个指针字段(*lchild、*rchild)，分别指向结点的左孩子和右孩子。查找 data，如果找到则返回该结点，否则返回 NULL

1、算法思路

  • 如果二叉查找树为空树，则查找失败，返回 NULL
  • 如果二叉查找树不为空

（1）如果 T->data == data，则返回该结点

（2）如果 T->data > data，则递归查找左子树

（3）如果 T->data < data，则递归查找右子树

时间复杂度

  • 最好的情况，根结点就是要查找的结点，所以最好时间复杂度为： O(1)
  • 最差的情况，二叉查找树退化为链表时，所以最差时间复杂度为： O(n)
  • 平均时间复杂度为：O(\log n)

2、实现代码

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

// 扩展二叉树前序序列
char *g_bad_str = "7654321########";
char *g_average_str = "421##3##65##7##";
int g_index = 0;
char *g_str = NULL;
int g_search_times = 0;

typedef enum BST_TYPE {
    BAD,
    AVERAGE
}BST_TYPE;

typedef struct BST_node {
    int data;
    struct BST_node *lchild, *rchild;
}*BST;

// 二叉查找树查找
BST bst_search(BST const T, const char data) {
    if (!T)
        return NULL;
    
    g_search_times++;
    if (T->data == data)
        return T;
    else if (T->data > data)
        return bst_search(T->lchild, data);
    else
        return bst_search(T->rchild, data);
}

void bst_create(BST *T, BST_TYPE type) {
    if (type == BAD)
        g_str = g_bad_str;
    else
        g_str = g_average_str;
    
    if (g_str[g_index] == '#') {
        *T = NULL;
        g_index++;
    } else {
        *T = malloc(sizeof(**T));
        (*T)->data = g_str[g_index];
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        g_index++;
        bst_create(&(*T)->lchild, type);
        bst_create(&(*T)->rchild, type);
    }
}

void bst_destroy(BST T) {
    if (!T)
        return;
    
    bst_destroy(T->lchild);
    bst_destroy(T->rchild);
    printf("free %c\n", T->data);
    free(T);
}

int main(int argc, char *argv[]) {
    BST tree_bad = NULL;
    BST tree_average = NULL;
    BST tree_search = NULL;
    
    g_index = 0;
    bst_create(&tree_bad, BAD);

    g_index = 0;
    bst_create(&tree_average, AVERAGE);

    g_search_times = 0;
    char data = '1';
    tree_search = bst_search(tree_bad, data);
    if (tree_search)
        printf("bad search_times = %d, data = %c\n", g_search_times, tree_search->data);
    else
        printf("can't find %c, bad search_times = %d\n", data, g_search_times);

    g_search_times = 0;
    data = '7';
    tree_search = bst_search(tree_average, data);
    if (tree_search)
        printf("average search_times = %d, data = %c\n", g_search_times, tree_search->data);
    else 
        printf("can't find %c, average search_times = %d\n", data, g_search_times);

    printf("----------\n");
    bst_destroy(tree_bad);
    printf("----------\n");
    bst_destroy(tree_average);

    return 0;
}

四、二叉查找树的插入

因为通过中序遍历二叉查找树，得到的序列是有序的递增序列，因此二叉查找树的插入跟二分插入法类似。

假设有一个二叉查找树指针：T，每个结点有数据字段（data），有两个指针字段(*lchild、*rchild)，分别指向结点的左孩子和右孩子，并将数据 data 插入到其中。

1、算法思路

（1）如果二叉查找树指针 T 为 NULL，则创建新结点，并插入到当前位置

（2）如果 T->data > data，则递归插入到左子树中

（3）如果 T->data <= data，则递归插入到右子树中

时间复杂度

  • 最好的情况，根结点为空时，所以最好时间复杂度为： O(1)
  • 最差的情况，二叉查找树退化为链表时，所以最差时间复杂度为： O(n)
  • 平均时间复杂度为：O(\log n)

2、实现代码

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

int g_insert_times = 0;

typedef struct BST_node {
    int data;
    struct BST_node *lchild, *rchild;
}*BST;

// 二叉查找树插入
void bst_insert(BST *T, int data) {
    g_insert_times++;
    if (!(*T)) {
        *T = malloc(sizeof(**T));
        (*T)->data = data;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        printf("insert %c success, insert times = %d\n", data, g_insert_times);
    } else if ((*T)->data > data) {
        bst_insert(&(*T)->lchild, data);
    } else {
        bst_insert(&(*T)->rchild, data);
    }
}

void bst_destroy(BST T) {
    if (!T)
        return;
    
    bst_destroy(T->lchild);
    bst_destroy(T->rchild);
    printf("free %c\n", T->data);
    free(T);
}

void visit_node(BST T) {
    printf("%c\n", T->data);
}

void in_order_tree(BST T) {
    if (!T)
        return;

    in_order_tree(T->lchild);
    visit_node(T);
    in_order_tree(T->rchild);
}

void bst_test(BST *T) {
    g_insert_times = 0;
    bst_insert(T, '4');
    g_insert_times = 0;
    bst_insert(T, '2');
    g_insert_times = 0;
    bst_insert(T, '6');
    g_insert_times = 0;
    bst_insert(T, '1');
    g_insert_times = 0;
    bst_insert(T, '5');
    g_insert_times = 0;
    bst_insert(T, '3');
    g_insert_times = 0;
    bst_insert(T, '7');
}

void bst_test1(BST *T) {
    g_insert_times = 0;
    bst_insert(T, '7');
    g_insert_times = 0;
    bst_insert(T, '6');
    g_insert_times = 0;
    bst_insert(T, '5');
    g_insert_times = 0;
    bst_insert(T, '4');
    g_insert_times = 0;
    bst_insert(T, '3');
    g_insert_times = 0;
    bst_insert(T, '2');
    g_insert_times = 0;
    bst_insert(T, '1');
}

int main(int argc, char *argv[]) {
    BST T = NULL;
    BST T1 = NULL;

    bst_test(&T);
    printf("-------------\n");
    bst_test1(&T1);
    printf("---------\n");
    bst_destroy(T);
    printf("---------\n");
    bst_destroy(T1);

    return 0;
}

五、二叉查找树的删除

1、算法思路

（1）如果被删除结点的左子树为空时，将该结点的父结点中，让指向该结点的指针域指向该结点的右子树，然后删除该结点

（2）如果被删除结点的右子树为空时，将该结点的父结点中，让指向该结点的指针域指向该结点的左子树，然后删除该结点

（3）如果被删除结点的左右子树都不为空时，情况复杂的多，因为父结点的左指针或右指针不能同时指向被删除结点的左右子树。我们可以采用

  • 合并删除法

合并删除法：将被删除结点的左右子树合并得到一棵树，然后把这棵树挂到被删除结点的父结点中。

如何将被删除结点的左右子树合并得到一棵树呢？

因为二叉查找树的特性是：左子树的每个结点的值都比右子树每个结点的值小，所以，可以把被删除结点的左子树中值最大的结点（左子树中，沿着右结点找，结点的右指针为空的结点）作为被删除结点的右子树的父结点 或 被删除结点的右子树中，值最小的结点（右子树中，沿着左结点找，结点的左指针为空的结点）作为被删除结点的左子树的父结点，从而合并得到一棵树，然后挂到被删除结点的父结点中。

时间复杂度

  • 最好的情况，被删除的结点是根结点，且二叉查找树退化为链表时，此时查找的时间复杂度为 O(1)，删除的时间复杂度为 O(1)，所以最好时间复杂度为： O(1)
  • 最差的情况，二叉查找树退化为链表时，此时查找的时间复杂度为 O(n)，删除的时间复杂度为 O(1)，所以最差时间复杂度为： O(n)
  • 平均时间复杂度为：O(\log n)

2、代码实现

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

typedef struct BST_node {
    int data;
    struct BST_node *lchild, *rchild;
}*BST;

// 二叉查找树查找
BST* bst_search(BST* const T, int data) {
    if (!(*T))
        return NULL;
    
    if ((*T)->data == data)
        return T;
    else if ((*T)->data > data)
        return bst_search(&(*T)->lchild, data);
    else 
        return bst_search(&(*T)->rchild, data);
}

// 二叉查找树插入
void bst_insert(BST *T, int data) {
    if (!(*T)) {
        *T = malloc(sizeof(**T));
        (*T)->data = data;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
    } else if ((*T)->data > data) {
        bst_insert(&(*T)->lchild, data);
    } else {
        bst_insert(&(*T)->rchild, data);
    }
}

void bst_destroy(BST T) {
    if (!T)
        return;
    
    bst_destroy(T->lchild);
    bst_destroy(T->rchild);
    free(T);
}

void visit_node(BST T) {
    printf("%d\n", T->data);
}

void in_order_tree(BST T) {
    if (!T)
        return;

    in_order_tree(T->lchild);
    visit_node(T);
    in_order_tree(T->rchild);
}

void bst_create1(BST *T) {
    // 2346
    bst_insert(T, 4);
    bst_insert(T, 2);
    bst_insert(T, 6);
    bst_insert(T, 3);

    in_order_tree(*T);
    printf("----------\n");
}

void bst_create2(BST *T) {
    // 1246
    bst_insert(T, 4);
    bst_insert(T, 2);
    bst_insert(T, 6);
    bst_insert(T, 1);

    in_order_tree(*T);
    printf("----------\n");
}

void bst_create3(BST *T) {
    // 12345678
    bst_insert(T, 7);
    bst_insert(T, 4);
    bst_insert(T, 8);
    bst_insert(T, 2);
    bst_insert(T, 6);
    bst_insert(T, 1);
    bst_insert(T, 3);
    bst_insert(T, 5);

    in_order_tree(*T);
    printf("----------\n");
}

void bst_delete_by_merge(BST *T, int data) {
    BST* del_node = bst_search(T, data);
    if (!(*del_node))
        return;
    
    BST tmp = (*del_node);

    if (!(*del_node)->lchild) // 左孩子为空
        *del_node = (*del_node)->rchild;
    else if (!(*del_node)->rchild) // 右孩子为空
        *del_node = (*del_node)->lchild;
    else { // 左右子树都不为空
        // 把被删除结点左子树中值最大的结点（左子树中，沿着右结点找，结点的右指针为空的结点）作为被删除右子树的父结点
        BST rmax = (*del_node)->lchild;
        while(rmax->rchild) {
            rmax = rmax->rchild;
        }
        rmax->rchild = (*del_node)->rchild;

        // 挂到被删除结点的父结点中
        *del_node = (*del_node)->lchild;
    }

    printf("delete %d success\n", tmp->data);
    free(tmp);
}

int main(int argc, char *argv[]) {
    BST T1 = NULL;
    BST T2 = NULL;
    BST T3 = NULL;

    bst_create1(&T1);
    bst_delete_by_merge(&T1, 2);
    in_order_tree(T1);
    printf("--------\n");

    bst_create2(&T2);
    bst_delete_by_merge(&T2, 2);
    in_order_tree(T2);
    printf("--------\n");

    bst_create3(&T3);
    bst_delete_by_merge(&T3, 4);
    in_order_tree(T3);
    printf("--------\n");


    bst_destroy(T1);
    bst_destroy(T2);
    bst_destroy(T3);

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/538407.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

如何编译OpenHarmony自带APP

如何编译OpenHarmony自带APP

作者&#xff1a;王石 概述 OpenHarmony 的主干代码是开源社区的重要学习资源&#xff0c;对于想进行应用开发和熟悉 OpenHarmony 能力的同学主干代码是非常重要的资源&#xff0c;在主干代码的 applications 目录里聚集了很多原生的应用实现&#xff0c;那么如何编译这些代码…
阅读更多...
java:JUnit单元测试

java:JUnit单元测试

Junit单元测试 介绍 一个用于编写和执行java单元测试的框架,可以帮助开发人员验证代码 单元测试 一种测试方法,用于校验程序中的最小可测试单元(通常是一个方法)是否按照预期工作. JUnit提供了一组注解和断言方法,使编写和执行单元测试变得更加方便 在开发过程中可以频繁…
阅读更多...
HarmonyOS开发实例：【菜单app】

HarmonyOS开发实例：【菜单app】

简介 分布式菜单demo 模拟的是多人聚餐点菜的场景&#xff0c;不需要扫码关注公众号等一系列操作&#xff0c;通过分布式数据库可以方便每个人可及时查看到订单详情&#xff0c;数量&#xff0c;总额等&#xff1b;效果如下 demo效果 工程目录 完整的项目结构目录如下 ├…
阅读更多...
代码随想录第38天| 509. 斐波那契数 70. 爬楼梯

代码随想录第38天| 509. 斐波那契数 70. 爬楼梯

理论基础 刷题大纲&#xff1a; 动态规划5步曲&#xff1a; 1、确定dp数组以及下标的含义 2、确定递推公式 3、dp数组如何初始化 4、确定遍历顺序 5、举例推导dp数组 509. 斐波那契数 509. 斐波那契数 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.co…
阅读更多...
SpringBoot学习笔记二

SpringBoot学习笔记二

SpringBoot学习笔记二 1.SpringBoot配置加载顺序1.1 内部配置加载顺序1.2 外部配置加载顺序 2. SpringBoot整合其他框架2.1 SpringBoot整合Test2.2 SpringBoot整合Redis 1.SpringBoot配置加载顺序 1.1 内部配置加载顺序 同理可知&#xff0c;父项目中的confg下的配置优先级最…
阅读更多...
Bitmap OOM

Bitmap OOM

老机器Bitmap预读仍然OOM&#xff0c;无奈增加一段&#xff0c;终于不崩溃了。 if (Build.VERSION.SDK_INT < 21)size 2; 完整代码&#xff1a; Bitmap bitmap; try {//Log.e(Thread.currentThread().getStackTrace()[2] "", surl);URL url new URL(surl);…
阅读更多...
【数据结构与算法】之8道顺序表与链表典型编程题心决！

【数据结构与算法】之8道顺序表与链表典型编程题心决！

个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 目录 1、顺序表 1.1 合并两个有序数组 1.2 原地移除数组中所有的元素va…
阅读更多...
2024/4/5—力扣—下一个排列

2024/4/5—力扣—下一个排列

代码实现&#xff1a; 思路&#xff1a;两遍扫描 void swap(int *a, int *b) {int t *a;*a *b;*b t; }void reverse(int *nums, int l, int r) {while (l < r) {swap(nums l, nums r);l;r--;} }void nextPermutation(int *nums, int numsSize) {int i numsSize - 2;wh…
阅读更多...
手把手从零搭建ChatGPT网站midjourney-AI绘画系统，附详细搭建部署教程文档

手把手从零搭建ChatGPT网站midjourney-AI绘画系统，附详细搭建部署教程文档

一、系统前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持…
阅读更多...
前端开发攻略---用JavaScript打造炫酷数字变化动画效果：手写实现你的自定义动画函数！支持更改任意数字、动画速度

前端开发攻略---用JavaScript打造炫酷数字变化动画效果：手写实现你的自定义动画函数！支持更改任意数字、动画速度

1、演示 2、介绍 这篇文章将向您展示如何使用JavaScript来创建一个自定义的动画函数&#xff0c;以实现数字变化效果。我们将深入了解前端动画的本质&#xff0c;并通过手写代码来实现这个炫酷的数字变化动画效果。您将学到如何利用JavaScript来操作DOM元素&#xff0c;控制动画…
阅读更多...
知名专业定制线缆源头工厂推荐-精工电联：智能制造线缆的前沿技术探索

知名专业定制线缆源头工厂推荐-精工电联：智能制造线缆的前沿技术探索

优质定制线缆源头厂家推荐-精工电联&#xff1a;智能制造线缆的前沿技术探索 知名专业定制线缆源头工厂推荐-精工电联&#xff1a;智能制造线缆的前沿技 在科技飞速发展的当今时代&#xff0c;智能制造已成为工业4.0的核心驱动力。精工电联&#xff0c;作为智能制造领先的高品质…
阅读更多...
Pycharm中 Console 打不开

Pycharm中 Console 打不开

引言&#xff1a; 近年来&#xff0c;越来越多的高校洞察到了Pycharm为代表的编程IDE软件的重要性&#xff0c;已经购买了对应的版权。对于这些软件的使用&#xff0c;许多本科生可能还比较陌生&#xff0c;这系列博客主要总结了一些常见的BUG及对应的解决方案。本篇博客主要总…
阅读更多...
核心api实操-Activiti7从入门到专家（5）

核心api实操-Activiti7从入门到专家（5）

背景 上一节已经搭建了&#xff0c;具体的开发环境&#xff0c;数据库&#xff0c;并且找了一个可以用bpmnjs流程设计器&#xff0c;这一些&#xff0c;我们对核心api做个基础的实操&#xff0c;有个感性的认知&#xff0c;另外对数据库和基本数据流动有个理解。 部署 模板部…
阅读更多...
Java | Leetcode Java题解之第17题电话号码的字母组合

Java | Leetcode Java题解之第17题电话号码的字母组合

题目&#xff1a; 题解&#xff1a; class Solution {public List<String> letterCombinations(String digits) {List<String> combinations new ArrayList<String>();if (digits.length() 0) {return combinations;}Map<Character, String> phoneM…
阅读更多...
open-sora

open-sora

Open-Sora&#xff0c;高效复现类Sora视频生成方案开源&#xff01;魔搭社区最佳实践教程来啦&#xff01;https://mp.weixin.qq.com/s/WMQIDgZs2MBPGtx18XSXgw Open-Sora开源方案讲解开源但“平替”的方案。https://mp.weixin.qq.com/s/nPYCzgBA7hIsPZ6PCyXxKQOpen-Sora/docs…
阅读更多...
Qt信号与槽

Qt信号与槽

我们在使用Qt的时候&#xff0c;不使用Qt Designer 的方式进行开发&#xff0c;使用ui文件&#xff0c;信号与槽的连接方式是生成代码之后才能在setupUi函数里才能看到&#xff0c;或者需要进入Ui设计器里的信号槽模式里才能看到信号槽的连接。所以我们最好使用代码绘制界面。 …
阅读更多...
CCD机器视觉在工业生产中起到什么作用？

CCD机器视觉在工业生产中起到什么作用？

CCD机器视觉尺寸测量是基于相对测量方法&#xff0c;通过可追溯性、放大校准、自动边缘提升和屏幕图像测量来计算实际尺寸。在精密测量中&#xff0c;放大倍数必须达到35倍或更高&#xff0c;才能达到微米级的精度。此时&#xff0c;视线宽度小于5mm。对于大于5mm的物体&#x…
阅读更多...
游戏提示找不到steam_api64.dll，无法继续执行代码的解决方法

游戏提示找不到steam_api64.dll，无法继续执行代码的解决方法

在我们日常沉浸在电脑世界中&#xff0c;尽情享受各类电子游戏带来的精彩与刺激时&#xff0c;偶尔会遭遇一些令人困扰的技术问题。这次&#xff0c;当您正全神贯注地启动心仪的游戏&#xff0c;期待着新一局冒险或竞技的开始&#xff0c;电脑屏幕上却冷不防地弹出一条警示信息…
阅读更多...
--每周分享--

--每周分享--

分享内容&#xff1a; 1.单链表的归并排序 2.一道有趣的思考题 分享细节&#xff1a; 单链表的归并排序 主要思想&#xff1a;递归 怎么理解&#xff1f;下面具体说明&#xff1a; 1.首先&#xff0c;我从整体的思考步骤说明&#xff1a;先分区&#xff0c;再排序&#…
阅读更多...
游标的定义和类型

游标的定义和类型

Oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 游标的基本概念 游标从字面上理解为游动的光标&#xff0c;可以使用 Excel 表格来想象游标的作用&#xff0c;游标指向每一行&#xff0c;通过游标访问每行数据。 在 Orac…
阅读更多...
最新文章

Copyright @ 2022~2023