查找：折半查找、平衡二叉树、散列表（习题-1、5、6）二叉排序树（习题-2、3、4）
创始人
2024-05-04 02:12:54
0次

一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com

Time of completion：2023.1.1
Last edited: 2023.1.1

目录

查找：折半查找、平衡二叉树、散列表（习题-1、5、6）

第1关：折半查找的递归算法（算法设计题1）

任务描述

相关知识

编程要求

测试说明

参考代码

第2关：平衡二叉树的高度（算法设计题5）

任务描述

相关知识

编程要求

测试说明

参考代码

第3关：散列表关键字的插入和删除（算法设计题6）

任务描述

相关知识

编程要求

测试说明

参考代码

 查找：二叉排序树（习题-2、3、4）

第1关：二叉排序树判别（算法设计题2）

任务描述

相关知识

编程要求

测试说明

参考代码

第2关：不小于x的所有数据（算法设计题3）

任务描述

相关知识

编程要求

测试说明

参考代码

第3关：二叉排序树和查找（算法设计题4）

任务描述

相关知识

编程要求

测试说明

参考代码

作者有言

查找：折半查找、平衡二叉树、散列表（习题-1、5、6）

第1关：折半查找的递归算法（算法设计题1）

任务描述

写出折半查找的递归算法。

相关知识

折半查找。

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成本关任务。

测试说明

平台会对你编写的代码进行测试：

测试输入（共3行，第1行为元素个数n；第二行为空格分隔的n个元素；第三行为待查找元素）：

5

1 2 3 4 5 4

预期输出（共1行，待查元素所在位置）：

4

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;using namespace std;
typedef long long LL;
typedef pair PII;int n;int BinSearch_Cur(int a[],int key,int low,int high)
{/***********************Begin**********************/low = 1,  high = n;while(low <= high){int mid = (low + high) >> 1;if(key == a[mid]) return mid;else if(key < a[mid]) high = mid - 1;else low = mid + 1;}return 0;/*********************** End **********************/
}
int main()
{while(cin>>n){if(n==0) break;int a[99], key;for(int i = 1; i <= n; i ++) cin>>a[i];cin >> key;								cout << BinSearch_Cur(a, key, 0, n - 1) << endl;	}return 0;
}

第2关：平衡二叉树的高度（算法设计题5）

任务描述

本关任务：一棵平衡二叉树的每个结点都标明了平衡因子b，编写算法求解该平衡二叉树的高度。

相关知识

平衡二叉树

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成所要求任务。

测试说明

平台会对你编写的代码进行测试：

测试输入（共1行字符串，为先序构建二叉树的序列）：

110###0##

预期输出（共1行，为二叉树高度）：

