1 Replies - 1704 Views - Last Post: 10 August 2014 - 07:43 PM Rate Topic: -----

#1 rookie#9   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 51
  • Joined: 04-August 13

binary encryption trees strange occurences

Posted 10 August 2014 - 03:53 PM

assignment:::


Simple Cipher (70 points)

Grading Rubric Points
MakeEmpty, IsEmpty, CountNodes ADT operations 7
GetItem, PutItem, DeleteItem operations 21
Traverse Operation 7
Test Driver Implementation 14
Lab Write-Up 7
Lab Questions 7
Code Style 7
TOTAL 70

Deliverables
A single zip file including the following.

- Your Visual Studio Project directory and associated files, including source files for the iLab.
- The results of your testing. What tests did you run? Did everything work okay? Are there outstanding issues in your program? A short half-page summary of your results is about the right length.
- Your answers to the Part 6 iLab Questions.

If you document any issues, it will be easier to isolate any problems and provide detailed help, and it could potentially improve your grade.

Summary
In this iLab, you will create a simple encryption scheme, also called a cipher, using the binary tree ADT. In the process of implementing binary tree operations, you will also be exposed to a common use for binary trees: encryption and data compression.
Part 1: Understanding the Problem—Encrypting a Sentence

Imagine that you are writing a secret code to your best friend that you want only the two of you to be able to understand. As luck would have it, your best friend has also taken GSP295 and has a good understanding of binary trees. You devise a scheme to encode and decode a message based on the creation of a binary tree of its letters.

To encode a sentence, insert each successive letter into a binary tree using the alphabet as a comparative measure: a is the smallest character and z is the largest.

Take a simple example. To encode the sentence “meet me,” start by inserting the letters m followed by e followed by t into a binary tree. In the first insertion, the binary tree is empty, so m becomes the root node of the tree. Second, e is inserted. Because e is less than m, it is placed on the left node of the m node and becomes a leaf node. Third, a second e is discovered. Because e has already been inserted, the second e does not result in any change. Lastly, t is inserted by first comparing to m and then placing it in the right node of the m root node because it is greater.

After meet the simple binary tree looks like below.



Continue inserting all other letters of the sentence in this fashion. A space character (and other punctuation) is considered less than the a character. The space character is indicated by a simple empty box. When all characters are inserted, the binary tree will look like this.



To encode the message, use a standard convention involving traversing the tree. By convention, simply assign the root node of the tree a * character. For every other character in the tree, assign a character string based on how many lefts and how many rights are involved in the tree traversal. For left traversals, use a <, and for right traversals use a >. In the above example, e will be represented as < and t will become >. The space character will become <<. To complete the code, every character must be separated by a marker called the delimiter. Use ! (an exclamation point) as a delimiter for the code.

Using these conventions, “meet me” becomes the following.

*!<!<!>!<<!*!<!

You can omit the last delimiter character or include it; either way is fine as long as you specify which you’ve done somewhere in your write-up or documentation. Your program should not crash with or without the last delimiter character.

Extend this example further by drawing the binary tree out on paper for “meet me at the window.” What is the full encoding for this statement?

For encryption of simple English messages, cases and punctuation do not matter. You can assume that the user will be typing letters and spaces and does not need to worry about punctuation and special characters. The space character will evaluate to < a. This is perfectly normal. Simply make the assumption that your alphabet has 27 characters starting with space and ending with z.

In order to treat all letters equally, assume that capital letters and lowercase letters are the same. To do this, you can convert a user inputted string into lowercase by using the following code segment example.


You can also use this code segment as a basis for understanding how to process characters individually from a string, which involves the same basic loop.
Part 2: Creating a Binary Encryption Tree ADT

Step 1: Create the ADT

A binary search tree ADT will be needed in order to complete the iLab. Using the ADT described in the textbook, implement a binary tree structure that holds characters (the key value). For the purposes of this iLab, you will not need to implement the entire ADT. You will need the following operations.
• MakeEmpty
• IsEmpty
• GetItem
• PutItem
• DeleteItem
• CountNodes

