保研机试备考七:二叉搜索树与表达式树
AcWing 3786. 二叉排序树
题目
https://www.acwing.com/problem/content/3789/
思路
对于插入而言:
根据二叉排序树,左儿子<根节点<右儿子的性质,找到插入的点该插入的位置插入即可,该位置一定是个叶结点的位置,即查找时碰到空值。
对于删除而言:
先找到要删除的节点的位置
+ 如果要删除的点是叶结点,直接删除;
+ 如果要删除的点有一个分支,那么把这个点删了,分支上移;
+ 如果要删除的点有左右儿子,这时需要找到其左子树的最右边的节点,用该节点的值替代要删除节点的值(因为该节点的值是左子树里最大的,且是左子树里最接近要删除的节点的),再把这个位置的节点删掉。
对于查找而言:
如果是要找到前驱节点
+ 如果当前节点为空
返回-INF(表示没有点了,又不能左右答案,因为取最大值,所以用一个最小的值来)
+ 当前val大于x
到其左子树里面去找
+ 当前val<=x
val与其递归查找右子树取最大值
如果是要找到后继节点
+ 如果当前节点为空
返回INF(表示没有点了,又不能左右答案,因为取最小值,所以用一个最大的值来)
+ 当前val<=x
递归到右子树里面取找
+ 当前val>x
val与其递归查找左子树取最小值
代码
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
//结构体的定义尤其要注意
struct TreeNode
{
int val;
TreeNode *left,*right; //左右儿子
TreeNode(int x):val(x),left(NULL),right(NULL){} //构造函数
}*root; //定义根节点指针
void insert(TreeNode* &root,int x)
{
if(!root) root=new TreeNode(x); //如果是空,说明查找到了合适的位置,插入,需要先新建节点
else if(root->val>x) insert(root->left,x); //递归到左子树
else if(root->val<x) insert(root->right,x); //递归到右子树
}
void remove(TreeNode* &root,int x) //删除
{
if(root->val>x) remove(root->left,x);
else if(root->val<x) remove(root->right,x);
else
{
if(!root->left&&!root->right) root=NULL;
else if(!root->left) root=root->right;
else if(!root->right) root=root->left;
else
{
auto p=root->left;
while(p->right) p=p->right;
root->val=p->val;
remove(root->left,p->val);
}
}
}
int get_pre(TreeNode* root,int x)
{
if(!root) return -INF;
if(root->val>=x) return get_pre(root->left,x);
else return max(root->val,get_pre(root->right,x));
}
int get_suc(TreeNode* root,int x)
{
if(!root) return INF;
if(root->val<=x) return get_suc(root->right,x);
else return min(root->val,get_suc(root->left,x));
}
int main()
{
int n,opt,x;
cin>>n;
while(n--)
{
cin>>opt>>x;
if(opt==1) insert(root,x);
else if(opt==2) remove(root,x);
else if(opt==3) cout<<get_pre(root,x)<<endl;
else if(opt==4) cout<<get_suc(root,x)<<endl;
}
return 0;
}
TreeNode &root:加”&” 表示会改变树
TreeNode root:不加”&” 表示不会改变树,仅仅是查找访问
AcWing 3765. 表达式树
题目
https://www.acwing.com/problem/content/3768/
思路
写一个中序遍历即可,具体思路见代码
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* string val;
* TreeNode *left;
* TreeNode *right;
* };
*/
class Solution {
public:
string dfs(TreeNode* root)
{
if(!root) return ""; //如果当前节点为空,返回空串
if(!root->left&&!root->right) return root->val;//如果左右子树为空,就返回中间节点
else
return "("+dfs(root->left)+root->val+dfs(root->right)+")"; //要加括号表示优先级 中序遍历,左中右
}
string expressionTree(TreeNode* root) {
return dfs(root->left)+root->val+dfs(root->right);
} //为什么外层要套一个?因为最外层是不需要括号的,内层才需要括号,最外层放一个是为了防止最外层有括号
};