Deck 15: Graphs and Digraphs

Question 1

Write a function that reads a table of letters and their weights and constructs a Huffman code for these letters. Use the function in a program that encodes a message that the user enters.

Answer 1

Problem plan:
• Include the required header files into the program.
• Use "struct" for tree node
• Allocate new tree to a node
• Define a function "encoding ()" to encode the string.
o check if the root node is null
o check if the leaf node is found
o call the function "encoding ()" to append 0
o call the function "encoding ()" to append 1
• Define a function "huff_tree ()" to generate huffman code
o Use map tp count the frequency
o store live nodes
o create leaf node and push the elements
o perform until more than 1 node in the tree
o pointer is stored to the root of the Huffman
o traverse and store the huffman codes
o print the huffman codes
• Define "main()" to demonstrate huffman technique
o Declare variables
o get input from user
o call the function "huff_tree()" to generate huffman code
Program:
/ ***********************************************************Run the code in c++ 11 compiler *
*Program to construct Huffman code and the encode a *
*message entered by the user *
********************************************************** /
/ / include header files
#include
#include
#include
#include
using namespace std;
/ / struct for tree node
struct Node
{
int f;
char ch;
Node *l, *r;
};
/ / allocation of new tree to a node
Node* g_N(char ch, int f, Node* l, Node* r)
{
Node* node = new Node();
/ / assign the node elements
node- ch = ch;
node- f = f;
node- l = l;
node- r = r;
/ / return after all the process has been done
return node;
}
/ / object for comparison
struct comp
{
bool operator()(Node* l, Node* r)
{
/ / the item with highest priority has lowest / / frequency
return l- f r- f;
}
};
/ / traverse and store in an huffman map
void encoding(Node* root, string tx, map huffmanCode)
{
/ / check if the root node is null
if (root == NULL)
return;
/ / if the leaf node is found
if (!root- l !root- r)
huffmanCode[root- ch] = tx;
/ / cal the function to append 0
encoding(root- l, tx + "0", huffmanCode);
/ / call the function to append 1
encoding(root- r, tx + "1", huffmanCode);
}
/ / / build tree and decode
void huff_tree(string inp)
{
/ / to count the frequency
map f;
for (char ch : inp)
f[ch]++;
/ / store live nodes
priority_queue , comp pq;
/ / create leaf node and push the elements
for (auto it : f)
pq.push(g_N(it.first, it.second, NULL, NULL));
/ / perform until more than 1 node in the tree
while (pq.size() != 1)
{
/ / remove nodes with highest priotity
Node *l = pq.top(); pq.pop();
Node *r = pq.top(); pq.pop();
/ / internal node is created and then a new node / / is added
int sum = l- f + r- f;
pq.push(g_N('\0', sum, l, r));
}
/ / pointer is stored to the root of the huffman tree
Node* root = pq.top();
/ / traverse and store the huffman codes
map huffmanCode;
encoding(root, "", huffmanCode);
/ / print the huffman codes
cout "Huffman Code :\n" endl;
for (auto it : huffmanCode)
cout it.first " " it.second endl;
/ / actual string
cout "\n actual string was :\n";
cout inp endl;
/ / print encoded string
string tx = "";
for (char ch : inp)
tx += huffmanCode[ch];
cout "\n encoded string is :\n" tx endl;
}
/ / main function to perform huffman encoding
int main()
{
/ / variable declaration
string inp;
cout "enter the string you want to decode:";
/ / get input from user
cin inp;
/ / call the fuction to generate huffman code
huff_tree(inp);
return 0;
}
Sample Output:
enter the string you want to decode:goodmorning
Huffman Code :
d 1100
g 00
i 1101
m 011
n 111
o 10
r 010
actual string was :
goodmorning
encoded string is :
001010110001110010111110111100

Question 2

