This program is called: bstsort.c

This program will use:

  • structs, pointers, strings, and dynamic memory.
  • getopt for processing command line.
  • malloc/free functions for dynamically allocating and deallocating nodes and the buffer for strings.

This program will NOT use:

  • any libc string comparison funtions.
  • strcmp() and strcasecmp() functions.

This program will perform the following:

  • (1) Sorts the lines of an input file (or from standard input)
  • (2) print the sorted lines to an output file (or standard output).

This program will take the following command line arguments:

% bstsort [-c] [-o output_file_name] [input_file_name]

If -c is present, the program will compare the strings case sensitive.

Otherwise, its case insensitive.

If the output_file_name is given with the -o option, the program will output the sorted lines to the given output file.

otherwise, the output shall be the standard output.

Similarly, if the input_file_name is given, the program will read from the input file.

otherwise, the input will be from the standard input.

It will use getopt() to parse the command line arguments to determine the cases.

In addition to parsing and processing the command line arguments, this program will perform the following:

  • constructs a binary search tree as it reads from input.
  • each node will have at most two child nodes.
  • Either one or both can be empty.
  • If a child node exists, it is the root of a BST called subtree.
  • Each node contains a string.
  • If the left subtree of a node exists, it contains only nodes with strings greater than the nodes string.
  • In case of duplicate strings, this program uses a counter scheme.

NOTE: this program does not balance the BST.

Program's intended sequence:

  • Initially the tree is empty(root is null).
  • Program reads from the input file(or stdin) one line at a time.
  • If the line is not an empty line, it should create a tree node that stores a copy of the string.
  • Then it will remove the trailing line feed and then insert the tree node to the BST.
  • If a duplicate is found, it will simply increment the count and remove the new code.
  • As opposed to inserting the duplicate node.
  • An empty line would indicate the end of input for stdin.
  • An empty line or end of file would indicate the end of input for an input file.
  • In the situation where case insensitive is chosen, then it will use all lower case for the strings.
  • Once the program has read all the input, the program performs an in order traversal of the BST.
  • Then it prints out all the strings one line at a time to the output file or stdout.
  • Before the program ends it reclaims the tree by performing a post-order traversal.

Here's an example:

bash$ cat myfile
bob is working.
david is a new hire.
alice is bob's boss.
charles doesn't like bob.

bash$ ./bstsort myfile
alice is bob's boss.
bob is working.
charles doesn't like bob.
david is a new hire.

One should also be able to use './bstsort -o sortedfile < myfile' to take input from stdin (in this case, it's replaced by a file by the shell) and output the sorted lines in the output file (called sortedfile in the example).

Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.