COM2067 Lab 8 Solved

Write a C program that sorts the given integer values. The number of values is not known in advance. Your program will output the sorted values and the structure of the tree using given output format. (Assume for this homework study, values are distinct). Use red-black tree in your program.

Input:

45 95 35 55 85 25 15 65 75 -1

Your output will be the sorted list of given numbers (In-order walk on red-black tree produce the sorted list).

Your program should print the red-black tree in the following way (First number represents the value, the letter displays the color (R for red and B for black) and the number and the letter in parenthesis shows the parent node. L represents left child and R represents right child). Null nodes (leaf nodes) will not be printed.

45 B
25 B (45 L) 85 R (45 R)
15 R (25 L) 35 R (25 R) 65 B (85 L) 95 B (85 R) 55 R (65 L) 75 R (65 R)

Output:

15
25
35
45
55
65
75
85
95

45 B
25 B (45 L) 85 R (45 R)
15 R (25 L) 35 R (25 R) 65 B (85 L) 95 B (85 R) 55 R (65 L) 75 R (65 R)