(Project) Write a program to compress a file using a Huffman code and to decompress a file generated using this code. The program should first read through the file and determine the number of occurrences of each character in the file and the total number of characters in the file. The weight of each character will be the frequency count for that character. The program should then use these weights to construct the Huffman codes for the characters in the file. It should then read the file again and encode it using these Huffman codes and generate a file containing this encoded data. Compute the compression ratio, which is the number of bits in the compressed file divided by the total number of bits in the original file (eight times the number of characters in the file). The program should also provide the option of decompressing a file that was encoded using this Huffman code.

Answer 2

Problem plan:
• Include the required header files into the program.
• Declare the constant values
• Declare "struct" for node
• Define the class to compare the left and right side values
o Use boolean function for operator
o Return if left value is greater than right value
• Type define for "priority queue"
• Generate the "trie" code
• Define a function "code()" to generate the code
o Initialize the static string
o Check if the right side of the node is not null
o Fill the right substring with "1"
o Again call the function
o Fill until all the right sub tree values are full
o Check if there is no string
o Assign the values to the string
• Define the function "cnt()" function to count values in the text file
o Initilaise the required variables
o Ifsteram to open the input file
o Get the values from file one by one
o Start counting the values
o Use "while" loop to check if the input is text
• If the count is greater or equal to "0" and less than size
• Increment the count value
o Close the input file
• Define the function "bstrngstring()"to check the input file
o Initialize the variable for input
o Initialize a blank string
o Get the input values for the file
o Use while loop to check if the input is text.
o Close the file
• Define the "main()" function to demonstrate Huffman encoding
o Initialize the required variables
o Message for user to enter an option
o Switch case to encode or decode
o When user enters "a"
• Request the user to enter the input file
• Get the filename from the user
• Print the input file name
• Print the output filename
• Open the output file and store the results
• Print the results in the output file
• Loop to print the left count value
• Loop to push values using a temp variable
o Call the function "code()"to go to the top of queue
o Create a bit code string
o Set the bit string value
o Once the encoding is done find the compression ratio
o Otherwise print stating that there is an error
o When the user enters "b"
• Request the user to enter the file name
• Get input file from user
• Open the input file
• Obtain the input from the user one by one
• Check for the magic number
• Check for the match in the input file
• For loop to read the letter count
• Get the input from the user
• Add the valid values to the priority queue
o Create "trie" code
o Create "bit" codes
o Loop until input is not equal to "#"
o Print to the output file the value of "j"
o Assign the bit string value to be blank
o Print when the input by user is not valid
o Close the output file
Program:
/ ***********************************************************Program to encode and decode a file using Huffman coding *
********************************************************** /
/ / include header files
#include
#include
#include
#include
#include
#include "bChar.h"
/ / declare the constant values
const std::string m_num = "7771234777";
const int asze = 256;
int l_Cnt[asze];
std::string st_cd[asze];
/ / declare struct for node
struct t_nd
{
char ch;
int cnt;
t_nd* l;
t_nd* r;
};
/ / define the class to compare the left and right side / / values
class cpre
{
public:
/ / boolean function for operator
bool operator()(const t_nd* left_sde, const t_nd* right_sde) const
{
/ / return if left value is greater than right / / value
return left_sde- cnt right_sde- cnt;
}
};
/ / make of the node
t_nd* makeT_nd(char ch, int cnt)
{
/ / temp value for node
t_nd* tmp = new t_nd;
/ / assign the temp value to point to the character, / / count, left
tmp- ch = ch;
tmp- cnt = cnt;
tmp- l = NULL;
tmp- r = NULL;
return tmp;
};
/ / typedef for priority queue
typedef std::priority_queue , cpre p_q;
/ / to try fotr multiple values in the queue
void tyr(p_q _h)
{
/ / loop until the size is less than 1
while (_h.size() 1)
{
t_nd* holder = new t_nd;
holder- l = _h.top(); _h.pop();
holder- r = _h.top(); _h.pop();
holder- cnt = holder- l- cnt + holder- r- cnt;
holder- ch = -1;
_h.push(holder);
}
}
/ / function to generate the code
void code(t_nd* _h)
{
/ / initialise the static swtring
static std::string bstrng = "";
/ / check if the right side of the node is not null
if (_h- r != NULL)
{
/ / fill the right substring with 1
bstrng += "1";
/ / again call the function
code(_h- r);
/ / fill until all the right sub stree values are / / filled with 1
bstrng = bstrng.substr(0, bstrng.size() - 1);
}
/ / check if the left value is not null
if (_h- l != NULL)
{
/ / fill the right substring with 0
bstrng += "0";
/ / again call the function for left node
code(_h- l);
/ / fill until all the left sub stree values are / / filled with 0
bstrng = bstrng.substr(0, bstrng.size() - 1);
}
/ / check if there is no string
if (!_h- l !_h- r)
{
/ / assign the values to the string
st_cd[_h- ch] = bstrng;
}
}
/ / to count the values in the text file
void cnt(std::string txt_fl, int _h)
{
/ / initilaise the required variables
char wrd;
/ / ifstram to open the input file
std::ifstream inf(txt_fl.c_str());
/ / get the values from file one by one
inf std::noskipws;
/ / start counting the values
for (int i = 0;i asze; ++i)
l_Cnt[i] = 0;
/ / use while loop to check if the input is text
while (inf wrd)
{
/ / if the count is greater or equal to 0 and less / / than size
if (wrd = 0 wrd asze)
{
/ / increment the count value
++l_Cnt[wrd];
++_h;
}
}
/ / close the file
inf.close();
}
/ / function to check the input file
std::string bstrngstring(std::string i_F)
{
/ / initialise the variable for input
char input;
/ / initialise a blank string
std::string bstrng = "";
std::ifstream inf(i_F.c_str());
/ / get the input values fro the file
inf std::noskipws;
/ / use while loop to check if the input is text
while (inf input)
{
bstrng += st_cd[input];
}
/ / close the file
inf.close();
bstrng += st_cd[3];
return bstrng;
}
/ / Function main
int main(int argc, char** argv)
{
/ / initialize the required variables
int r_c;
char ch;
unsigned char ch_in;
std::string i_F = "", o_Txt_fl = "", bstrng = "", bstrngsub = "", mn = "";
std::ofstream o_F;
std::ifstream inf;
p_q pq;
bChar bchar;
int o_sze = 0;
/ / message for user to enter an option
std::cout "select (a / b)\n" std::endl "a. to encode a file" std::endl "b. to decode a file" std::endl;
std::cin ch;
/ / switch case to encode or decode
switch (ch)
{
/ / when user enters 'a'
case 'a':
/ / request the user to enter the input file
std::cout "please enter file to be encoded: " std::endl;
/ / get the filename from the user
std::cin i_F;
/ / the output file o
o_Txt_fl = i_F + ".txt";
/ / print the input file name
std::cout std::left std::setw(17);
std::cout "Input file: " i_F std::endl;
/ / print the output filename
std::cout std::left std::setw(17);
std::cout "Output file:" o_Txt_fl std::endl;
std::cout std::endl;
/ / open the output file and store the results
o_F.open(o_Txt_fl.c_str());
cnt(i_F, o_sze);
if (l_Cnt[3] == 0)
l_Cnt[3] = 1;
/ / print the results in the output file
o_F m_num std::endl;
o_F i_F std::endl;
/ / loop to print the left count value
for (int i = 0; i asze; ++i)
{
o_F l_Cnt[i] " ";
}
o_F std::endl;
/ / loop to push values using a temp variable
for (int i = 0; i asze; ++i)
{
if (l_Cnt[i] 0)
{
/ / call the function "makeT_nd"
t_nd* tmp = makeT_nd(i, l_Cnt[i]);
pq.push(tmp);
}
}
/ / call the functiiion to go to the top of queue
tyr(pq);
code(pq.top());
/ / to create a bit code string
bstrng = bstrngstring(i_F);
o_F '#';
/ / set the bit string value
bchar.setbstrng(bstrng);
o_F std::noskipws;
r_c = bchar.i_R(o_F);
/ / once the encoding is done
if (r_c == bstrng.length())
{
std::cout "Encoding is done successfully! :)" std::endl;
/ / find the compression ratio
std::cout "The ration of compression: " (float)r_c / ((float)o_sze * 8.0) * 100.0 "%" std::endl;
}
else
{
/ / otherwise print stating that there is an / / error
std::cout "there is an error :(" std::endl;
std::cout "Expected: " bstrng.length() * 8 " but got: " r_c std::endl;
}
break;
/ / when the user enters b
case 'b':
/ / request the user to enter the file name
std::cout "Please enter the file to be decoded: " std::endl;
/ / get input file from user
std::cin i_F;
/ / open the input file
inf.open(i_F.c_str());
/ / obtain the input form the user one by one
inf mn;
/ / check for the magic number
if (mn != m_num)
{
std::cout "the numbers does not match" std::endl;
return 1;
}
inf o_Txt_fl;
/ / check for the match in the input file
if (o_Txt_fl != i_F.substr(0, i_F.length() - 4))
{
std::cout o_Txt_fl " "
std::cout "no match found but the decoding can be performed" std::endl;
}
o_F.open(o_Txt_fl.c_str());
/ / for loop to read the letter count
for (int i = 0; i asze; ++i)
{
/ / get the input from the user
inf l_Cnt[i];
if (l_Cnt[i] 0)
{
/ / add the valid values to the the / / priority queue
t_nd* tmp = makeT_nd(i, l_Cnt[i]);
pq.push(tmp);
}
}
/ / to create trie code
tyr(pq);
/ / to create bit codes
code(pq.top());
/ / loop until input is not equal to "#"
while (ch_in != '#')
{
inf ch_in;
}
inf std::noskipws;
while (inf ch_in)
{
bstrng += bchar.g_B(ch_in);
}
/ / close the input dile
inf.close();
for (int i = 0; i bstrng.length(); ++i)
{
/ / increment the value of bit string variable
bstrngsub += bstrng[i];
for (int j = 0; j asze; ++j)
{
/ / check if the bit string is equal to / / string code
if (bstrngsub == st_cd[j])
{
/ / if it is an end of file
if (j == 3)
{
/ / go to the newline
o_F "\n";
i = bstrng.length();
/ / then exit
break;
}
/ / print to the output file the / / value of j
o_F (char)j;
/ / assign the bit string value to / / be blank
bstrngsub = "";
break;
}
}
}
break;
default:
/ / print when the input by user is not valid
std::cout "your choice is invalid" std::endl;
break;
}
/ / close the output file
o_F.close();
return 0;
}
bChar.h:
/ / include header files
#include
#include
#include
#include
/ / class definition for bChar
class bChar {
public:
/ / declare the variables in public
unsigned char* c;
int shift_cnt;
std::string bstrng;
/ / function call for bchar()
bChar();
void setbstrng(std::string _h);
int i_R(std::ofstream outf);
std::string g_B(unsigned char _h);
void w_R(std::ofstream outf);
~bChar();
};
/ / include the required files
#include "bChar.h"
/ / include the ffunction from the header "bChar.h"
bChar::bChar()
{
shift_cnt = 0;
c = (unsigned char*)calloc(1, sizeof(char));
}
/ / this function will return how many bits are been inserted
void bChar::setbstrng(std::string _h)
{
bstrng = _h;
}
int bChar::i_R(std::ofstream outf)
{
int tot = 0;
/ / check the length of the bit string
while (bstrng.length())
{
if (bstrng[0] == '1')
*c |= 1;
*c = 1;
++shift_cnt;
++tot;
bstrng.erase(0, 1);
/ / check if the shift count is 7
if (shift_cnt == 7)
{
/ / write the results to the output file
w_R(outf);
shift_cnt = 0;
free(c);
c = (unsigned char*)calloc(1, sizeof(char));
}
}
/ / check for trailing bits
if (shift_cnt 0)
{
/ / if there is a trailing bit then push it
*c = (8 - shift_cnt);
w_R(outf);
free(c);
c = (unsigned char*)calloc(1, sizeof(char));
}
return tot;
}
/ / the output is given in binary format
std::string bChar::g_B(unsigned char _h)
{
std::stringstream _itoa;
int _size = sizeof(unsigned char) * 8;
for (unsigned _s = 0; _s _size - 1; ++_s)
{
_itoa ((_h (_size - 1 - _s)) 1);
}
return _itoa.str();
}
/ / function to write the bits
void bChar::w_R(std::ofstream outf)
{
outf *c;
}
/ / destructor for the method "bChar()"
bChar::~bChar()
{
if (c)
free(c);
}
Sample Input file:
Maria is studying to become an immigration lawyer.
At her university alone there are more than a thousand undocumented students;
so many, they have established a support centre.
Cities like Los Angeles have vowed to fight to defend immigrant communities from Mr Trump's policies
Sample Output:
select (a / b)
a. to encode a file
b. to decode a file
a
please enter file to be encoded:
f1.txt
Input file: f1.txt
Output file: f1.txt.txt
Encoding is done successfully! :)
The ration of compression: 55.3191%
f1.txt.mpc :
7771234777
f1.txt
0 0 0 1 0 0 0 0 0 0 3 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 0 0 0 0 0 1 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 16 2 5 9 29 3 5 9 19 0 1 6 12 16 16 4 0 14 16 21 9 4 2 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Question 3

