二叉排序树

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 using namespace std;
 5 
 6 typedef struct Node {
 7     int data;
 8     int num;
 9     struct Node *l, *r;
10 } Node, *BSTree;
11 
12 int count;
13 
14 // 二叉排序树 
15 void InsertBST(BSTree &T, int data)
16 {
17     if (!T) {
18         T = (BSTree)malloc(sizeof(Node));
19         if (!T) exit(1);
20         T->data = data;
21         T->num = 1;
22         T->l = T->r = NULL;
23         return;    
24     }
25     
26     if (data < T->data) {
27         InsertBST(T->l, data);
28     } else if (data > T->data) {
29         InsertBST(T->r, data);
30     } else {
31         T->num++; return;
32     }
33 }
34 
35 void Visit(BSTree T) 
36 {
37     for (int i = 0; i < T->num; i++) {
38         if (count > 1) cout << T->data << " ";
39         else cout << T->data << endl;
40     }
41     ++count;
42 }
43 void TraverseBST(BSTree T, void(*Visit)(BSTree)) 
44 {
45     if (!T) return;
46     TraverseBST(T->l, Visit);
47     Visit(T);
48     TraverseBST(T->r, Visit);
49 }
50 
51 
52 int main() 
53 {
54     int n, data;
55     BSTree T = NULL;
56     
57     cin >> n;
58     for (int i = 0; i < n; i++) {
59         cin >> data;
60         InsertBST(T, data);
61     }
62     
63     count = n;
64     TraverseBST(T, Visit);
65     
66     return 0;
67 }