// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Huffman tree node abstract base class template class HuffNode { public: virtual ~HuffNode() {} // Base destructor virtual int weight() = 0; // Return frequency virtual bool isLeaf() = 0; // Determine type }; template // Internal node subclass class IntlNode : public HuffNode { private: HuffNode* lc; // Left child HuffNode* rc; // Right child int wgt; // Subtree weight public: IntlNode(HuffNode* l, HuffNode* r) { wgt = l->weight() + r->weight(); lc = l; rc = r; } int weight() { return wgt; } bool isLeaf() { return false; } HuffNode* left() const { return lc; } void setLeft(HuffNode* b) { lc = (HuffNode*)b; } HuffNode* right() const { return rc; } void setRight(HuffNode* b) { rc = (HuffNode*)b; } }; template // Leaf node subclass class LeafNode : public HuffNode { private: E it; // Value int wgt; // Weight public: LeafNode(const E& val, int freq) // Constructor { it = val; wgt = freq; } int weight() { return wgt; } E val() { return it; } bool isLeaf() { return true; } };