Write a driver program to test your AVLTree class template from Exercise 14.

Answer 3

Problem plan:
• Include the required header files into the program.
• Declare the AVL node class template
• Now define the template class for AVL node
o Initialize the required variables
o Assign values to all the node variables
o Delete the nodes
• Define the class template for AVL tree node.
o Declare the required functions
o Initialize the root node
o Declare the function to rotate right
o Declare the function to rotate left
o Declare the function to rotate left then right
o Declare the function to rotate right then left
o Declare the other functions to re-balance a tree, find height, set balance, print balance and clear nodes
• Define the functions
• Define the "main()" function to demonstrate the AVL tree class template
o Create an object for AVL tree class
o Start inserting the values into the tree
o Call the function "prnt_bal()" to print the results
Program:
/ ***********************************************************Program to test AVL Tree class template *
********************************************************** /
/ / include the required header files
#include
#include
using namespace std;
/ / AVL node class template
template
/ / class definition
class AVL_node {
public:
/ / initialise the required variables
T key;
int balance;
AVL_node *l, *r, *parent;
/ / assign values to all the node variables
AVL_node(T k, AVL_node *p) : key(k), balance(0), parent(p),
l(NULL), r(NULL) {}
/ / delete the nodes
~AVL_node()
{
delete l;
delete r;
}
};
/ / template for AVLTree class
template
/ / class definition
class AVLtree
{
public:
/ / declare the required functions
AVLtree(void);
~AVLtree(void);
/ / to insert the values into the tree
bool insert(T key);
/ / to delete the constant value k
void del_K(const T key);
/ / to print the balance
void prnt_bal();
private:
/ / initialize the root node
AVL_node *root;
/ / initilaise to rotate left
AVL_node * LL(AVL_node *a);
/ / initilaise to rotate right
AVL_node * RR(AVL_node *a);
/ / initilaise to rotate left then right
AVL_node * LR(AVL_node *n);
/ / initialize to rotate right then left
AVL_node * RL(AVL_node *n);
/ / to re_bal the tree
void re_bal(AVL_node *n);
/ / to find the ht of the tree
int ht(AVL_node *n);
/ / to set the balance of the tree
void st_bal(AVL_node *n);
/ / to print the balance of the tree
void prnt_bal(AVL_node *n);
/ / to clear the nodes
void clr_n(AVL_node *n);
};
/ / AVL tree class definition
template
/ / function definition for rebalancing the nodes
void AVLtree ::re_bal(AVL_node *n)
{
st_bal(n);
/ / if the balance is -2
if (n- balance == -2)
{
/ / if the height of left is greater than height of / / right
if (ht(n- l- l) = ht(n- l- r))
/ / then perform RR rotation
n = RR(n);
else
/ / otherwise perform LR rotation
n = LR(n);
}
/ / if the balance is 2
else if (n- balance == 2)
{
/ / if the height of the right tree is greater than / / height of left right
if (ht(n- r- r) = ht(n- r- l))
/ / perform LL rotation
n = LL(n);
else
/ / perform RL rotation
n = RL(n);
}
/ / if the parent node is null
if (n- parent != NULL) {
/ / perform rebalancing the tree
re_bal(n- parent);
}
else {
/ / assign the root to n
root = n;
}
}
/ / template function for LL rotation
template
/ / perform LL rotation
AVL_node * AVLtree ::LL(AVL_node *a)
{
/ / assign right of a to b
AVL_node *b = a- r;
/ / a is assigned to parent of b
b- parent = a- parent;
/ / left of b is assigned to right of b
a- r = b- l;
/ / check if the right of a is not equal to null
if (a- r != NULL)
a- r- parent = a;
/ / a is assigned to left of b
b- l = a;
/ / b is assigned to parent of b
a- parent = b;
/ / if the parent of b is not NULL
if (b- parent != NULL) {
if (b- parent- r == a) {
b- parent- r = b;
}
else {
b- parent- l = b;
}
}
/ / set balance of a
st_bal(a);
/ / set balance of b
st_bal(b);
return b;
}
template
/ / template function for RR rotation
AVL_node * AVLtree ::RR(AVL_node *a)
{
AVL_node *b = a- l;
/ / parent of a is assigned to parent of b
b- parent = a- parent;
/ / right of b is assigned to left of a
a- l = b- r;
/ / check if left of a is NULL
if (a- l != NULL)
a- l- parent = a;
/ / a is assigned to right of b
b- r = a;
/ / b is assigned to parent of a
a- parent = b;
/ / check if parent of b is NULL
if (b- parent != NULL) {
if (b- parent- r == a) {
b- parent- r = b;
}
else {
b- parent- l = b;
}
}
/ / set balance of a
st_bal(a);
/ / set balance of b
st_bal(b);
return b;
}
/ / template LR rotation
template
/ / perform LR rotation
AVL_node * AVLtree ::LR(AVL_node *n)
{
n- l = LL(n- l);
return RR(n);
}
/ / template function for RL rotation
template
AVL_node * AVLtree ::RL(AVL_node *n)
{
n- r = RR(n- r);
return LL(n);
}
template
/ / find the height of the tree
int AVLtree ::ht(AVL_node *n)
{
if (n == NULL)
return -1;
return 1 + max(ht(n- l), ht(n- r));
}
/ / set the balance of the tree
template
void AVLtree ::st_bal(AVL_node *n)
{
n- balance = ht(n- r) - ht(n- l);
}
/ / print the balance node
template
/ / define the function to print the tree
void AVLtree ::prnt_bal(AVL_node *n)
{
/ / check if n is not NULL
if (n != NULL)
{
/ / cal the function to print the left tree
prnt_bal(n- l);
cout n- balance "\n";
/ / call the function to print the right tree
prnt_bal(n- r);
}
}
template
/ / check if the AVL tree is NULL
AVLtree ::AVLtree(void) : root(NULL) {}
/ / check if the AVL tree is void then delete the root node
template
AVLtree ::~AVLtree(void)
{
/ / delete the root value
delete root;
}
/ / template class to insert element into the tree
template
/ / define the function insert the node
bool AVLtree ::insert(T key)
{
/ / check if the root value is NULL
if (root == NULL)
{
root = new AVL_node (key, NULL);
}
else {
AVL_node
*n = root,
*parent;
/ / use while loop to insert the element into the / / tree
while (true)
{
/ / check if the n of key equals to key
if (n- key == key)
return false;
/ / n is assigned to the parrent
parent = n;
bool g_L = n- key key;
/ / if the control goes to left then n is / / right otherwise left
n = g_L ? n- l : n- r;
/ / check if the n value is null
if (n == NULL) {
if (g_L)
{
/ / left of the parent is set to new / / AVL node
parent- l = new AVL_node (key, parent);
}
else
{
/ / right of the parent node is set / / to new AVL node
parent- r = new AVL_node (key, parent);
}
/ / rebalance the parent node
re_bal(parent);
break;
}
}
}
return true;
}
/ / template class for deletion
template
/ / function to delete the values
void AVLtree ::del_K(const T d_k)
{
if (root == NULL)
return;
/ / assign nodes with the respective values
AVL_node
*n = root,
*parent = root,
*d_N = NULL,
*child = root;
/ / use while loop to check the nodes one by one whether / / it is balanced and then delete the nodes
while (child != NULL)
{
/ / if the value is not null the assign n to parent / / node
parent = n;
/ / assign child to n
n = child;
child = d_k = n- key ? n- r : n- l;
/ / check if the key to be deleted is equal the / / node
if (d_k == n- key)
d_N = n;
}
/ / if the delete key value is not null
if (d_N != NULL) {
/ / then the key is assigned to delete node
d_N- key = n- key;
/ / now the left node is assigned to the child
child = n- l != NULL ? n- l : n- r;
/ / if the root is assigned to the delete key node
if (root- key == d_k)
{
/ / childe is assigned to the root node
root = child;
}
else {
/ / if the left of parent is n
if (parent- l == n) {
/ / then assign the child to left
parent- l = child;
}
else
{
/ / otherwise assign right to the child
parent- r = child;
}
/ / call the function to rebalance the nodes / / again
re_bal(parent);
}
}
}
/ / template class to print the balance
template
void AVLtree ::prnt_bal() {
prnt_bal(root);
cout endl;
}
/ / main function to demonstarte AVLTree class
int main(void)
{
/ / create an object for AVL tree class
AVLtree t;
/ / start inserting the values into the tree
cout "Inserting values into the tree one by one....." endl;
/ / insert values into the tree
t.insert(11);
t.insert(33);
t.insert(22);
t.insert(55);
t.insert(44);
t.insert(99);
t.insert(77);
t.insert(88);
t.insert(66);
/ / print the values
cout "Print the balance factor: ";
/ / call the function to print the results
t.prnt_bal();
}
Sample Output:
Inserting values into the tree one by one.....
Print the balance factor: 0
0
0
1
1
0
0
0
-1

