[HDOJ1106]排序

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1106
二叉树排序输出，测试此数据结构用......
  1 #include <cstdio>
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 #ifndef _KIRAI_BST
  7 #define _KIRAI_BST
  8 
  9 namespace kirai {
 10     template<class type>
 11     struct bstnode {
 12         typedef bstnode<type>* np;
 13         type _data;
 14         np left;
 15         np right;
 16         bstnode<type>() { left = NULL; right = NULL; }
 17         bstnode<type>(const int& x) : _data(x) { bstnode<type>(); }
 18     };
 19 
 20     template<class type>
 21     class bst {
 22         typedef bstnode<type>* np;
 23         typedef bstnode<type> nt;
 24 
 25     public:
 26         bst() { _root = NULL; }
 27         // ~bst();
 28         bool empty() const { return _root == NULL; }
 29         void insert(const type&);
 30         bool remove(const type&);
 31         bool query(const type&) const;
 32         bool change(const type&);
 33 
 34     public:
 35         void preorder(void(*visit)(type)) { _preorder(_root, visit); };
 36         void inorder(void(*visit)(type)) { _inorder(_root, visit); };
 37         void postorder(void(*visit)(type)) { _postorder(_root, visit); };
 38 
 39     protected:
 40         void _insert(np, const type&);
 41         void _inorder(np, void(*)(type));
 42         void _postorder(np, void(*)(type));
 43         void _preorder(np, void(*)(type));
 44     private:
 45         np _root;
 46     };
 47     
 48     template <class type>
 49     void bst<type>::insert(const type& x) {
 50         if (empty()) {
 51             np tmp = new nt;
 52             _root = tmp;
 53             _root->_data = x;
 54             return;
 55         }
 56         _insert(_root, x);
 57         return;
 58     }
 59 
 60     // x () than _data, then put x into (). : larger:right, smaller:left
 61     template <class type>
 62     void bst<type>::_insert(np cur, const type& x) {
 63         if (x >= cur->_data) {
 64             if (cur->right == NULL) {
 65                 np tmp = new nt;
 66                 cur->right = tmp;
 67                 tmp->_data = x;
 68                 return;
 69             }
 70             else {
 71                 _insert(cur->right, x);
 72             }
 73         }
 74         else {
 75             if (cur->left == NULL) {
 76                 np tmp = new nt;
 77                 cur->left = tmp;
 78                 tmp->_data = x;
 79                 return;
 80             }
 81             else {
 82                 _insert(cur->left, x);
 83             }
 84         }
 85     }
 86     template <class type>
 87     void bst<type>::_preorder(np cur, void(*visit)(type data)) {
 88         if (cur != NULL) {
 89             (*visit)(cur->_data);
 90             _preorder(cur->left, visit);
 91             _preorder(cur->right, visit);
 92         }
 93     }
 94 
 95     template <class type>
 96     void bst<type>::_inorder(np cur, void(*visit)(type data)) {
 97         if (cur != NULL) {
 98             _inorder(cur->left, visit);
 99             (*visit)(cur->_data);
100             _inorder(cur->right, visit);
101         }
102     }
103 
104     template <class type>
105     void bst<type>::_postorder(np cur, void(*visit)(type data)) {
106         if (cur != NULL) {
107             _postorder(cur->left, visit);
108             _postorder(cur->right, visit);
109             (*visit)(cur->_data);
110         }
111     }
112 }
113 
114 #endif
115 
116 char bf[1001];
117 char *pt, *five = "5";
118 int num[1000];
119 int n, cnt;
120 
121 void convert(int x) {
122     num[cnt++] = x;
123 }
124 
125 int main() {
126     while(~scanf("%s", bf)) {
127         // freopen("in", "r", stdin);
128         char* tmp;
129         kirai::bst<int> accepted;
130         pt = bf;
131         n = 0;
132         pt = strtok(bf, five);
133         while(pt != NULL) {
134             tmp = pt;
135             pt = strtok(NULL, five);
136             num[n] = atoi(tmp);
137             n++;
138         }
139         for(int i = 0; i < n; i++) {
140             accepted.insert(num[i]);
141         }
142         cnt = 0;
143         accepted.inorder(convert);
144         printf("%d", num[0]);
145         for(int i = 1; i < cnt; i++) {
146             printf(" %d", num[i]);
147         }
148         printf("
");
149     }
150 }