questionWe noted that it is natural to model the organizati

. question:We noted that it is natural to model the organization of books, file systems or directories as trees. Suppose T is an ordered tree that describes a file system. That is, for each node v, v.element is the name of a subdirectory and all the items in the subdirectory are stored in the descendants of v. Write a pseudocode based on a tree traversal that prints out the file system in a linear fashion so that it looks like the table of contents of a book. More specifically, for any two nodes v and w

, • if v and w are siblings and v is to the left of w then v.element appears before w.element but both elements have the same indentation from the left margin; moreover, all the elements stored in the subtree of v appear before all the elements stored in the subtree of w

. • if v is an ancestor of w then v.element appears before w.element and v.element is closer to the left margin than w.element. For example, suppose T is the tree that appears in Figure 2.15 of your book.

Then the output of your algorithm should be: /user/rt/courses

cs016

grades

homeworks

hw1

hw2

hw3

programs

pr1

pr2

pr3

cs252/

projects

papers

buylow

sellhigh

demos

market

grades

usertteourses/ esote s016 cs252/ homeworksprograms projectsgrades papers/ demos/ buylow selihigh market Figure 2.15: A tree representing a portion of a file system.

Solution

We will need to use the preorder traversal method for this; in general the process would be:-

1.Visit and print the root.

2. Recursively traverse and print each sub-tree from left to right.

The structure of each node will be:-

struct Node{
   String data;
    Node* LeftmostChild;
   Node* RightSibling;
   int depth;
}

\'depth\' contains a number which tells us the level of the node in the tree. The root will have depth 0, all of its immediate children will have depth 1, all of their immediate children will ahve depth 2 and so on.

The following recursive function will print out the tree in pre-order. Before the data in the node is printed out, the \'depth\' variable is used to print spaces. So if the depth of a particular node is 2, two spaces will be printed out followed by the data stored in that node.

Function PrintNode(Node* Root){
   for i=0 to Root->depth{
       print \" \";
   }
   print Root->data;
   print \"\ \";
   Node* temp=Root->LeftmostChild;
   while(temp){
       PrintNode(temp);
       temp=temp->RightSibling;
   }
}