Question 4

Write a driver program to test your red-black tree class template from Exercise 24.

Question 5

Write a driver program to test your B-tree class template from Exercise 25.

Question 6

Write a driver program to test your general-tree class template from Exercise 26.

Question 7

Use your B-tree class template from Exercise 26 in a program that reads words and constructs a B-tree to store these words. The program should then allow the user to enter a word and should search the B-tree for this word.

Question 8

Demonstrate that Morse code is not immediately decodable by showing that the bit string 100001100 can be decoded in more than one way.

Question 9

Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5.
000001001

Question 10

Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5.
001101001

Question 11

Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5.
000101001

Question 12

Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5.
00001010011001

Question 13

Construct the Huffman code for the C++ keywords and weights given in the following table:

Question 14

Repeat Exercise 6 for the following table of letters and weights:

Question 15

Using the Huffman code developed in Exercise 7, encode the message "feed a deaf aged hag".

Question 16

Repeat Exercise 3 for the following table of C++ keywords and weights (frequencies):

Question 17

For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing.
long, const, typedef, bool, public, break, else

Question 18

For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing.
bool, new, return, struct, while, case, enum

Question 19

For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing.
do, long, new, and, operator, int, namespace

Question 20

For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing.
unsigned, short, long, int, double, char

Question 21

