Department of Computer Science and Engineering, IIT Kanpur
CS210: Data Structures
Dr. R. K. Ghosh
Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Solution to Assignment 7
Following lines will give you a specific idea on how to tackle the problems including how to design the data structures and what functions are needed .
Data structure for slicing tree
The structure can be designed in following manner. It will consist of the coordinates of the rectangle with height and width , the left and right nodes in the slice tree ,the number of the rectangles .
In case of a cut the new node is the right one , while the left is the changed one. The coordinates for the nodes are set at the time of cuts. The distinction between the horizontal and vertical cut can be displayed by the use of proper symbol like a horizontal bar or vertical bar(hyphen).
Initially there is only one rectangle with some given coordinates . Then with the use of mouse or butons we can ask for cuts and the position of the cuts . These informations are then used to update the data structure .
For displaying the rectangle we use the coordinates , the cut symbols (to figure out whether the cuts are horizontal or vertical ).
Sample class structure
Implementing the tree traversal scheme
The structure can be maintained like this -- it consists of the file name , directory name(in which the present file/directory is included) ,size of the file and a date variable (for the function touch (last updated or viewed).
For each file first check for the directory (the user is expected to give the path for the file ). Go in to that directory and to inner directory if needed . Now we can access the record for the particaulr file.
Each time a file is accessed , the time stamp is replaced by the present date (use in built java functions). This takes care of the touch command.
To remove a file (the rm command) just remove the record of the file . For rmdir command however we need to see that all the files inside it are already removed . Else display an error message.
Similarly for mkdir command we create a new record for an empty directory.
Sample Class Structure
Step by step construction of binary tree
Easiest of the three problems . It consists of two parts -
(i)namely checking whether a valid tree can be constructed or not and
(ii) constrcting the tree if the answer to previous query is yes.
For the former part , create a function which finds out the tree out of the preorder and inorder traversals.
Since we know that the preorder follows the pattern NODE-LEFT-RIGHT and inorder LEFT-NODE-RIGHT it is easy to find out the root and then other nodes(recursively) too.
For the later part , we need to draw the tree nodes one at a time in an applet . So we can use a structure consisting of the values of node and the position of the node (which can be done by maintaining the two integers as the values for the coordinates).Now use a delay to display the nodes one at a time (i.e. as the tree is growing ). Alternatively use something like a mouse click or a button press to display the nodes .
Sample Class Structure