BST的INSERT、FIND、遍历

https://blog.csdn.net/Charles_Zaqdt/article/details/89810087

        嗯...就是贴个板子

#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 ;
}

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{
			p_inorder(root);
			puts("");
			p_preorder(root);
			puts("");
		}
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券