查找：折半查找、平衡二叉树、散列表（习题-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详细讲解

相关内容

热门资讯

安卓手机系统怎么加速,安卓手机... 你有没有发现，你的安卓手机最近变得有点“慢吞吞”的？别急，别急，今天就来给你支几招，让你的安卓手机瞬...
小米note安卓7系统,探索性... 你有没有发现，手机更新换代的速度简直就像坐上了火箭呢？这不，小米Note这款手机，自从升级到了安卓7...
安卓和鸿蒙系统游戏,两大系统游... 你有没有发现，最近手机游戏界可是热闹非凡呢！安卓和鸿蒙系统两大巨头在游戏领域展开了一场激烈的较量。今...
安卓手机没有系统更,揭秘潜在风... 你有没有发现，现在安卓手机的品牌和型号真是五花八门，让人挑花了眼。不过，你知道吗？尽管市面上安卓手机...
充值宝带安卓系统,安卓系统下的... 你有没有发现，最近手机上的一款充值宝APP，在安卓系统上可是火得一塌糊涂呢！这不，今天就来给你好好扒...
安卓系统8.0镜像下载,轻松打... 你有没有想过，想要给你的安卓手机升级到最新的系统，却不知道从哪里下载那个神秘的安卓系统8.0镜像呢？...
安卓系统修改大全,全方位修改大... 你有没有想过，你的安卓手机其实是个大宝藏，里面藏着无数可以让你手机焕然一新的秘密？没错，今天就要来个...
安卓刷miui系统教程,安卓刷... 你有没有想过给你的安卓手机换换口味？别看它现在用得挺顺手的，偶尔来点新鲜感也是不错的。今天，就让我来...
超星学系统安卓版,便捷学习新体... 你有没有发现，学习生活越来越离不开电子设备了？手机、平板，这些小玩意儿简直就是我们的学习小助手。今天...
安卓平板6.0系统安装,轻松上... 你有没有想过，你的安卓平板6.0系统是不是该升级一下了呢？别看它现在看起来还挺精神的，但谁知道背后隐...
安卓系统屏幕显示文字,探索个性... 你有没有发现，手机屏幕上的文字有时候会变得模糊不清，或者颜色暗淡，让人看得很费劲？这可真是让人头疼的...
快递扫描系统下载安卓,便捷物流... 你有没有想过，每次快递员来送快递，他们是怎么快速找到你的包裹的呢？是不是觉得他们有超能力？其实，这背...
安卓系统能打开zip,操作指南... 你有没有想过，你的安卓手机里那些神秘的zip文件到底怎么打开呢？别急，今天就来给你揭秘这个小小的技术...
塞班怎么查找安卓系统,塞班系统... 你有没有想过，你的塞班手机里竟然也能装上安卓系统？听起来是不是有点神奇？别急，今天我就来手把手教你如...
安卓系统短消息提醒,安卓系统短... 你有没有发现，手机里的短消息提醒功能有时候就像一个贴心的管家，有时候又像个爱闹腾的小孩子？今天，咱们...
安卓系统如何跳过密码,安卓系统... 你是不是也和我一样，有时候手机锁屏密码设置得太复杂，每次解锁都要费好大一番力气？别急，今天就来教你怎...
鸿蒙系统功能与安卓,功能对比与... 你知道吗？最近手机圈里可是热闹非凡呢！华为的新操作系统鸿蒙系统（HarmonyOS）一经推出，就引发...
安卓系统卡苹果系统不卡,揭秘两... 你有没有发现，身边的朋友都在争论安卓系统和苹果系统哪个更好？其实，这个问题就像是在问谁家的孩子更聪明...
安卓系统卡解决了吗,安卓系统卡... 你有没有遇到过安卓手机卡顿的问题？是不是每次打开应用都感觉像蜗牛爬行？别急，今天就来聊聊这个让人头疼...
华为安卓系统下载软件,畅享海量... 你有没有想过，手机里的系统就像是我们的大脑，而下载的软件就像是大脑里的各种功能？今天，就让我带你一起...