For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing.
bool, enum, if, this, else, case, void, do, return, unsigned, false, true, double, while

Question 22

Proceed as in Exercises 1-5, but for the following collections of numbers:
22, 44, 88, 66, 55, 11, 99, 77, 33

Question 23

Proceed as in Exercises 1-5, but for the following collections of numbers:
11, 22, 33, 44, 55, 66, 77, 88, 99

Question 24

Proceed as in Exercises 1-5, but for the following collections of numbers:
99, 88, 77, 66, 55, 44, 33, 22, 11

Question 25

Proceed as in Exercises 1-5, but for the following collections of numbers:
55, 33, 77, 22, 11, 44, 88, 66, 99

Question 26

Proceed as in Exercises 1-5, but for the following collections of numbers:
50, 45, 75, 65, 70, 35, 25, 15, 60, 20, 41, 30, 55, 10, 80

Question 27

Proceed as in Exercises 1-5, but for the following collections of numbers:
Draw diagrams for a simple left rotation similar to those in the text for the simple right rotation. Also describe what links must be reset to accomplish this rotation.

Question 28

Proceed as in Exercises 1-5, but for the following collections of numbers:
Draw diagrams for a right-left rotation similar to those in the text for the left-right rotation. Also describe what links must be reset to accomplish this rotation.

