高端网站建设服务商上海雍熙_商业模式顶层设计案例_google安卓版下载_今日国内新闻重大事件

时间:2025/7/12 9:25:18来源：https://blog.csdn.net/yang_pi_pi/article/details/144406252 浏览次数: 0次

1. 查找的基本概念

在这里插入图片描述

2. 静态查找

2.1 顺序查找

typedef int KeyType;
typedef int InfoType;
typedef struct
{KeyType key;InfoType otherdata;
}SeqList; // 顺序表类型
// 顺序查找

int SeqSearch(SeqList R[], int n, int k)
{int i = n;R[0].key = k;  // R[0].key为查找不成功的监视哨while (R[i].key != k)i--;return i; // 查找成功返回所找元素的索引，否则返回0；
}

2.2 有序表的查找

二分查找

int BinarySearch(SeqList R[], int n, int k)
{int left = 0, right = n - 1;int mid = 0;while (left <= right){mid = (left + right) / 2;if (R[mid].key > k)right = mid - 1;else if (R[mid].key < k)left = mid + 1;elsereturn mid;}return 0;// 没有找到
}

分块查找(索引顺序查找)

在这里插入图片描述

3. 树表形式的动态查找表

在这里插入图片描述

3.1 二叉排序树

在这里插入图片描述

二叉排序树的查找操作

// 二叉排序树的查找操作
BSTree* BSTSearch(BSTree* t, int k)
{while (t != NULL){if (t->key > k)t = t->lchild;else if (t->key < k)t = t->rchild;elsereturn t;}return NULL;
}

二叉排序树的插入操作和二叉树排序树的构造

愚蠢的bug，直接拿着main函数传入的指针遍历二叉排序树，导致每次插入节点时都会丢失二叉排序树的根

void BSTCreate(BSTree** t, int k)
{BSTree* pre = NULL;while ((*t) != NULL){if ((*t)->key > k) {pre = *t;*t = (*t)->lchild;}else if ((*t)->key < k) {printf("______________,右子树\n");pre = *t;*t = (*t)->rchild;}else  // 所查节点已经存在break;} //当所查节点不存在时if (*t == NULL){BSTree* tmp = (BSTree*)malloc(sizeof(BSTree));tmp->lchild = NULL;tmp->rchild = NULL;tmp->key = k;if (pre != NULL) {if (pre->key > k) {  // 应该插入pre的左孩子pre->lchild = tmp;}else { // 应该插入pre的右孩子printf("应该插入pre的右孩子\n");pre->rchild = tmp;}}else { // 二叉排序树还未建立printf("建立二叉排序树\n");*t = tmp;}}}

正确的方式

void BSTCreate(BSTree** t, int k)
{BSTree* pre = NULL,*current = *t;while (current != NULL){if (current->key > k) {pre = current;current = current->lchild;}else if (current->key < k) {/*	printf("______________,右子树\n");*/pre = current;current = current->rchild;}else  // 所查节点已经存在return;} BSTree* tmp = (BSTree*)malloc(sizeof(BSTree));tmp->lchild = NULL;tmp->rchild = NULL;tmp->key = k;if (pre != NULL) {if (pre->key > k) {  // 应该插入pre的左孩子pre->lchild = tmp;}else { // 应该插入pre的右孩子//printf("应该插入pre的右孩子\n");pre->rchild = tmp;}}// 二叉排序树还未建立else { printf("建立二叉排序树\n");*t = tmp;}}

在这里插入图片描述

删除二叉排序树中的节点

在这里插入图片描述

void BSTDeleteLeafChild(BSTree* pre, BSTree* current)
{if (pre->lchild == current) // 待删除节点为pre的左孩子{pre->lchild = NULL;}else if (pre->rchild == current) {pre->rchild = NULL;}free(current);current = NULL;
}
void BSTDeleteRightChild(BSTree* pre, BSTree* current)
{// 待删除节点current只有右孩子，直接将该有孩子替换到待删除节点位置即可if (pre->lchild == current) // 待删除节点为pre的左孩子{pre->lchild = current->rchild;free(current);current = NULL;}else if (pre->rchild == current) {pre->rchild = current->rchild;free(current);current = NULL;}else {printf("BSTDeleteRightChild:pre和current没有父子关系！！！\n");}}
void BSTDeleteLeftChild(BSTree* pre, BSTree* current)
{// 待删除节点current只有左孩子，直接将该左孩子替换到待删除节点位置即可if (pre->lchild == current) // 待删除节点为pre的左孩子{pre->lchild = current->lchild;free(current);current = NULL;}else if (pre->rchild == current) {pre->rchild = current->lchild;free(current);current = NULL;}else {printf("BSTDeleteRightChild:pre和current没有父子关系！！！\n");}
}
// 在二叉排序树种删除某个节点
void BSTDelete(BSTree** t, int k)
{/*会出现四种情况1. 待删除的节点为叶子2. 待删除的节点只有左孩子3. 待删除节点只有右孩子4. 待删除节点左右孩子都有*/BSTree* pre = NULL, * current = *t;while (current != NULL){if (current->key > k) {pre = current;current = current->lchild;}else if (current->key < k) {pre = current;current = current->rchild;}else  // 节点找到break;}if (current == NULL){printf("该节点没有找到\n");return;}//1. 待删除的节点为叶子if (current->lchild == NULL && current->rchild == NULL){BSTDeleteLeafChild(pre, current);}//2. 待删除的节点只有左孩子else if (current->lchild != NULL && current->rchild == NULL){BSTDeleteLeftChild(pre, current);}//3. 待删除节点只有右孩子else if (current->lchild == NULL && current->rchild != NULL){BSTDeleteRightChild(pre,current);}//4. 待删除节点左右孩子都有else  {// 1. 首先找到以待删除节点为根的最左节点BSTree* t1 = current,*t2 = current;while (t2->lchild != NULL){t1 = t2;t2 = t2->lchild;}current->key = t2->key; 2. 删除最左节点if(t2->rchild!=NULL)BSTDeleteRightChild(t1, t2);else {t1->lchild = NULL;free(t2);t2 = NULL;}}
}