COMPILERS / PROGRAM TRANSLATION Write a program to build dynamic (heap allocatio

Question

COMPILERS / PROGRAM TRANSLATION

Write a program to build dynamic (heap allocation with pointers) tree and print it using different traversals. The program will be invoked as

run [file]
in such a way that if the file is not specified the program will read the same data from the keyboard. If the argument is given, the program reads data file file.dat. (note that file is any name and the extension is implicit). Programs failing this convention will get max 50% if graded. Examples:

run //read from the keyboard until keyboard EOF

run < somefile // same as above except redirecting from somefile

run somefile // read from somefile.dat

run somefile.dat // read from somefile.dat.dat, or from somefile.dat if you verify correct extension (not required)

Assume the input data is all letters and digits, with standard WS separators

the input data will be stored in a tree based on the first character of each data using the ASCII value for ordering (lower and upper letters are not distinct)

If the file is not readable, the program will abort with an appropriate message

If the file is found to contain an invalid character, the program will abort with an appropriate message (what character) stating the line number on which it happened

Note: for 75% you may process the data into binary tree rather than the ternary extension described below. This will still require all project details other than the ternary extension. If time permits, you may then extend the tree or submit for 75%.

The program will read the data and put into into a ternary tree, which is an extension of the binary search tree (BST). First, the problem is described using BST, and then the BST is extended below

Problem description using BST simplificationThe program will read the file left to right and produce a BST with each node containing

the first character of data in the node

the list of data starting with the character, left to right as the data appears in the file

potential left and right subtree

Remember the left subtree only contains smaller data and the right subtree bigger data

Tree is never balanced or restructured other than growing new leaves and adding to the list of data in the nodes

The program will subsequently print all 3 traversals, in the following order, each starting with the traversal name (as below) followed by ":" followed by new line, followed by the traversal output. Traversals:

preorder

inorder

postoder

proper output means

one node printed per line

printing a node is printing the node's char followed by the list of strings in the node, all separated by spaces - after initial indentation equal to 2 x level (root at level=0)

Extension to ternary search tree

The left and middle subtrees must contain data smaller than a node, and the right subtree must contain larger data

The left subtree must be created before creating the middle subtree

The left subtree must contain data smaller than the middle subtree

Example (x is null pointer) using letters only
File names.dat:
hi hello hi me again hello apple brenda carla zebra
Invocation: > tree names

ternaryTree.docx

Output
Preorder
h: hi hello hi hello
a: again apple
b: brenda
c: carla
m: me
z: zebra
Inorder
etc.

Additional requirements:

You must have one source file main.c with the main driver, which only processes the argument, opens the file, calls another function to build the tree, and then calls the three traversals to print the tree. Bulding the tree (through one function) should be implemented in another source file buildTree.c. The display traversals (3 functions) are to be implemented in a third source file traversals.c. The tree is to be passed on the interface (as the root pointer), not global. That is, the interfaces are to be as follow (minimum, can extend arguments if needed):
node_t *buildTree(FILE *);
void traverseInorder(node_t*);
void traversePreorder(node_t*);
void traversePostorder(node_t*);

You must use appropriate header files (node.h, buildTree.h and traversals.h)

Use this functional architecture even if you program in a language different from C

Explanation / Answer

public class BinaryTreeTraversal {

   static class Node {
       Node left, right;
       int value;

       public Node(int value) {
           this.value = value;
       }
   }

   public static void traversePreOrder(Node root) {
       if (root == null) return;
       System.out.print(root.value + " ");
       traversePreOrder(root.left);
       traversePreOrder(root.right);
   }
  
   public static void traverseInOrder(Node root) {
       if (root == null)
           return;
       traverseInOrder(root.left);
       System.out.print(root.value + " ");
       traverseInOrder(root.right);
   }
  
   public static void traversePostOrder(Node root) {
       if (root == null) return;
       traversePostOrder(root.left);
       traversePostOrder(root.right);
       System.out.print(root.value + " ");
   }
  

   public static Node generateMinHeightBST(int[] vs, int start, int end) {
       if (end < start)
           return null;
       int mid = (start + end) / 2;
       Node node = new Node(vs[mid]);
       node.left = generateMinHeightBST(vs, start, mid - 1);
       node.right = generateMinHeightBST(vs, mid + 1, end);
       return node;
   }

   public static void printBinaryTree(Node root, int level) {
       if (root == null)
           return;
       printBinaryTree(root.right, level + 1);
       if (level != 0) {
           for (int i = 0; i < level - 1; i++) {
               System.out.print("| ");
           }
           System.out.println("|-------" + root.value);

       } else {
           System.out.println(root.value);
       }
       printBinaryTree(root.left, level + 1);
   }

   public static void main(String[] args) {
       int[] vs = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

       Node root = BinaryTreeTraversal.generateMinHeightBST(vs, 0, vs.length - 1);
       System.out.print("Traverse InOrder: ");
       BinaryTreeTraversal.traverseInOrder(root);
       System.out.println();
      
       System.out.print("Traverse PreOrder: ");
       BinaryTreeTraversal.traversePreOrder(root);
       System.out.println();
      
       System.out.print("Traverse PostOrder: ");
       BinaryTreeTraversal.traversePostOrder(root);
       System.out.println(" ");

       BinaryTreeTraversal.printBinaryTree(root, 0);

   }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.