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

编写一个程序，通过将查找操作添加到二叉搜索树 T 对二叉搜索树 T 执行以下操作：二叉搜索树 I。

插入k：将一个包含k的节点插入到T中。
find k：报告T是否有包含k的节点。
打印：分别通过中序树遍历和先序树遍历打印二叉搜索树的键。

输入
在第一行中，给出了操作数 m。在接下来的 m 行中，给出了由 insert k、find k 或 print 表示的操作。

输出
对于每个 find k 操作，如果 T 有一个包含 k 的节点，则打印“yes”，否则打印“no”。

另外，对于每个打印操作，分别打印一行中序树遍历和先序树遍历得到的key列表。在每个键之前放置一个空格字符。

约束

1≤ 操作次数≤500,000

1≤打印操作次数 ≤10

−2,000,000,000≤key≤2,000,000,000

如果使用上述伪代码，二叉树的高度不会超过 100。
二叉搜索树中的键都是不同的。

输入样例

10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print

输出样例

yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

#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;
        else
            x=x->right;
    }
    z->p=y;
    if(y==nullptr)
        root=z;
    else if(z->key<y->key)
        y->left=z;
    else
        y->right=z;
 
    return root;
}
 
void findd(Node* root,int k)
{
    while(root!=nullptr&&k!=root->key)
    {
        if(k<root->key)
            root=root->left;
        else
            root=root->right;
    }
    if(root)
        cout<<"yes"<<endl;
    else
        cout<<"no"<<endl;
}
 
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;
            findd(tree,v);
        }
        if(c=="print")
        {
            inorder(tree);
            cout<<endl;
            preorder(tree);
            cout<<endl;
        }
    }
    return 0;
}