当前位置: 首页 > news >正文

数据结构学习笔记 :二叉搜索树与高效查找算法详解

目录

  1. 二叉搜索树(BST)实现
    1.1 顺序存储实现
    1.2 链式存储实现
  2. 查找算法
    2.1 顺序查找
    2.2 折半查找
    2.3 哈希查找
  3. 总结与应用场景
  4. 代码示例与完整实现

一、二叉搜索树(BST)实现

1. 顺序存储实现

BST的顺序存储基于完全二叉树的特性,通过数组模拟树的结构。

核心代码
#include <stdio.h>
#include <stdbool.h>
#define MaxSize 100
typedef int ElemType;typedef struct Tree {ElemType data[MaxSize]; // 数据域bool flag[MaxSize];     // 标记节点是否有效
} Tree;// 初始化
void InitTree(Tree *t) {for (int i = 0; i < MaxSize; i++) {t->flag[i] = false;}
}// 插入节点
bool insert_node(Tree *t, ElemType e) {int i = 1; // 根节点从1开始while (i < MaxSize) {if (!t->flag[i]) { // 找到空位置插入t->data[i] = e;t->flag[i] = true;return true;} else {if (t->data[i] > e) {i = 2 * i;      // 左子树方向} else if (t->data[i] < e) {i = 2 * i + 1; // 右子树方向} else {return false; // 重复值不插入}}}return false;
}// 删除节点(复杂度较高)
void del_node(Tree *t, int n) {// 实现逻辑:递归删除叶子节点// 代码见知识库完整示例
}// 中序遍历打印
void print_tree(Tree *t) {for (int i = 1; i < MaxSize; i++) {if (t->flag[i]) {printf("data[%d]=%d\n", i, t->data[i]);}}
}

2. 链式存储实现

链式BST通过动态节点实现,支持高效插入、删除和遍历。