Question 29

Proceed as in Exercises 1-5, but for the following collections of numbers:
Design and test an AVLTree class template.

Question 30

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given:
55, 66, 44, 77, 33, 88, 22, 99, 11

Question 31

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given:
55, 66, 77, 88, 99, 11, 22, 33, 44

Question 32

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given:
11, 22, 33, 44, 55, 66, 77, 88, 99

Question 33

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given:
99, 88, 77, 66, 55, 44, 33, 22, 11

Question 34

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given:
B, E, A, N, S

Question 35

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given:
C, O, R, N, F, L, A, K, E, S

Question 36

Draw the red-black trees for the 2-3-4 trees in Exercises 1-6.

Question 37

Draw the red-black trees for the 2-3-4 trees in Exercises 1-6.

Question 38

Draw the red-black trees for the 2-3-4 trees in Exercises 1-6.

Question 39

Draw the red-black trees for the 2-3-4 trees in Exercises 1-6.

Question 40

Draw the red-black trees for the 2-3-4 trees in Exercises 1-6.

Question 41

Draw the red-black trees for the 2-3-4 trees in Exercises 1-6.

Question 42

Repeat Exercises 1-6, but use B-trees of order 5.

Question 43

Repeat Exercises 1-6, but use B-trees of order 5.

Question 44

