IP Addresses and Binary Search Tree

Program Description

This is a programming assignment. You will develop a binary tree with some of its operations.

• You need to implement a data structure to represent a node. Each node should have data fields containing four integers from an IP address as its key, its parent node called "parent", its left child node called "left", and its right child node called "right".
• Using the nodes above, you need to implement a binary search tree using their keys.
• Since each IP address looks something like: 103.28.113.134, if you compare two IP addresses, then first, you need to compare the left most integer to decide which one is larger, then compare the second integers from left. If they are same, then compare the third integers from left. If they are same, then compare the forth integers from left. For instance, 103.28.113.134 is considered to be smaller than 103.28.221.153, because of their third integer.
• Your binary search tree needs to have operations "inorderTreeWalk", "preorderTreeWalk", and "postorderTreeWalk" that will print all node keys in a certain order (see the lecture notes/textbook.)
• Your binary search tree needs to have operations "treeInsert", "treeDelete", "treeSearch", "treeMinimum", "treeMaximum", "treeSuccessor", and "treePredecessor",. (see the lecture notes/textbook for those operations.)
• BinarySeachTree class should have a constructor that initializes its root to be NULL, and a destructor that will delete all nodes in the tree and perform garbage collections. The destructor should also print “The number of nodes deleted: X” where X is the number of nodes deleted and it should be called when a user chooses to exit the program.
• You should implement a driver class with a main method which takes the following commands (A, B, C, D, E, F, G, H, I, J, Q) from the keyboard:
  • In-order print command, it should print all keys in the tree using the in-order, by placing a carriage return between keys. It should print "tree is empty" if the tree is empty.
  • Pre-order print command, it should print all keys in the tree using the pre-order, by placing a carriage return between keys. It should print "tree is empty" if the tree is empty.
  • Post-order print command, it should print all keys in the tree using the post-order, by placing a carriage return between keys. It should print "tree is empty" if the tree is empty.
  • Tree Minimum command, it should call "treeMinimum" and print the minimum value as "The minimum IP address is x" where x is the smallest IP address in the tree. It should print "tree is empty" if the tree is empty.
  • Tree Maximum command, it should call "treeMaximum" and print the maximum value as "The maximum IP address is x" where x is the largest IP address in the tree. It should print "tree is empty" if the tree is empty .
  • Tree Predecessor command, it should prompt “Please enter an IP address to find its predecessor:n”, and read in the input. It should call "treePredecessor" and print the predecessor as "The predecessor of xxx.xxx.xxx.xxx is yyy.yyy.yyy.yyy" where xxx.xxx.xxx.xxx is the IP address entered by a user and yyy.yyy.yyy.yyy is its predecessor. If it does not have any predecessor, print “IP address does not have any predecessor”. It should print "tree is empty" if the tree is empty.
  • Tree Successor command, it should prompt “Please enter an IP address to find its successor:n”, and read in the input. It should call "treeSuccessor" and print the successor as "The successor ofxxx.xxx.xxx.xxx is yyy.yyy.yyy.yyy" where xxx.xxx.xxx.xxx is the IP address entered by a user and yyy.yyy.yyy.yyy is its successor. If it does not have any successor, print “IP address does not have any successor”. It should print "tree is empty" if the tree is empty.
  • Search command, it should ask user “Please enter an IP address to search:n”. Then you should call "treeSearch" operation to search the value. Then the program should print "The IP address xxx.xxx.xxx.xxx found" if it is found, and print "The IP address xxx.xxx.xxx.xxx not found", otherwise, where xxx.xxx.xxx.xxx is the IP address entered by a user.
  • Insert command, it should ask user “Please enter an IP address to insert:n”. Then you should call "treeInsert" operation to insert this value. Then the program should print "The IP address xxx.xxx.xxx.xxx inserted" if it is inserted successfully, and print "The IP address xxx.xxx.xxx.xxx not inserted", otherwise, where xxx.xxx.xxx.xxx is the IP address entered by a user.
  • Delete command, it should ask user “Please enter an IP address to delete:n”. Then you should call "delete" operation to search and delete the value. Then the program should print "The IP address xxx.xxx.xxx.xxx deleted" if it is deleted successfully, and print "The IP address xxx.xxx.xxx.xxx not deleted", otherwise, where xxx.xxx.xxx.xxx is the IP address entered by a user .
  • Quit the program and exit. The binary search tree object should be deleted.