For all binary tree ADT operations, ensure that the binary search tree property is maintained. The key value of any node is greater than the key value of its left child and any of its children and less than the key value of its right child and any of its children.

Further properties are not required. PutItem and DeleteItem operations do not need to ensure the binary tree is balanced. Please also note that you cannot use already existing binary tree include files or APIs. You must implement the ADT using basic data structures as outlined in your textbook in the Binary Search Trees chapter.

Important: Be careful with edge or border cases. For example, what happens when you delete an item that isn’t in the tree? What happens if you get an item that isn’t in your tree? Your program should not break in these conditions!

Step 2: Modify the GetItem Operation

Now that you’ve created the binary tree ADT you need to make one critical adjustment. Change your GetItem operation to return a string of characters consistent with the tree traversal character creation of left and right from Part 1. Every time GetItem traverses the tree to the right, the > character should be appended to the string. Every time that GetItem traverses the tree to the left, the < character should be appended to the string. In the end, a call to GetItem should return the complete code for the character being searched for. This can be done by changing the return type or by passing a parameter by reference. Either is sufficient.

Remember that you will need to create a special case for the root node, which should return *.

Step 3: Add a Traverse Operation

Add a custom Traverse operation to your ADT. This operation should take a string code as a parameter and return the letter stored at the corresponding location in the binary tree.

For example, passing the Traverse operation a string of <<< will cause it to traverse the binary tree from the root, down the left node, down the left node of that node, and then down the left node of the resulting node. The traverse operation will then return the letter stored at that node.

Remember that you will need to create a special case for the * string, which is the root node.
Part 3: Implementing a Test Driver

Now you are ready to create a test driver to test your new encryption and decryption program.
In order to test your system fully, please implement the following test driver commands.

1. Create Encryption Tree

The Create Encryption Tree command forms the encryption tree from a string of characters known as the key. Both the sender and receiver have to know the encryption key in order to both encode and decode a message. This menu command should do the following.

• Prompt the user for a string (the encryption key).
• Convert the string to all lowercase letters.
• Add each character in the string to the binary tree.
• Output success to the user, along with the number of nodes in the binary tree:
“Encryption Tree created successfully with 14 nodes.”

You must use the CountNotes ADT operation in this command.

2. Encrypt Message

Encrypt message performs the actual message encryption by making calls to GetItem. This menu command should do the following.

• Prompt the user for a string (the message to encrypt).
• Convert the string to all lower case letters.
• Call GetItem from the binary tree ADT on each character in the string.
• Concatenate the codes for each character along with the delimiter.
• Output success to the user along with the encrypted message.
• For example, with the encryption key “meet me,” the message “meet me” becomes the following.

Encoded String: *!<!<!>!<<!*!<

If you are not familiar with string concatenation in C++, you can return the concatenation of two strings by simply adding them together. For example, see below.


3. Remove Characters From a Key

One way to compress a message is to remove characters that aren’t required for its understanding. Vowels are wonderful inventions, but most of the time a message can be understood without them. Create a menu command to remove a character from the encryption key.

• Prompt a user for a string of characters to remove.
• Convert the string to all lowercase letters.
• Call DeleteItem from your binary tree ADT to remove the letters.
• Output success to the user, along with the number of nodes in the binary tree:
“Encryption Tree modified successfully, total nodes: 12.”

You must use the CountNotes ADT operation in this command.

4. Decrypt a Message

Using the binary tree and a code entered from the user, decrypt a message and output it to the user.

• Prompt a user for an encoded message.
• Call Traverse from your binary tree ADT on each code in the string.
• Concatenate the letters for each code character.
• Output success to the user along with the decrypted message.
• For example, with the encryption key “meet me,” the code *!<!<!>!<<!*!< becomes
“Decryption complete: meet me.”

You will have to pre-process the string in order to break it into string codes. Remember that each code is separated by the character !.