核心代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int ElemType;
typedef struct BitNode {ElemType data;struct BitNode *lchild, *rchild;
} BitNode, *BitTree;// 新建节点
BitNode* newnode(ElemType e) {BitNode *node = (BitNode*)malloc(sizeof(BitNode));node->data = e;node->lchild = node->rchild = NULL;return node;
}// 插入节点
bool insert_node(BitTree *t, BitNode *new) {if (*t == NULL) { // 空树直接插入根节点*t = new;return true;}BitNode *p = *t;while (1) {if (new->data < p->data) { // 左子树方向if (p->lchild == NULL) {p->lchild = new;return true;}p = p->lchild;} else if (new->data > p->data) { // 右子树方向if (p->rchild == NULL) {p->rchild = new;return true;}p = p->rchild;} else {return false; // 重复值不插入}}
}// 中序遍历
void MidOrder(BitNode *root) {if (root == NULL) return;MidOrder(root->lchild);printf("%d ", root->data);MidOrder(root->rchild);
}// 删除节点(递归实现)
BitNode* del_node(BitTree t, ElemType e) {if (t == NULL) return NULL;if (e < t->data) { // 左子树查找t->lchild = del_node(t->lchild, e);} else if (e > t->data) { // 右子树查找t->rchild = del_node(t->rchild, e);} else { // 找到节点if (t->lchild == NULL && t->rchild == NULL) { // 叶子节点free(t);return NULL;} else if (t->lchild != NULL) { // 替换为左子树最大值BitNode *tmp = t->lchild;while (tmp->rchild != NULL) tmp = tmp->rchild;t->data = tmp->data;t->lchild = del_node(t->lchild, tmp->data);} else { // 替换为右子树最小值BitNode *tmp = t->rchild;while (tmp->lchild != NULL) tmp = tmp->lchild;t->data = tmp->data;t->rchild = del_node(t->rchild, tmp->data);}}return t;
}

二、查找算法

1. 顺序查找

原理:逐个遍历数组,直到找到目标或遍历结束。

bool find(int *a, int size, int dat) {for (int i = 0; i < size; i++) {if (a[i] == dat) return true;}return false;
}

2. 折半查找

前提:数组必须有序。

bool half_find(int *a, int size, int dat) {int start = 0, end = size - 1, mid;while (start <= end) {mid = (start + end) / 2;if (a[mid] == dat) return true;else if (a[mid] > dat) end = mid - 1;else start = mid + 1;}return false;
}

3. 哈希查找

原理:通过哈希函数将数据映射到哈希表中,解决冲突(如链地址法)。

核心代码
#include <stdio.h>
#include <stdlib.h>
#define HASH_GEN 15 // 哈希表大小typedef struct Inode {int data;struct Inode *next;
} Inode;typedef struct {Inode *hash[HASH_GEN]; // 哈希表数组int count;             // 元素个数
} HashTable;// 哈希函数(取模法)
int hash_code(int dat) {return dat % HASH_GEN;
}// 初始化哈希表
void init_hash(HashTable *h) {for (int i = 0; i < HASH_GEN; i++) {h->hash[i] = NULL;}h->count = 0;
}// 插入节点
bool insert_hash_node(HashTable *h, int dat) {Inode *new = (Inode*)malloc(sizeof(Inode));new->data = dat;new->next = NULL;int index = hash_code(dat);new->next = h->hash[index];h->hash[index] = new;h->count++;return true;
}// 查找节点
bool find_hash_node(HashTable *h, int dat) {int index = hash_code(dat);Inode *p = h->hash[index];while (p != NULL) {if (p->data == dat) return true;p = p->next;}return false;
}

三、总结与应用场景

BST的优缺点

特性顺序存储链式存储
插入/删除效率低(需递归查找空位)高(动态分配,直接操作指针)
空间利用率低(需预留大数组空间)高(仅分配必要节点空间)
适用场景完全二叉树(如堆结构)动态扩展的BST(如数据库索引)

查找算法对比

算法时间复杂度适用场景
顺序查找O(n)无序小规模数据
折半查找O(log n)有序且静态数据
哈希查找平均O(1)高频查询、大规模数据

四、代码示例与完整实现

1. BST顺序存储完整示例

int main() {Tree tree;InitTree(&tree);// 插入数据for (int i = 0; i < 10; i++) {int n;scanf("%d", &n);insert_node(&tree, n);}print_tree(&tree);// 删除根节点del_node(&tree, 1);print_tree(&tree);return 0;
}

2. 链式BST与哈希查找完整示例

int main() {BitTree root = NULL;HashTable hast_list;init_hash(&hast_list);// 插入BST节点for (int i = 0; i < 100; i++) {BitNode *node = newnode(i);insert_node(&root, node);}// 插入哈希表节点for (int i = 0; i < 100; i++) {insert_hash_node(&hast_list, i);}// 测试查找if (find_hash_node(&hast_list, 121)) {printf("哈希查找成功\n");}// 中序遍历BSTMidOrder(root);return 0;
}

http://www.xdnf.cn/news/7723.html

相关文章:

  • React 列表渲染基础示例
  • DFS/BFS专练-搞定图论基础!(从海岛问题过渡至图论基础应用C++/C)
  • 无刷电机槽数相同、转子极数不同的核心区别
  • Nacos安装及数据持久化
  • ESP32之本地HTTP服务器OTA固件升级流程,基于VSCode环境下的ESP-IDF开发(附源码)
  • 【Spring Boot】MyBatis入门:连接Mysql数据库、测试单元、连接的常见错误
  • 汇编语言中的数据
  • 基于C++(MFC)的细胞识别程序
  • 人工智能在后端开发中的革命:从架构到运维
  • 前端:uniapp中uni.pageScrollTo方法与元素的overflow-y:auto之间的关联
  • 极狐GitLab 项目导入导出设置介绍?
  • 架构师面试(三十一):IM 消息收发逻辑
  • 手撕STL——vector
  • 利用DeepSeek设计一个HTML批量转换工具设计
  • Hadoop的三大结构及其作用?
  • hadoop的三大结构及各自的作用
  • yarn的定义
  • 「数据可视化 D3系列」入门第九章:交互式操作详解
  • 自动驾驶与机器人算法学习
  • 【区块链通用服务平台及组件】京北方分布式身份管理平台 | FISCO BCOS 应用案例
  • java八股之并发编程
  • 医院数据中心智能化数据上报与调数机制设计
  • 仿腾讯会议项目开发——界面关闭功能实现
  • Flink介绍——实时计算核心论文之Kafka论文详解
  • java输出、输入语句
  • Vue3 Composition API与十大组件开发案例详解
  • 杂记-LeetCode中部分题思路详解与笔记-HOT100篇-其四
  • 【datawhaleAI春训营第一期笔记】AI+航空安全
  • Tensorflow实现用接口调用模型训练和停止训练功能
  • Mac mini 安装mysql数据库以及出现的一些问题的解决方案