3

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;using namespace std;
typedef long long LL;
typedef pair PII;typedef struct BiTNode
{char data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;void CreatBiTree(BiTree &T)
{  //按先序次序输入二叉树中结点的值 创建二叉链表表示的二叉树 char ch;cin>>ch;if(ch=='#') T = NULL;         //递归结束 空树 else{                         //递归创建二叉树 T = new BiTNode;          //生成根节点T->data = ch;             //根结点数据域置ch CreatBiTree(T->lchild);   //递归创建左子树 CreatBiTree(T->rchild);   //递归创建右子树 } 
} 
int Depth(BiTree T)
{/***********************Begin**********************/if(!T) return 0;else if(!(T -> lchild) && !(T -> rchild)) return 1;return Depth(T -> lchild) >= Depth(T -> rchild) ? Depth(T -> lchild) + 1 : Depth(T -> rchild) + 1;/*********************** End **********************/
}
int main()
{BiTree T;CreatBiTree(T);cout<

第3关：散列表关键字的插入和删除（算法设计题6）

任务描述

本关任务：创建散列表，并在其中插入n个关键字；然后删除指定关键字K。设散列函数为H，解决冲突的方法为链地址法。

相关知识

散列表

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成所要求任务。

测试说明

平台会对你编写的代码进行测试，以下为两个测试用例的例子。

测试输入（共3行：第1行是关键字的个数n；第二行为空格分隔的n个关键字；第3行为待删除的关键字K):

 预期输出(共2组：第1组为插入完成后的地址-关键字对集，第2组为删除K之后的地址-关键字对集如下所示)：

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;using namespace std;
typedef long long LL;
typedef pair PII;#define LENGTH 7typedef struct LNode
{int data;struct LNode *next;
}LNode, *LinkList;LinkList HT[LENGTH];int H(int data)
{return data % LENGTH;
}bool Insert_K( )
{/***********************Begin**********************/int n; cin >> n;int res = H(n);LNode *p = HT[res];while(p -> next)if(p -> next -> data == n) return false;else p = p -> next;
//	LNode *p = HT[res] -> next;            // 被 segmentation fault 啦，气死我啦…… 
//	while(p)
//		if(p -> data == n) return false;
//		else p = p -> next;LNode *s = new LNode;s -> data = n; s -> next = p -> next;p -> next = s;
//	p -> data = n;return true;/*********************** End **********************/
}
bool Delete_K(int data)
{/***********************Begin**********************/int res = H(data);LNode *p = HT[res];while(p -> next)if(p -> next -> data == data) {LNode *s = p -> next;p -> next = s -> next;delete s;return true;}else if(p -> next -> data != data) p = p -> next;return false;/*********************** End **********************/
}
void Output()
{//输出数据for(int i=0;inext;  		//p初始化为链表的首元结点while(p){cout<data;p=p->next;if(p) cout<<" ";}cout<next=NULL;}
}
int main()
{initHash();int n,ndel;cin>>n;for(int i=0;i>ndel;Delete_K(ndel);Output();return 0;
}

 查找：二叉排序树（习题-2、3、4）

第1关：二叉排序树判别（算法设计题2）

任务描述

写一个判别给定二叉树是否为二叉排序树的算法。

相关知识

二叉排序树。

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成本关任务。

测试说明

平台会对你编写的代码进行测试：

测试输入（共一行）：

ba##c##

预期输出：

YES

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;using namespace std;
typedef long long LL;
typedef pair PII;typedef struct BiTNode
{char data; struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;void CreateBiTree(BiTree &T,char a[],int &i)
{//先序建立二叉树/***********************Begin**********************/if(a[i] == '#')  T = NULL;			else{							T = new BiTNode, T -> data = a[i];					CreateBiTree(T -> lchild, a, ++ i);	CreateBiTree(T -> rchild, a, ++ i);}/*********************** End **********************/
}BiTree pre=NULL;									//前驱指针void JudgeBST(BiTree T,int &flag)
{//判断二叉树T是否是二叉排序树，flag初值为1if(T!=NULL&&flag){ /***********************Begin**********************/JudgeBST(T -> lchild, flag);if (!pre) pre = T;else if (pre -> data < T -> data) pre = T;else flag = false;/*********************** End **********************/}else return;JudgeBST(T -> rchild, flag);
}
int main()
{char a[99];//输入先序序列cin>>a;if(strcmp(a,"#")!=0){int i=-1;int flag=1;BiTree T;CreateBiTree(T,a,++i);JudgeBST(T,flag);if(flag)cout<<"YES"<

第2关：不小于x的所有数据（算法设计题3）

任务描述

本关任务：已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild, data, rchild），其中lchild、rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值≥x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。

相关知识

二叉排序树

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成所要求任务。

测试说明

平台会对你编写的代码进行测试：

测试输入（共三行，第一行为列表元素个数n；第二行为以空格分隔的列表中的元素；第三行为x的值）：

5 1 3 4 2 5 3

预期输出（共两行，第一行为排序后的列表；第二行为不小于x的所有元素）

1 2 3 4 5 3 4 5

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;using namespace std;
typedef long long LL;
typedef pair PII;typedef struct BSTNode
{//二叉排序树的二叉链表存储表示int data;struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;void InsertBST(BSTree &T,int e){/***********************Begin**********************/if(!T){BSTNode *S = new BSTNode;S  -> data = e, S -> lchild = S -> rchild = NULL, T = S;}else if(e < T -> data) InsertBST(T -> lchild, e);else InsertBST(T -> rchild, e);/*********************** End **********************/
}
void Print(BSTree T)
{//中序输出以T为根的二叉排序树的所有结点/***********************Begin**********************/if(T){Print(T -> lchild);cout << T -> data << ' ';Print(T -> rchild);}/*********************** End **********************/	
}
void PrintAllx(BSTree T,int x)
{//在二叉排序树T中，查找值≥x的结点并输出/***********************Begin**********************/if(T == NULL) return;PrintAllx(T -> lchild, x);if(T -> data >= x) cout << T -> data << ' ';PrintAllx(T -> rchild, x);/*********************** End **********************/
}
int main()
{BSTree T=NULL;int n;cin>>n;for(int i=0;i>e;InsertBST(T,e);}Print(T);cout<>x;PrintAllx(T,x);
}

第3关：二叉排序树和查找（算法设计题4）

任务描述

本关任务：已知二叉排序树T的结点形式为(llink, data, count, rlink)，从空树开始，依次在树中查找n个结点元素，若存在，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

相关知识

二叉排序树（Binary Sort Tree）又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。 1．二叉排序树的定义二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）它的左、右子树也分别为二叉排序树。 二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成所要求任务。

测试说明

平台会对你编写的代码进行测试，以下为两个测试用例的例子。

测试输入（共2行：第1行是元素的个数n；第二行为空格分隔的n个元素):

6 1 3 4 2 5 3

预期输出(共2行：第1行为排序后的各元素；第2行为对应每个元素的计数)：

1 2 3 4 5 1 1 2 1 1

参考代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;using namespace std;
typedef long long LL;
typedef pair PII;typedef struct BiTNode
{int data;int count;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void SearchBST(BiTree &T,int X)
{/***********************Begin**********************/BiTNode *s = new BiTNode;s -> data = X, s -> count = 1, s -> lchild = s -> rchild = NULL;if(T == NULL) T = s;else{BiTNode *r = T, *p = NULL;while(r){if(r -> data == X) {r -> count ++; return;}else{p = r;if(r -> data > X) r = r -> lchild;else r = r -> rchild;}}if(p -> data > X) p -> lchild = s; else p -> rchild = s; }/*********************** End **********************/
}
void PrintData(BiTree T)
{//中序遍历输出二叉树T/***********************Begin**********************/if(T){PrintData(T -> lchild);cout << T -> data << ' ';PrintData(T -> rchild);}/*********************** End **********************/
}
void PrintCount(BiTree T)
{//中序遍历输出二叉树T计数/***********************Begin**********************/if(T){PrintCount(T -> lchild);cout << T -> count << ' ';PrintCount(T -> rchild);}/*********************** End **********************/
}
int main()
{int n;cin>>n;int e;        			//变量e用于接收输入数据BiTree T=NULL;for(int i=0;i>e;SearchBST(T,e);}PrintData(T);			//中序遍历输出二叉树T结点cout<

作者有言

如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：计算机基础知识（基础入门小白专属）八

下一篇：Vue3详细讲解

相关内容

热门资讯

安卓系统自带的网页,功能与特色... 你有没有发现，每次打开安卓手机，那熟悉的系统界面里总有一个默默无闻的小家伙——安卓系统自带的网页浏览...
美咖云系统安卓版,开启智能生活... 你有没有发现，最近手机上多了一个叫“美咖云系统安卓版”的小家伙？它就像一个魔法师，轻轻一点，就能让你...
安卓系统推荐最好的手机,盘点性... 你有没有想过，拥有一部性能卓越的手机，就像是拥有了移动的宝藏库？在这个信息爆炸的时代，一部好手机不仅...
安卓11系统能精简吗,释放潜能 你有没有发现，随着手机越来越智能，系统也越来越庞大？安卓11系统，这个最新的操作系统，是不是也让你觉...
安卓自动重启系统软件,揭秘原因... 手机突然自动重启，是不是感觉整个人都不好了？别急，今天就来和你聊聊这个让人头疼的安卓自动重启系统软件...
苹果手机x刷安卓系统,探索安卓... 你有没有想过，你的苹果手机X竟然也能刷上安卓系统？是的，你没听错，就是那个一直以来都和我们苹果手机X...
安卓系统智商低吗,智商低下的真... 你有没有想过，为什么安卓系统的智商总被调侃得好像有点低呢？是不是觉得它总是慢吞吞的，有时候还犯点小错...
安卓系统手机联系人,揭秘你的社... 你有没有发现，手机里的联系人列表就像是一个小小的社交圈呢？里面藏着我们的亲朋好友、工作伙伴，甚至还有...
安卓系统免费铃声下载,打造个性... 手机里那首老掉牙的铃声是不是让你觉得有点out了呢？别急，今天就来给你支个招，让你轻松给安卓手机换上...
安卓系统用哪个桌面好,打造个性... 你有没有发现，手机桌面可是我们每天都要面对的“脸面”呢？换一个好看的桌面，心情都能跟着好起来。那么，...
虚拟大师是安卓10系统,功能与... 你知道吗？最近在手机圈里，有个新玩意儿引起了不小的轰动，那就是虚拟大师！而且，更让人惊喜的是，这个虚...
安卓系统与苹果优缺点,系统优缺... 说到手机操作系统，安卓和苹果绝对是两大巨头，它们各有各的特色，就像两道不同的美味佳肴，让人难以抉择。...
安卓win双系统主板,融合与创... 你有没有想过，一台电脑如果既能流畅运行安卓系统，又能轻松驾驭Windows系统，那该有多爽啊？没错，...
安卓系统可精简软件,轻松提升手... 你有没有发现，手机里的安卓系统越来越庞大，软件也越装越多，有时候感觉手机就像个“大肚子”，不仅运行速...
安卓系统基于linux的代码,... 你有没有想过，那个陪伴你每天刷抖音、玩游戏、办公的安卓系统，其实背后有着一套复杂的基于Linux的代...
苹果和安卓的拍照系统,谁更胜一... 你有没有发现，现在手机拍照已经成为我们生活中不可或缺的一部分呢？无论是记录生活的点滴，还是捕捉美丽的...
苹果和安卓系统不同吗,系统差异... 你有没有想过，为什么你的手机里装的是苹果的iOS系统，而朋友的手机却是安卓系统呢？这两种系统，看似都...
安卓系统有多少级,揭秘其多级架... 你有没有想过，那个陪伴我们日常生活的安卓系统，它其实有着丰富的层级结构呢？没错，就是那个让我们的手机...
华为鸿蒙系统与安卓的,技术融合... 你知道吗？最近科技圈可是炸开了锅，华为鸿蒙系统与安卓的较量成为了大家热议的话题。这不，今天我就来给你...
什么安卓手机是苹果系统,搭载苹... 你有没有想过，为什么有些人宁愿花大价钱买苹果手机，而有些人却对安卓手机情有独钟呢？其实，这个问题背后...