Remember to remove the ! or ignore it from your Traverse ADT operation.


Part 4: Testing

In order for your encryption to be useful, the encrypted must be sent to someone with the same encryption key.

Test your program by creating test cases for encryption keys and messages to encode and decode. An excellent test case to use for your encryption key is, “the quick brown fox jumps over the lazy dog.” This sentence contains all the letters of the alphabet, and therefore you can test encode and decode any English sentence with it. For the purposes of exchanging encrypted messages this week, use this sentence as the encryption key.

It would be an excellent idea to test your program by communicating with your classmates via secret code on the discussion boards. Post a message to the discussion boards. Try to decrypt a code that someone else posts. Does the message make sense?

In order to communicate with your classmates, use the encryption key, “the quick brown fox jumps over the lazy dog.”



header:::

#include <iostream>
#include <string>

using namespace std;

enum OrderType{Pre_Order, In_Order, Post_Order};

struct TreeNode
{
	string Info;
	TreeNode* Left;
	TreeNode* Right;
	
};

class Queue
{
public:
	Queue();
	~Queue();
	void Make_Empty(); // resets all values to 0 or -1
	bool Is_Full() const; // check if queue is full
	bool Is_Empty() const; // check if queue is empty
	void Enqueue(string);// adds to queue
	void Dequeue(string); // removes from queue
	void Hash(string value); // hash table function
	void Display(); // display queue

private:
	static const int Peeps_Limit = 3;// limit of people per que
	static const int Carts_Num = 7; // number of carts in ride
	int HashValue;
	int HashSize;
	int Max;
	int front;
	int rear;
	string * queue;
	int StringLength;
	string rides[Carts_Num][Peeps_Limit];
	TreeNode* root;

};

class BinaryADT
{

public:
	//construct
	BinaryADT();
	//destruct functions
	~BinaryADT();
	void Destroy(TreeNode*&);
	//copy functions
	BinaryADT(const BinaryADT& Original_Tree);
	void CopyTree(TreeNode*& Copy, const TreeNode* Orininal_Tree);
	
	void operator= (const BinaryADT& Original_Tree);
	void Make_Empty();
	
	bool Is_Empty() const;
	bool Is_Full() const;
	//retrieval functions
	string Get_Item(string Item, bool& found) const;
	void Retrieve(TreeNode* Tree, string Item, bool& found) const;
	//insert nodes
	void Put_Item(string Item);
	void Insert(TreeNode*& Tree, string Item);
	void FindNode(TreeNode*Tree, string Item, TreeNode*& NodePtr, TreeNode*& ParentPtr);
	//delete nodes
	void Delete_Item(string Item);
	void DeleteNode(TreeNode*& );
	void Delete(TreeNode*&, string);
	void Get_Predecessor(TreeNode* , string& );
	//reset tree
	void Reset_Tree(OrderType Order);
	//get more items
	string Get_Next_Item(OrderType Order, bool& finished);
	//count nodes
	int Count_Nodes(TreeNode*);
	int Get_Length();
	//print functions
	void Print(std::ofstream& outFile);
	void Print_Tree(TreeNode* Tree, std::ofstream& outFile);
	//Traversals
	void PreOrder(TreeNode*, Queue&);
	void InOrder(TreeNode*, Queue&);
	void PostOrder(TreeNode*, Queue&);

private:

	TreeNode* root;

	Queue PreQue;
	Queue InQue;
	Queue PostQue;
};



.cpp


#include "Binary_Tree.h"
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

//check functions

bool BinaryADT::Is_Full() const
{
	TreeNode* location;
	try
	{
		location = new TreeNode;
		delete location;
		return false;
	}
	catch ( bad_alloc exception )
	{
		return true;
	}
}

bool BinaryADT::Is_Empty() const
{
	return root == NULL;
}

//count functions

int BinaryADT::Get_Length()
{
	return Count_Nodes(root);
}

