swust oj 1011

二叉排序树的实现和查找

1000(ms)

10000(kb)

2782 / 6301

按照给定的关键字集合，建立二叉排序树。在建立的二叉排序树上查找指定的关键字，查找成功，输出找到该关键字比较的次数；查找不成功，输出-1.

输入

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

输出

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

样例输入

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

样例输出

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 typedef int Datetype;
 7 using namespace std;
 8 int x;
 9 
10 typedef struct link{
11     Datetype date;
12     struct link *lchild;
13     struct link *rchild;
14 }tree;
15 
16 void creat(tree *&L, int arr[] ,int l,int r)
17 {
18     if(l>r)
19     {
20         L=NULL;
21         return ;
22     }
23     int s=(l+r)>>1;
24     L=new tree;
25     L->date=arr[s];
26     creat(L->lchild,arr,l,s-1);
27     creat(L->rchild,arr,s+1,r);
28 }
29 
30 void display(tree *&L)
31 {
32     if(L!=NULL)
33     {
34         cout<<L->date<<" ";
35         display(L->lchild);
36         display(L->rchild);
37     }
38 }
39 
40 void delet(tree *&L)
41 {
42     if(L!=NULL)
43     {
44         delet(L->lchild);
45         delet(L->rchild);
46         delete(L);
47     }
48 }
49 
50 void find(tree *&L, int a)
51 {
52     if(L!=NULL)
53     {
54         x++;
55         if(a>L->date)
56             find(L->rchild,a);
57         else if(a<L->date)
58             find(L->lchild,a);
59         else
60             return ;
61     }
62     if(L==NULL)
63         x=0;
64 }
65 
66 int main()
67 {
68     int arr[100];
69     int n,a;
70     tree *L;
71     cin>>n;
72     for(int i=0;i<n;i++)
73     {
74         cin>>arr[i];
75     }
76     sort(arr,arr+n);
77     cin>>a;
78     creat(L,arr,0,n-1);
79 //    display(L);
80     find(L,a);
81     if(x)
82         cout<<x;
83     else
84         cout<<"-1";
85     delet(L);
86     return 0;
87 }