• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# C++ binary tree /entropy

a guest May 9th, 2012 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <conio.h>
2. #include <iostream>
3. #include <cctype>
4. #include <string>
5. #include <fstream>
6. #include <math.h>
7.     using namespace std;
8.
9. #define MAX_LEN_FILE    256
10. #define M_LOG2E 1.44269504088896340736 //log2(e)
11.
12. inline long double log2(const long double x){
13.     return  log(x) * M_LOG2E;
14. }
15.
16. struct TreeNode
17. {
18.     string word;
20.     TreeNode *left;
21.     TreeNode *right;
22.
23.     TreeNode(string str, int g)
24.     {
25.         word = str;
27.         count = 1;
28.         left = NULL;
29.         right = NULL;
30.     }
31. };
32.
33. void Find(TreeNode *node, string str, int g)
34. {
36.     {
37.         if (str == node->word)
38.         {
39.             // Yes, the item has been found in the root node.
40.             node->count++;
41.             return;
42.         }
43.     }
44.     else if (g < node->grade) {
45.         // If the item occurs, it must be in the left subtree.
46.         if (node->left == NULL)
47.         {
48.             node->left = new TreeNode(str, g);
49.             return;
50.         }
51.         else
52.             return Find( node->left, str, g );
53.     }
54.     else {
55.         // If the item occurs, it must be in the right subtree.
56.         if (node->right == NULL)
57.         {
58.             node->right = new TreeNode(str, g);
59.             return;
60.         }
61.         else
62.         return Find( node->right, str, g );
63.     }
64. }
65.
66. double ComputeEntropy(TreeNode *root, int count)
67. {
68.     double entropy = 0;
69.
70.     entropy += (-log2(root->count/(double)count)) * root->count;
71.
72.     if (root->left != NULL)
73.         entropy += ComputeEntropy(root->left, count);
74.
75.     if (root->right != NULL)
76.         entropy += ComputeEntropy(root->right, count);
77.
78.     return entropy;
79. }
80.
81. int main()
82. {
83.     TreeNode *root;
84.     char name[MAX_LEN_FILE], temp;
85.     bool first = true;
86.     int wordsCount = 0;
87.
88.     root = NULL;
89.
90.     cout << "Zadejte cestu k souboru: ";
91.     cin >> name;
92.
93.     ifstream file;
94.
95.     file.open (name, ifstream::in);
96.
97.     if(!file.is_open())
98.     {
99.         cout << "Spatne zadana cesta k souboru!" << endl;
100.         getche();
101.         return 0;
102.     }
103.
105.     string word;
106.
107.     while (file.get(temp) && !file.eof())
108.     {
109.
110.                 if(isalpha(temp))
111.         {
112.             word += temp;
114.         }
115.         else if (word != "")
116.         {
117.             if (first)
118.             {
119.                 root = new TreeNode(word, grade);
120.                 first = false;
121.             }
122.             else
123.             {
125.             }
126.
127.             wordsCount++;
129.             word = "";
130.         }
131.     }
132.
133.     file.close();
134.
135.     cout.precision(10); // ??
136.     cout << fixed << ComputeEntropy(root, wordsCount);
137.
138.     getche();
139.     return 0;
140. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top