int BinaryADT::Count_Nodes(TreeNode* Tree)
{
	if (Tree == NULL)
	{
		return 0;
	}
	else
	{
		return Count_Nodes(Tree->Left) + Count_Nodes(Tree->Right) + 1;
	}
}

//retrieval functions

string BinaryADT::Get_Item(string Item, bool& found) const
{
	Retrieve(root, Item, found);
	return Item;
}

void BinaryADT::Retrieve(TreeNode* Tree, string Item, bool& found) const
{
	if (Tree == NULL)
	{
		found = false;
	}
	else if (Item < Tree->Info)
	{
		Retrieve(Tree->Left, Item, found);
	}
	else if (Item > Tree->Info)
	{
		Retrieve(Tree->Right, Item, found);
	}
	else
	{
		Item = Tree->Info;
		found = true;
	}
}

//insert functions

void BinaryADT::Put_Item(string Item)
{
	Insert(root, Item);

	TreeNode* NewNode;
	TreeNode* NodePtr;
	TreeNode* ParentPtr;

	NewNode = new TreeNode;
	NewNode->Info = Item;
	NewNode->Left = NULL;
	NewNode->Right = NULL;

	FindNode(root, Item, NodePtr, ParentPtr);

	if (ParentPtr == NULL)
	{
		root = NewNode;
	}
	else if (Item < ParentPtr->Info)
	{
		ParentPtr->Left = NewNode;
	}
	else
	{
		ParentPtr->Right = NewNode;
	}

}

void BinaryADT::Insert(TreeNode*& Tree, string Item)
{
	if (Tree == NULL)
	{
		Tree = new TreeNode;
		Tree->Right = NULL;
		Tree->Left = NULL;
		Tree->Info = Item;
	}
	else if (Item < Tree->Info)
	{
		Insert(Tree->Left, Item);
	}
	else
	{
		Insert(Tree->Right, Item);
	}
}

//delete functions

void BinaryADT::Delete_Item(string Item)
{
	Delete(root, Item);

	TreeNode* NodePtr;
	TreeNode* ParentPtr;

	FindNode(root, Item, NodePtr, ParentPtr);

	if (NodePtr == root)
	{
		DeleteNode(root);
	}
	else if (ParentPtr->Left == NodePtr)
	{
		DeleteNode(ParentPtr->Left);
	}
	else
	{
		DeleteNode(ParentPtr->Right);
	}
}

void BinaryADT::Delete(TreeNode*& Tree, string Item)
{
	if (Item < Tree->Info)
	{
		Delete(Tree->Left, Item);
	}
	else if (Item > Tree->Info)
	{
		Delete(Tree->Right, Item);
	}
	else
	{
		DeleteNode(Tree);
	}
}

void BinaryADT::DeleteNode(TreeNode*& Tree)
{
	string Data;
	TreeNode* TempPtr;

	TempPtr = Tree;
	if (Tree->Left == NULL)
	{
		Tree = Tree->Right;
		delete TempPtr;
	}
	else if (Tree->Right == NULL)
	{
		Tree = Tree->Left;
		delete TempPtr;
	}
	else
	{
		Get_Predecessor(Tree->Left, Data);
		Tree->Info = Data;
		Delete(Tree->Left, Data);
	}
}

void BinaryADT::Get_Predecessor(TreeNode* Tree, string& Data)
{
	while (Tree->Right != NULL)
	{
		Tree = Tree-> Right;
		Data = Tree->Info;
	}
}

//Print functions

void BinaryADT::Print_Tree(TreeNode* Tree, std::ofstream& outFile)
{
	if (Tree != NULL)
	{
		Print_Tree(Tree->Left, outFile);
		outFile << Tree->Info;
		Print_Tree(Tree->Right, outFile);

	}
}

void BinaryADT::Print(std::ofstream& outFile)
{
	Print_Tree(root, outFile);
}

BinaryADT::BinaryADT()
{
	root = NULL;
}
BinaryADT::~BinaryADT()
{
	Destroy(root);
}
void BinaryADT::Destroy(TreeNode*& Tree)
{
	if (Tree != NULL)
	{
		Destroy(Tree->Left);
		Destroy(Tree->Right);
		delete Tree;
	}
}

