BST的INSERT、FIND、DELETE、遍历

 

        嗯...就是贴个板子

 

#include <bits/stdc++.h>
using namespace std;
struct node{
	int num;
	node *p, *l, *r;
};
node *root, *null;
int n, xx;
string str;

void p_inorder(node *x){     // 中序遍历
	if(x == null) return ;
	p_inorder(x -> l);
	printf(" %d", x -> num);
	p_inorder(x -> r);
	return ;
}

void p_preorder(node *x){    // 前序遍历
	if(x == null) return ;
	printf(" %d", x -> num);
	p_preorder(x -> l);
	p_preorder(x -> r);
	return ;
}

bool find(int a){           // 查询
	node *x = root;
	while(x != null){
		if(x -> num == a) return true;
		if(a > x -> num) x = x -> r;
		else x = x -> l;
	}
	return false;
}

void insert(int a){          // 插入
	node *x = root, *y = null;
	node *z = new node();
	z -> num = a;
	z -> l = null; z -> r = null;
	while(x != null){
		y = x;
		if(z -> num < x -> num) x = x -> l;
		else x = x -> r;
	}
	z -> p = y;
	if(y == null) root = z;
	else{
		if(z -> num < y -> num) y -> l = z;
		else y -> r = z;
	}
	return ;
}

void del(int x){
  node *p = root , *par;
  while(p -> num != x){
    if(p -> num > x){
      par = p;
      p = p -> l;
    }
    else{
      par = p;
      p = p -> r;
    }
  }
  if(p -> l == null && p -> r == null){
    if(par -> l == p) par -> l = null;
    else if(par -> r == p) par -> r = null;
    delete p;
    return ;
  }
  if(p -> l != null && p -> r == null){
    if(p == root) root = p -> l;
    else if(par -> l == p) par -> l = p -> l;
    else if(par -> r == p) par -> r = p -> l;
    delete p;
    return ;
  }
  else if(p -> l == null && p -> r != null){
    if(p == root) root = p -> r;
    else if(par -> l == p) par -> l = p -> r;
    else if(par -> r == p) par -> r = p -> r;
    delete p;
    return ;
  }
  else if(p -> l != null && p -> r != null){
    node *left = p -> r;
    par = p;
    while(left -> l){
      par = left;
      left = left -> l;
    }
    p -> num = left -> num;
    if(par -> l == left) par -> l = left -> r;
    else if(par -> r == left) par -> r = left -> r;
    delete left;
    return ;
  }
}

int main()
{
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		cin>>str;
		if(str == "insert"){
			scanf("%d", &xx);
			insert(xx);
		}
		else if(str == "find"){
			scanf("%d", &xx);
			if(find(xx)) puts("yes");
			else puts("no");
		}
    else if(str == "delete"){
      scanf("%d", &xx);
      del(xx);
    }
		else{
			p_inorder(root);
			puts("");
			p_preorder(root);
			puts("");
		}
	}
	return 0;
}

 

全部评论

相关推荐

想按时下班的大菠萝在...:隔壁学校的,加油多投, 实在不好找可以下个学期开学找,把算法八股准备好,项目有空再换换
投了多少份简历才上岸
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务