DSA-Assignments

commit e6f8b2cc5be1a9deec1b05e0315f15e5c0dd80c3
parent b7c5af167bad9e69d666a307bb46991e8d59bd74
Author: William Lindholm <a22willi@student.his.se>
Date:   Wed, 29 Nov 2023 14:46:38 +0100

Implemented huffman tree structure using priority queue.

Diffstat:
M
Problem3/Problem3.cpp
 | 
85
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---

1 file changed, 82 insertions(+), 3 deletions(-)
diff --git a/Problem3/Problem3.cpp b/Problem3/Problem3.cpp
@@ -7,8 +7,88 @@
 
 
 #include <iostream>
+#include <vector>
+#include <queue>
+
+using namespace std;
+
+
+struct node
+{
+	char data;
+	int freq = 0;
+	node* left = NULL;
+	node* right = NULL;
+};
+
+
+class nodeComparator
+{
+	public:
+		bool operator() (const node& leftNode, const node& rightNode) const
+		{
+			return leftNode.freq > rightNode.freq;
+		}
+};
+
+
+/*
+ * Class: HuffmanTree
+ * Description: A Huffman tree
+ */
+class huffmanTree
+{
+	private:
+		priority_queue<node, vector<node>, nodeComparator> nodes;
+
+	public:
+		/*
+		 * Function: Constructor
+		 * Description: Create a Huffman tree from a string
+		 * @param plainText: the string to create the tree 
+		 */
+		huffmanTree(string plainText)
+		{
+			// create nodes 
+			for (int i = 0; i < (int) plainText.length(); i++)
+			{
+				node n;
+				n.data = plainText[i];
+				n.freq += 1;
+				nodes.push(n);
+			}
+		}
+			
+		/*
+		 * Function: getTree
+		 * Description: Get the Huffman tree
+		 * @return: reference of ´the Huffman tree
+		 */
+		priority_queue<node, vector<node>, nodeComparator> getTree() const
+		{
+			return nodes;
+		}
+
+		/*
+		 * Function: printTree
+		 * Description: Print the Huffman tree
+		 */
+		void print() const
+		{
+			priority_queue<node, vector<node>, nodeComparator> temp = nodes;
+
+			while (!temp.empty())
+			{
+				cout << temp.top().data << " " << temp.top().freq << endl;
+				temp.pop();
+			}
+		}
+};
+
 
 int main()
 {
-    std::cout << "Hello World!\n";
-}
-\ No newline at end of file
+	huffmanTree T = huffmanTree("Hello World");
+
+	T.print();
+};