搜索二叉树的建立

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 using namespace std;
 6 
 7 struct Nod
 8 {
 9     int num;
10     Nod *left;
11     Nod *right;
12     Nod()
13     {
14         num=0;
15         left=right=NULL;
16     }
17 };
18 
19 template <class TYPE>
20 Nod* buildBinarySortTree(TYPE *a,int i,int size,Nod *head,Nod * &h)
21 {
22     if(i>=size)
23     {
24         return head;
25     }
26     if(h==NULL)
27     {
28         h=new Nod;
29         h->num=a[i];
30         head=(head?head:h);
31         buildBinarySortTree(a,i+1,size,head,head);
32     }
33     else
34     {
35         if(a[i]>h->num)
36         {
37             buildBinarySortTree(a,i,size,head,h->right);
38         }
39         else
40         {
41             buildBinarySortTree(a,i,size,head,h->left);
42         }
43     }
44     return head;
45 }
46 
47 void displayBinarySortTree(Nod *head)
48 {
49     if(head)
50     {
51         displayBinarySortTree(head->left);
52         cout<<head->num;
53         displayBinarySortTree(head->right);
54     }
55 }
56 
57 void freeBinarySortTree(Nod *head)
58 {
59     if(head)
60     {
61         freeBinarySortTree(head->left);
62         freeBinarySortTree(head->right);
63         delete head;
64     }
65 }
66 
67 int main()
68 {
69     int n;
70     while(cin>>n&&n)
71     {
72         int i;
73         int *a=new int[n+1];
74         for(i=0;i<n;i++)
75         {
76             cin>>a[i];
77         }
78         Nod *head=NULL;
79         head=buildBinarySortTree(a,0,n,head,head);
80         displayBinarySortTree(head);
81         freeBinarySortTree(head);
82         delete a;
83     }
84     return 0;
85 }
86 
87 /*
88 5
89 4 7 3 2 1
90 */