//copy functions

BinaryADT::BinaryADT(const BinaryADT& Original_Tree)
{
	CopyTree(root, Original_Tree.root);
}

void BinaryADT::operator=(const BinaryADT& Original_Tree)
{
	if (&Original_Tree == this)
	{
		return;
		Destroy(root);
		CopyTree(root, Original_Tree.root);
	}
}

void BinaryADT::CopyTree(TreeNode*& Copy, const TreeNode* Original_Tree)
{
	if (Original_Tree == NULL)
	{
		Copy = NULL;
	}
	else
	{
		Copy = new TreeNode;
		Copy->Info = Original_Tree->Info;
		CopyTree(Copy->Left, Original_Tree->Left);
		CopyTree(Copy->Right, Original_Tree->Right);
	}
}

//transversal time

void BinaryADT::Reset_Tree(OrderType Order)
{
	switch (Order)
	{
	case Pre_Order: PreOrder(root, PreQue); 
		break;
	
	case In_Order: InOrder(root, InQue); 
		break;
	
	case Post_Order: PostOrder(root, PostQue); 
		break;
	}
}

void BinaryADT::PreOrder(TreeNode* Tree, Queue& PreQue)
{
	if (Tree != NULL)
	{
		PreQue.Enqueue(Tree->Info);
		PreOrder(Tree->Left, PreQue);
		PreOrder(Tree->Right, PreQue);
	}
}

void BinaryADT::InOrder(TreeNode* Tree, Queue& InQue)
{
	if (Tree != NULL)
	{
		InOrder(Tree->Left, InQue);
		InQue.Enqueue(Tree->Info);
		InOrder(Tree->Right, InQue);
	}
}

void BinaryADT::PostOrder(TreeNode* Tree, Queue& PostQue)
{
	if (Tree != NULL)
	{
		PostOrder(Tree->Left, PostQue);
		PostOrder(Tree->Right, PostQue);
		PostQue.Enqueue(Tree->Info);
	}
}

string BinaryADT::Get_Next_Item(OrderType Order, bool& finished)
{
	string Item;
	finished = false;
	switch (Order)
	{
	case Pre_Order: PreQue.Dequeue(Item);
		if (PreQue.Is_Empty())
		{
			finished = true;
		}
		break;

	case In_Order: InQue.Dequeue(Item);
		if (InQue.Is_Empty())
		{
			finished = true;
		}
		break;

	case Post_Order: PostQue.Dequeue(Item);
		if (PostQue.Is_Empty())
		{
			finished = true;
		}
		break;
	}
	return Item;
}

//insert node functions
void BinaryADT::FindNode(TreeNode*Tree, string Item, TreeNode*& NodePtr, TreeNode*& ParentPtr)
{
	NodePtr = Tree;
	ParentPtr = NULL;
	bool found = false;
	while (NodePtr != NULL && !found)
	{
		if (Item < NodePtr->Info)
		{
			ParentPtr = NodePtr;
			NodePtr = NodePtr->Left;
		}
		else if (Item > NodePtr->Info)
		{
			ParentPtr = NodePtr;
			NodePtr = NodePtr->Right;
		}
		else
		{
			found = true;
		}
	}
}

	
Queue::Queue()
{
	HashValue = 0;
	HashSize = 7;
	Max = Peeps_Limit;
	front = 0;
	rear = 0;
	StringLength = 0;

}

Queue::~Queue()
{
	delete[] queue;
}

void Queue::Make_Empty()
{
	HashValue = NULL;
	HashSize = NULL;
	Max = NULL;
	front = NULL;
	rear = NULL;
	queue = NULL;
	StringLength = NULL;

	for (int i = 0; i < Carts_Num; i++)
		for (int j = 0; j < Peeps_Limit; j++)
			rides[i][j] = "";

}