Repeat Exercises 1-6, but use B-trees of order 5.

Question 45

Repeat Exercises 1-6, but use B-trees of order 5.

Question 46

Repeat Exercises 1-6, but use B-trees of order 5.

Question 47

Repeat Exercises 1-6, but use B-trees of order 5.

Question 48

Construct the B-tree of order 5 that results when the following integers are inserted in the order given: 261, 381, 385, 295, 134, 400, 95, 150, 477, 291, 414, 240, 456, 80, 25, 474, 493, 467, 349, 180, 370, 257.

Question 49

Give the binary-tree representation of the following tree:

Question 50

Give the binary-tree representation of the following forest:

Question 51

Give an algorithm to delete a node from a 2-3-4 tree.

Question 52

Give an algorithm to delete a node from a red-black tree.

Question 53

Exercises 24-26 ask you to develop class templates for various trees. You should also write driver programs to test your answers as instructed in Programming Problems 4-6 at the end of this chapter.
Develop a class template for red-black trees.

Question 54

Exercises 24-26 ask you to develop class templates for various trees. You should also write driver programs to test your answers as instructed in Programming Problems 4-6 at the end of this chapter.
Develop a class template for B-trees that uses nodes with more than two links as described in the text to store the nodes of the B-tree.

Question 55

Exercises 24-26 ask you to develop class templates for various trees. You should also write driver programs to test your answers as instructed in Programming Problems 4-6 at the end of this chapter.
Develop a class template for general search trees that uses a binary tree to represent the tree as described in the text.