The following is an example run.

Sample Output: (the user enters the string shown in bold)

Choice Action
------ ------
A Inorder Print
B Preorder Print
C Postorder Print
D Tree Minimum
E Tree Maximum
F Tree Predecessor
G Tree Successor
H Tree Search
I Tree Insert
J Tree Delete
Q Quit
? Display Help

What action would you like to perform?
I
Please enter an IP address to insert:
403.28.113.134
The IP address 403.28.113.134 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
509.202.41.38
The IP address 509.202.41.38 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
110.322.167.104
The IP address 110.322.167.104 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
610.136.161.29
The IP address 610.136.161.29 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
110.322.176.145
The IP address 110.322.176.145 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
210.138.248.249
The IP address 210.138.248.249 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
110.138.194.176
The IP address 110.138.194.176 inserted
What action would you like to perform?
A
110.138.194.176
110.322.167.104
110.322.176.145
210.138.248.249
403.28.113.134
509.202.41.38
610.136.161.29
What action would you like to perform?
B
403.28.113.134
110.322.167.104
110.138.194.176
110.322.176.145
210.138.248.249
509.202.41.38
610.136.161.29
What action would you like to perform?
C
110.138.194.176
210.138.248.249
110.322.176.145
110.322.167.104
610.136.161.29
509.202.41.38
403.28.113.134
What action would you like to perform?
F
Please enter an IP address to find its predecessor:
509.202.41.38
The predecessor of 509.202.41.38 is 403.28.113.134
What action would you like to perform?
G
Please enter an IP address to find its successor:
110.322.176.145
The successor of 110.322.176.145 is 210.138.248.249
What action would you like to perform?
D
The minimum IP address is 110.138.194.176
What action would you like to perform?
E
The maximum IP address is 610.136.161.29
What action would you like to perform?
H
Please enter an IP address to search:
51.222.209.77
The IP address 51.222.209.77 not found
What action would you like to perform?
H
Please enter an IP address to search:
610.136.161.29
The IP address 610.136.161.29 found
What action would you like to perform?
I
Please enter an IP address to insert:
112.65.241.44
The IP address 112.65.241.44 inserted
What action would you like to perform?
I
Please enter an IP address to insert:
51.222.209.77
The IP address 51.222.209.77 inserted
What action would you like to perform?
H
Please enter an IP address to search:
110.136.161.30
The IP address 110.136.161.30 not found
What action would you like to perform?
J
Please enter an IP address to delete:
610.136.161.29
The IP address 610.136.161.29 deleted
What action would you like to perform?
J
Please enter an IP address to delete:
610.138.161.29
The IP address 610.138.161.29 not deleted
What action would you like to perform?
A
51.222.209.77
110.138.194.176
110.322.167.104
110.322.176.145
112.65.241.44
210.138.248.249
403.28.113.134
509.202.41.38
What action would you like to perform?
D
The minimum IP address is 51.222.209.77
What action would you like to perform?
E
The maximum IP address is 509.202.41.38
What action would you like to perform?
A
51.222.209.77
110.138.194.176
110.322.167.104
110.322.176.145
112.65.241.44
210.138.248.249
403.28.113.134
509.202.41.38
What action would you like to perform?
B
403.28.113.134
110.322.167.104
110.138.194.176
51.222.209.77
110.322.176.145
210.138.248.249
112.65.241.44
509.202.41.38
What action would you like to perform?
C
51.222.209.77
110.138.194.176
112.65.241.44
210.138.248.249
110.322.176.145
110.322.167.104
509.202.41.38
403.28.113.134
What action would you like to perform?
Q
The number nodes deleted: 8