这题，我起先用的是AVL树，结果时间超时，最后发现，直接用二叉树就行了，根本就不需要旋转。由于数据是随机的，因而这棵二叉树的性能还行。当然还可以用来解决。
题目很简单，直接上代码
1 #include2 #include 3 #include 4 #include 5 #include 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 =http://www.cnblogs.com/shuaiwhu/archive/2012/06/29/ NULL; 19 left = right = NULL; 20 balance = count = 0; 21 } 22 Node(char* s) 23 { 24 data = http://www.cnblogs.com/shuaiwhu/archive/2012/06/29/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 }