浙大版《数据结构学习与实验指导(第2版)》进阶实验8-2.3:二叉搜索树的最近公共祖先

简介: 浙大版《数据结构学习与实验指导(第2版)》进阶实验8-2.3:二叉搜索树的最近公共祖先

题意

给定一棵二叉搜索树的先序遍历序列,要求你找出任意两结点的最近公共祖先结点(简称 LCA)。


Input

输入的第一行给出两个正整数:待查询的结点对数 M(≤ 1000)和二叉搜索树中结点个数 N(≤ 10000)。随后一行给出 N  个不同的整数,为二叉搜索树的先序遍历序列。最后 M行,每行给出一对整数键值 U和 V。所有键值都在整型int范围内。


Output

对每一对给定的 U和 V,如果找到 A 是它们的最近公共祖先结点的键值,则在一行中输出 LCA of U and V is A.。但如果 U和 V中的一个结点是另一个结点的祖先,则在一行中输出 X is an ancestor of Y.,其中 X 是那个祖先结点的键值,Y 是另一个键值。如果 二叉搜索树中找不到以 U或 V为键值的结点,则输出 ERROR: U is not found. 或者 ERROR: V is not found.,或者 ERROR: U and V are not found。

思路

难点在于建树

二叉搜索树性质:左儿子的值<根节点的值<右儿子的值,所以中序遍历是递增的序列。

题目给出了先序遍历,那么从小到大排序后就是中序遍历,建树的过程位根据先序遍历和中序遍历建立二叉树。

递归建树后,根据二叉搜索树的性质递归查找lca的值。如果x,y都大于当前节点的值,说明x,y都在当前节点的右子树;如果x,y都小于当前节点的值,说明x,y都在当前节点的左子树;否则,说明x,y分列在当前节点的左、右子树,那么当前节点就是lca。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+100;
#define debug(x) cout<<#x<<":"<<x<<endl;
struct node{
    int val;
    node *l;
    node *r;
};
node tr[maxn];
int a[maxn],b[maxn],idx;
map<int,int>mp;
node* build(int len,int u,int st){
    if(len<1) return 0;
    node* now=&tr[idx++];///根节点
    now->val=a[u];
    int t=0;
    t=lower_bound(b+t+st,b+len+st,a[u])-b-st;///找到根节点
   /// debug(t);
    now->l=build(t,u+1,st);
    now->r=build(len-t-1,u+t+1,st+t+1);
    return now;
}
int lca(int x,int y,node* root){
    if(x>root->val&&y>root->val)
        return lca(x,y,root->r);
    else if(x<root->val&&y<root->val)
        return lca(x,y,root->l);
    else return root->val;
}
int main()
{
    int m,n;cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ///debug(a[i]);
        b[i]=a[i];
        mp[b[i]]=1;///标记出现过
    }
    sort(b,b+n);///中序遍历
    node* root=build(n,0,0);
    while(m--){
        int x,y;
        cin>>x>>y;
        if(!mp.count(x)&&!mp.count(y)) printf("ERROR: %d and %d are not found.\n",x,y);
        else if(!mp.count(x)&&mp.count(y)) printf("ERROR: %d is not found.\n",x);
        else if(mp.count(x)&&!mp.count(y)) printf("ERROR: %d is not found.\n",y);
        else{
            int par=lca(x,y,root);
            if(par==x){
                printf("%d is an ancestor of %d.\n",x,y);
            }
            else if(par==y){
                printf("%d is an ancestor of %d.\n",y,x);
            }
            else{
                printf("LCA of %d and %d is %d.\n",x,y,par);
            }
        }
    }
    return 0;
}
目录
相关文章
|
2月前
|
存储 算法 编译器
数据结构实验之矩阵的运算器(二维数组)
本实验旨在通过团队合作,掌握数组和矩阵相关运算的代码实现,包括矩阵的加减、数乘、转置、乘法、n次方及行列式的计算。实验过程中,成员们需分工协作,解决编程难题,最终实现一个功能完备的矩阵计算器。通过本实验,不仅锻炼了编程能力,还加深了对数学概念的理解,同时培养了团队合作精神。
76 4
|
2月前
数据结构实验之串模式匹配问题
本实验旨在掌握串模式匹配技术,通过创建文本文件、实现单词计数与定位功能,最终构建一个包含文件建立、单词统计与定位、程序退出等选项的主菜单,以增强对字符串处理的理解与应用能力。
71 4
|
2月前
|
算法
数据结构实验之最长公共子序列
本实验旨在通过编程实践帮助学生理解串的基本概念及求解最长公共子序列的算法。实验内容包括使用动态规划方法设计并实现算法,以找出给定两序列的最大公共子序列。示例代码展示了如何通过构建状态矩阵和回溯路径来找到解决方案。实验总结指出,`memset()`函数用于内存初始化,且对于特定输入,程序能正确输出最长公共子序列之一。
66 4
|
2月前
|
算法
数据结构实验之操作系统打印机管理器问题
本实验旨在通过实现操作系统中的打印机管理器问题,掌握队列的基本操作如入队、出队等,利用队列的先进先出特性解决先申请先打印的问题。实验包括队列的初始化、入队、出队、打印队列内容等功能,并通过菜单式界面进行交互。实验结果显示基本功能可正常执行,但在连续操作时存在执行失败的情况,需进一步优化。
57 4
|
2月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
73 4
|
2月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
117 4
|
2月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
72 4
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

热门文章

最新文章