数据结构学习笔记 :二叉搜索树与高效查找算法详解
目录
- 二叉搜索树(BST)实现
1.1 顺序存储实现
1.2 链式存储实现 - 查找算法
2.1 顺序查找
2.2 折半查找
2.3 哈希查找 - 总结与应用场景
- 代码示例与完整实现
一、二叉搜索树(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;
}