深圳 XP03A 笔记 day03
2026-07-28 10:19:12
发布于：广东
23阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
//引用传递
void get(int &a,int &b){
int t = a;
a = b;
b = t;
}
//值传递
void get(int a,int b){
int t = a;
a = b;
b = t;
}
int main(){
int a = 5,b = 3;
get(a,b);
cout<<a<<" "<<b;
// 位运算 2进制运算
// 1. & 与 特点 全1才是1 有0就是0
// 2. | 或 特点 全0才是0 有1就是1
// 3. ^ 异或 特点 相同为0 不同为1
// 4. >>右移 特点 /2 整除
// 5. <<左移 特点 *2
// 6. ~非 特点 取反
// 1. & 取地址符号
// 2. * 解地址符号
//int a = 10;
// cout<< &a<<endl ;
// long long b[10];
// cout<< &b <<endl;
// cout<< &b[1] <<endl;
// cout<< &b[2] <<endl;
//int* p = &a; // 指向int类型变量 指针
///cout<<*p;
return 0;
}
二叉搜索树
#include<bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
Node(int x){
val=x;
left=NULL;
right=NULL;
}
};
// 插入节点
Node* insertNode(Node* root,int x){
// 找到空位置，创建新节点
if(root==NULL){
return new Node(x);
}
if(x<root->val){
root->left=insertNode(root->left,x);
}else if(x>root->val){
root->right=insertNode(root->right,x);
}
// x==root->val 时不重复插入
return root;
}
// 查找节点
bool findNode(Node* root,int x){
if(root==NULL){
return false;
}
if(root->val==x){
return true;
}
if(x<root->val){
return findNode(root->left,x);
}else{
return findNode(root->right,x);
}
}
// 找到一棵树中的最小值节点
Node* getMin(Node* root){
while(root->left!=NULL){
root=root->left;
}
return root;
}
// 删除节点
Node* deleteNode(Node* root,int x){
if(root==NULL){
return NULL;
}
if(x<root->val){
root->left=deleteNode(root->left,x);
}else if(x>root->val){
root->right=deleteNode(root->right,x);
}else{
// 找到了要删除的节点
// 情况1：没有左孩子
if(root->left==NULL){
Node* t=root->right;
delete root;
return t;
}
// 情况2：没有右孩子
if(root->right==NULL){
Node* t=root->left;
delete root;
return t;
}
// 情况3：左右孩子都有
// 找右子树中的最小节点
Node* t=getMin(root->right);
// 用后继节点的值替换当前节点
root->val=t->val;
// 删除右子树中重复的后继节点
root->right=deleteNode(root->right,t->val);
}
return root;
}
// 前序遍历：根、左、右
void preorder(Node* root){
if(root==NULL){
return;
}
cout<<root->val<<" ";
preorder(root->left);
preorder(root->right);
}
// 中序遍历：左、根、右
void inorder(Node* root){
if(root==NULL){
return;
}
inorder(root->left);
cout<<root->val<<" ";
inorder(root->right);
}
// 后序遍历：左、右、根
void postorder(Node* root){
if(root==NULL){
return;
}
postorder(root->left);
postorder(root->right);
cout<<root->val<<" ";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Node* root=NULL;
int q;
cin>>q;
while(q--){
int op,x;
cin>>op>>x;
if(op==1){
// 插入x
root=insertNode(root,x);
}else if(op==2){
// 查询x
if(findNode(root,x)){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}else if(op==3){
// 删除x
root=deleteNode(root,x);
}else if(op==4){
// 中序遍历
inorder(root);
cout<<"\n";
}
}
return 0;
}
这里空空如也
有帮助，赞一个