二叉搜索树Ⅲ【东北大学oj数据结构8-3】C++

二叉搜索树 III
B：在二叉搜索树II中加入delete指令，创建程序对二叉搜索树T执行如下指令。

插入 k：将key k 插入到 T 中。
find k：报告T中是否存在key k。
delete k：删除key为 k 的节点。
打印：使用中序树遍历和先序树遍历算法打印key值。
删除 k，删除二叉搜索树 T 给定的键为 k 的节点 z，更新父子链接（指针），同时根据考虑以下三种情况的算法保持二叉搜索树条件：

如果 z 没有孩子，则删除 z 的父母 p 的孩子（即 z）。
如果 z 只有一个孩子，将 z 的父节点的子节点更改为 z 的子节点，将 z 的子节点的父节点更改为 z 的父节点，然后从树中删除 z。
如果 z 有两个孩子，则将 z 的下一个节点 y 的key复制到 z 的key并删除 y。这里z的下一个节点是中间前向巡逻中z之后得到的节点。

输入
输入的第一行给出了指令数 m。在下一个 m 行，以插入 k、查找 k、删除 k 或打印的形式在一行上给出指令。

输出
对于每个 find k 指令，如果 T 包含 k 则输出 yes，如果 T 不包含则输出 no。
进一步，对于每条打印指令，将中序遍历算法和先序遍历算法得到的key的排列输出到一行。在每个key之前打印一个空格。

约束
指令数不超过50万条。
打印指令数量不超过10条。
−2,000,000,000 ≤ key ≤ 2,000,000,000
如果按照上面的伪代码算法，树的高度不会超过100。
二叉搜索树中的键没有重复。

数据结构

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print

输出样例

yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22 

#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;// 定义树的节点结构
struct Node {int key;Node* right;Node* left;Node* p;
};Node* creat(int a)
{Node* n=new Node();n->key=a;n->left=nullptr;n->right=nullptr;n->p=nullptr;return n;
}Node* insertt(Node* root,Node* z)
{Node* y=nullptr;Node* x=root;while(x!=nullptr){y=x;if(z->key<x->key)x=x->left;elsex=x->right;}z->p=y;if(y==nullptr)root=z;else if(z->key<y->key)y->left=z;elsey->right=z;return root;
}Node* findd(Node* root,int k)
{while(root!=nullptr&&k!=root->key){if(k<root->key)root=root->left;elseroot=root->right;}return root;
}Node* deletee(Node* root,Node* z)
{if(z->left==nullptr&&z->right==nullptr){if(z->p==nullptr){delete z;return nullptr;}if(z->p->left==z)z->p->left=nullptr;elsez->p->right=nullptr;delete z;}else if(z->left==nullptr||z->right==nullptr){Node* child=(z->left!=nullptr)?z->left:z->right;if(z->p==nullptr){delete z;return child;}if(z->p->left==z)z->p->left=child;elsez->p->right=child;child->p=z->p;delete z;}else{Node* y=z->right;while(y->left!=nullptr){y=y->left;}z->key=y->key;root=deletee(root,y);}return root;
}void preorder(Node* a)
{if(a==nullptr) return;cout<<a->key<<" ";preorder(a->left);preorder(a->right);
}
void inorder(Node* a)
{if(a==nullptr) return;inorder(a->left);cout<<a->key<<" ";inorder(a->right);
}int main() {int n;Node* tree=nullptr;cin>>n;for (int i = 0; i < n; i++) {string c;cin>>c;if(c=="insert"){int v;cin>>v;Node* newNode=creat(v);tree=insertt(tree,newNode);}if(c=="find"){int v;cin>>v;Node* a=findd(tree,v);if(a)cout<<"yes"<<endl;elsecout<<"no"<<endl;}if(c=="delete"){int v;cin>>v;Node* a=findd(tree,v);if(a)tree=deletee(tree,a);}if(c=="print"){inorder(tree);cout<<endl;preorder(tree);cout<<endl;}}return 0;
}