Use C to implement serialization/marshalling/unloading/flattening of a red/black tree to a string

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

CSE 2320 Lab Assignment 4

Goals:

1. Understanding of red-black

2. Understanding of recursive binary tree

Requirements:

1. Use C to implement 1) serialization/marshalling/unloading/flattening of a red/black tree to a string and 2) the inverse operation of deserializing/unmarshalling/loading/unflattening a string to a red/black tree. Both operations are based on the recursive pre-order traversal of a binary tree.

The input is 1) the number of bytes in a string (including the NULL terminator), 2) a string no longer than the indicated length corresponding to a red-black tree, 3) n, the number of keys to be inserted into the tree, and 4) the n integers to be inserted into the tree.

The output is 1) the length (including the NULL terminator) of a string corresponding to the final red- black tree (after insertions) and 2) the string corresponding to the final red-black tree.

In the serialized version of a tree, . indicates the sentinel. Each key will be immediately followed by a letter r or b indicating its color. Optionally, a key may include a sign (+ or -). Three examples follow:

1. Submit all necessary C source files on Canvas by 10:45 am (section 004) or 1:45 pm (section 003) on November 14. Comments at the beginning of the source file should include: your name, your ID number, and the command used to compile your code on Omega (5 point penalty for non- compliance).

Getting Started:

1. Suitable driver and header files are available at http://ranger.uta.edu/~weems/NOTES2320/LAB/LAB4FALL19/ . c is available at http://ranger.uta.edu/~weems/NOTES2320/REDBLACKC/ .

2. You must use separate compilation. Do not merge together implementation and header

3. The string representing a red-black tree will be free of

4. Be sure your code does not leak memory. If you malloc() it, you are obligated to free()

5. You should check the deserialized tree either while building it or by using verifyRBproperties().

6. Your deserialization code should check the input string for errors. Characters past the end of a tree should result in a warning. Inappropriate characters elsewhere should result in a message and exit()

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of