POJ 2418 Hardwood Species

这题，我起先用的是AVL树，结果时间超时，最后发现，直接用二叉树就行了，根本就不需要旋转。由于数据是随机的，因而这棵二叉树的性能还行。当然还可以用trie树来解决。
题目很简单，直接上代码
  1 #include <iostream>
  2 #include <stack>
  3 #include <string.h>
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 using namespace std;
  7 
  8 class Node
  9 {
 10 public:
 11        char* data;
 12        Node* left;
 13        Node* right;
 14        int balance;
 15        int count;
 16        Node()
 17        {
 18                data = NULL;
 19                left = right = NULL;
 20                balance = count = 0;
 21        }
 22        Node(char* s)
 23        {
 24                data = new char[30];
 25            strcpy(data, s);
 26                left = NULL;
 27                right = NULL;
 28                balance = 0;
 29                count = 1;
 30        }
 31 };
 32 
 33 
 34 class AVLTree
 35 {
 36 private:
 37        Node* root;
 38 
 39 public:
 40        int vertexNumber;
 41        AVLTree()
 42        {
 43                root = NULL;
 44                vertexNumber = 0;
 45        }
 46 
 47 
 48        AVLTree(Node* r)
 49        {
 50                root = r;
 51                vertexNumber = 0;
 52        }
 53        int depth(Node* node)
 54        {
 55                if(node == NULL)
 56                        return -1;
 57                int l = depth(node->left);
 58                int r = depth(node->right);
 59 
 60                return (l < r)?(r+1):(l+1);
 61        }
 62 
 63        void insert(char* str)
 64        {
 65                Node* child = root;
 66                Node* parent = NULL;
 67                Node* grandpa = NULL;
 68                int flag;
 69 
 70                if(root == NULL)
 71                {
 72                        Node* no = new Node(str);
 73                        root = no;
 74                        return;
 75                }
 76 
 77                while(child != NULL)
 78                {
 79                        if(strcmp(str, child->data) == 0)
 80                        {
 81                                (child->count)++;
 82                                return;
 83                        }
 84 
 85                        parent = child;
 86                        if(strcmp(str, child->data) < 0)
 87                                child = parent->left;
 88                        else 
 89                                child = parent->right;
 90                }
 91 
 92                Node* node = new Node(str);
 93                if(strcmp(node->data, parent->data) < 0)
 94                        parent->left = node;
 95                else 
 96                        parent->right = node;          
 97        }
 98 
 99        void print(Node* node)
100        {
101                if(node != NULL)
102            {
103            print(node->left);
104            printf("%s %.4f\n", node->data, (double)(node->count)*100/vertexNumber);
105            print(node->right);
106            }
107        }
108 
109        Node* getRoot()
110        {
111                return root;
112        }
113 };
114 
115 int main()
116 {
117        AVLTree* avlTree = new AVLTree();
118 
119        char str[30];
120        while(gets(str) != NULL)
121        {
122                avlTree->insert(str);
123                (avlTree->vertexNumber)++;
124        }
125        avlTree->print(avlTree->getRoot());       
126        return 0;
127 }