二叉排序树的实现和查找 swustoj

二叉排序树的实现和查找  1000(ms)  10000(kb)  2257 / 5150 按照给定的关键字集合，建立二叉排序树。在建立的二叉排序树上查找指定的关键字，查找成功，输出找到该关键字比较的次数；查找不成功，输出-1.

输入

关键字个数n； 关键字集合； 要查找的关键字；

输出

查找成功输出比较的次数，否则输出-1。

样例输入

12 25 18 46 2 53 39 32 4 74 67 60 11 74

样例输出

4

提示：二叉排序树根结点大于左结点，小于右结点，这样创建一颗树就好了

        

#include<iostream>

#include<stdlib.h> using namespace std; typedef struct node { int data; struct node *l,*r; }Tree; int flag=0,obj=0;//flag作用判断是否寻找到，obj计算比较次数。 void creat(Tree *&l,int num)//创建二叉搜索树。 { if(l==NULL) { l=(Tree *)malloc(sizeof(Tree)); l->data=num; l->l=l->r=NULL; return ; } if(l->data<num)  creat(l->l,num); else creat(l->r,num); } void fun(Tree *&l,int num) { obj++;//每比较一次计数＋1. if(l==NULL) return ; else if(l->data<num) fun(l->l,num); else if(l->data>num) fun(l->r,num); else if(l->data==num) { flag=1; return ; } } int main() { Tree *l; l=(Tree *)malloc(sizeof(Tree)); int n,m; cin>>n; cin>>m; l->data=m; l->l=l->r=NULL; for(int i=1;i<n;i++) { cin>>m; creat(l,m); } cin>>m; fun(l,m); if(flag) cout<<obj; else cout<<"-1"; return 0; }