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,
  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
                                /   \
                               b     c
                              /    /   \
                             d    e     f
    is stored as the file "a b d . . . c e . . f . ." where spaces indicate newlines.