bool Queue::Is_Empty() const
{
	return root == NULL;
}

bool Queue::Is_Full() const
{
	TreeNode* location;
	try
	{
		location = new TreeNode;
		delete location;
		return false;
	}
	catch (bad_alloc exception)
	{
		return true;
	}
}


void Queue::Enqueue(string)
{
	const string value; string name; int Name_num;
	cout << "enter the number of names : ";
	cin >> Name_num;

	for (int i = 0; i < Name_num; i++)
	{

		cout << endl << "enter name " << i << " :";
		cin >> name;
		Hash(name);
		rides[HashValue][rear] = name;
		rear = (rear + 1) % Max;
		cout << endl << name << " is now in queue.";
	}

	if (Is_Full())
	{
		cout << "queue is full, please wait " << endl;
		return;
	}
}

void Queue::Dequeue(string)
{
	for (int i = 0; i < Carts_Num; i++)
		rides[i][front] = "";

	front = (front + 1) % Max;

	Display();
}

void Queue::Hash(string value)
{
	for (unsigned index = 0; index < value.size(); index++)
	{
		HashValue = (HashValue * 31) + value[index];
		HashValue %= HashSize;
	}
}


void Queue::Display()
{
	for (int i = 0; i <Carts_Num; i++)
		for (int j = 0; j < Peeps_Limit; j++)
			cout << "Ride " << i << "Person: " << rides[i][j] << endl;
}





main



#include "Binary_Tree.h"
#include <iostream>
#include <fstream>
#include <string>
#include <conio.h>

using namespace std;


int main()
{
	BinaryADT b;
	string teststring;
	int rem, ins, car;
	string Item;
	TreeNode* T;
	T = 0;
	Queue Q;
	
	while (1)
	{
		cout << " Binary Search Tree" << endl;
		cout << endl << endl;
		cout << " 1. Put Item In Queue" << endl;
		cout << " 2. In-Order Traversal " << endl;
		cout << " 3. Pre-Order Traversal " << endl;
		cout << " 4. Post-Order Traversal " << endl;
		cout << " 5. Remove Item In Queue " << endl;
		cout << " 6. exit" << endl;
		cout << " Enter your choice : ";

		cin >> car;
		
		switch (car)
		{
		case 1: cout << " Enter a string to be inserted : ";
			getline(cin, teststring);
			for (unsigned int i = 0; i < teststring.size(); i++)
			{
				teststring[i] = tolower(teststring[i]);
			}
			cin >> ins;
			b.Put_Item(Item);
			break;
		case 2: cout << endl;
			cout << " In-Order Traversal " << endl;
			b.InOrder(T,Q);
			break;
		case 3: cout << endl;
			cout << " Pre-Order Traversal " << endl;
			b.PreOrder(T,Q);
			break;
		case 4: cout << endl;
			cout << " Post-Order Traversal " << endl;
			b.PostOrder(T,Q);
			break;
		case 5: cout << " Enter data to be deleted : ";
			cin >> rem;
			b.Delete_Item(Item);
			break;
		case 6:
			return 0;

		}
	}

	_getch();

}





the header file contains content from this lab and last weeks lab for the enqueue statement... the .cpp is from the book and i made the header to correspond with it... what is goin on with it is when i try to delete a node.....the program breaks... when i enter a character instead of an integer it sends it into an infinite loop of the main call...try this code and see what happens.... pretty sure it is not supposed to do that...

Is This A Good Question/Topic? 0
  • +

Replies To: binary encryption trees strange occurences

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6502
  • View blog
  • Posts: 22,258
  • Joined: 05-May 12

Re: binary encryption trees strange occurences

Posted 10 August 2014 - 07:43 PM

What do you mean by "it breaks"? What have you done to try to narrow down the problem? Or are you trying to get us to do the debugging for you?

The infinite loop is easy. It is because the input stream gets into an error state when it was expecting to parse a number and you entered a letters. Simply check to see if the input stream is in an error state, tell the user that the input was invalid, and the error state.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1