欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

天梯赛:7-157 二叉搜索树的结构 (30分)(AC满分+解析+测试点)

程序员文章站 2022-06-08 12:07:39
...

7-157 二叉搜索树的结构 (30分)

天梯赛:7-157 二叉搜索树的结构 (30分)(AC满分+解析+测试点)
输入样例:

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例:

Yes
Yes
Yes
Yes
Yes
No
No
No

测试点:
下图参考博客:https://blog.csdn.net/Dream_Weave/article/details/82744830
天梯赛:7-157 二叉搜索树的结构 (30分)(AC满分+解析+测试点)

思路

1. 首先读者要知道什么是二叉搜索树,它是怎么构造的,特点等等。。。
2. 二叉搜索树构造好了,定义结构体point保存每个结点对应的父节点,深度。
使用map对输入的值标记,map<int,point>。(为什么不直接用数组下标呢?因为输入的数据可能很大,直接用数组下标标记内存会超)
3. 对输入的字符串进行处理,采用的是sscanf(很好用啦)。具体用法读者自行了解(当然有很多方法,读者自行选择)。
注意: (测试点2)当输入字符串中的结点不存在时,需要注意一下,此时应该输出No。解释: 会有一种情况,这两个结点都不存在时,可能它们的深度都是默认值0,然后就输出了Yes,其实应该输出No。(鄙人当时。。。就是这个错误找了半天QAQ。。。。)

样例:

输入:
5
2 4 1 3 0
2
10 and 20 are on the same level
2 and 10 are on the same level
输出:
No
No
#include<bits/stdc++.h>
using namespace std;
typedef struct TNode{
	int data;
	struct TNode *right;
	struct TNode *left;
} *BinTree;
BinTree bst=NULL;
struct point{
	int fa,d=-1;
};
map<int,point> p; //map标记输入的值,节省内存,不会段错误 

BinTree insert(BinTree &bst, int x, int fa, int dept){  //插入新结点,构造二叉搜索树 
	if(!bst){
		bst=(BinTree)malloc(sizeof(TNode));
		bst->data=x;
		bst->left = bst->right = NULL;
		if(fa!=-1){
			p[x].d=dept;  //深度 
			p[x].fa=fa;   //x的父节点 
		}
	}
	else{
		if(x < bst->data){  //x在左子树上 
			bst->left = insert(bst->left, x, bst->data, dept+1);
		}
		else if(x > bst->data){ //x在右子树上
 			bst->right = insert(bst->right, x, bst->data, dept+1);
		}
	}
	return bst;
}

int main(){
	int n,m,x,root;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>x;
		insert(bst, x, -1, 0); //构造二叉搜索树 
	}
	root=bst->data;  //根结点 
	p[root].fa=-1;
	p[root].d=0;
	cin>>m;
	getchar();
	while(m--){
		int x,y=-1,flag=0;
		string s;
		getline(cin,s);
		if(s.find("root")!=string::npos){  //判断是否为根 
			sscanf(s.c_str(),"%d is the root",&x);
			if(root==x) flag=1;
		}
		else if(s.find("siblings")!=string::npos){ //判断是否为兄弟 
			sscanf(s.c_str(),"%d and %d are siblings",&x,&y);
			if(p[x].fa == p[y].fa)flag=1;	
		}
		else if(s.find("parent")!=string::npos){ //判断x是否为y的父节点 
			sscanf(s.c_str(),"%d is the parent of %d",&x,&y);	
			if(p[y].fa == x)flag=1;
		}
		else if(s.find("left")!=string::npos){ //判断y是否为x的左孩子 
			sscanf(s.c_str(),"%d is the left child of %d",&x,&y);	
			if(p[x].fa==y&&x<y)flag=1;
		}
		else if(s.find("right")!=string::npos){ //判断y是否为x的右孩子
			sscanf(s.c_str(),"%d is the right child of %d",&x,&y);	
			if(p[x].fa==y&&x>y)flag=1;
		}else if(s.find("same")!=string::npos){  //是否在同一层 
			sscanf(s.c_str(),"%d and %d are on the same level",&x,&y);	
			if(p[x].d==p[y].d)flag=1;
		}
		if(p[x].d==-1||p[y].d==-1&&y!=-1)flag=0;//判断输入的结点是否存在,不存在输出No 
		if(flag) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

代码中:sting中find()函数和string::npos(解析)
https://blog.csdn.net/weixin_43581819/article/details/104187948

欢迎大家批评改正 !!!