CSE 326, Spring 1995: Homework 4

Due 4/26/95

1. (10 points) Recall the adjaceny list representation of a graph. The vertices of the graph are numbered 1 to n. An array G[1..n] is formed where G[i] is the list nodes indicating the vertices adjacent to i. If G is an undirected graph then each edge (i,j) is represented twice with i on j's list and j on i's list. Recall also (from CSE 321) that a connected component of G is a maximal set X of vertices such that there is a path in G from any vertex in X to any other vertex in X,
   • Design an algorithm based on depth first search to label the connected components of G. Your algorithm should fill in an array C[1..n] with numbers 1,2,...,c where c is the number of connected components. You should have C[i] = C[j] if and only if i and j are in the same connected component.
   • Demonstrate your algorithm on the graph defined by the vertices {1,2,...,9} and edges (1,6), (2,3), (3,4) (2,5) (5,7), (6,8), (7,2), (8,1).
2. (20 points) It is often handy to store a binary tree in a file. Assume each node in the binary tree contains a character string. Assume also that all operations you need on strings are provided. For example, you do not need to design algorithms to test if a string equals ".", writes a string into a file, or reads a string from a file. To create the file in preorder file format do a preorder traversal of the tree, when a node is visited put the character string in the file followed by a newline and when a null is visited put a dot, ".", followed by a newline. For example, the tree

                              
                                 a
                               /   \
                              b     c
                             /    /   \
                            d    e     f
   

   is stored as the file "a b d . . . c e . . f . ." where spaces indicate newlines.
   • Design an algorithm which outputs the preorder file format of a binary tree given a pointer to the root of a binary tree. Assume the binary tree has nodes with fields "data", "left_child", and "right_child".
   • Design an algorithm which takes a preorder file format of a binary tree and produces the binary tree. Hint: an effective approach is to design a recursive function that processes a sequence of lines in a file and returns a binary tree.
   • Is there a similar file format based on postorder traversal? If not why not. If so, then explain how to modify the algorithm for producing the tree from the preorder file format to an algorithm for producing the tree from the postorder file format.
   • Is there a similar file format based on inorder traversal? If not why not. If so, then explain how to modify the algorithm for producing the tree from the preorder file format to an algorithm for producing the tree from the inorder file format.