#include<iostream>

 using namespace std;

 class BinNode {

 private:

     int element;

     BinNode *leftChild;

     BinNode *rightChild;

 public:

         BinNode(int a, BinNode* left, BinNode* right) {

         element = a;

         leftChild = left;

         rightChild = right;

     }

     int val() { return element; }

     BinNode* left() { return leftChild; }

     void setLeft(BinNode *t) {  leftChild=t; }

     BinNode* right() { return rightChild; }

     void setRight(BinNode *t) { rightChild = t; }

 };

 class BST{

 private:

     BinNode *root;

      BinNode* insertHelp(int x, BinNode* root) {

          BinNode* t = root;

          if (t == NULL) { t = new BinNode(x, NULL, NULL); return t; }

         else if (x < t->val())

             t->setLeft(insertHelp(x, t->left()));

         else if (x > t->val())

             t->setRight(insertHelp(x, t->right()));

         return t;

     }

     void findHelp(const int x, int &count, BinNode* root) {

         count++;

         if (root == NULL) { count = ;return; }

         else if (root->val() == x)  return;

         if(x<root->val())

             findHelp(x, count, root->left());

         if(x>=root->val())

         findHelp(x, count, root->right());

     }

 public:

     BST() {    root = NULL;}

     ~BST() { clear(root);}

     void clear(BinNode *root) {

         if (root != NULL) {

             clear(root->left());

             clear(root->right());

             delete root;

         }

     }

     void insert(int& x) {

         root=insertHelp(x, root);

     }

     void find(const int x, int &count) {

         findHelp(x, count, root);

     }

 };

 int main() {

     BST a;

     int n;

     cout << "请输入节点个数：" << endl;

     cin >> n;

     cout << "依次输入节点值："<<endl;

     for (int i = ;i < n;i++) {

         int x;cin >> x;

         a.insert(x);

     }

     int num;

     while ((cout << "请输入需要查找的值：（ctrl+z结束查找）" << endl)&&(cin>>num)&&num!=EOF){

         int count=;

         a.find(num, count);

         if (count == )

             cout << "查找失败！" << endl;

         else

             cout << "查找成功！查找次数为：" << count << endl;

     }

     system("pause");

     return ;

 }