PROJECT: DOUBLY LINKED TREES (dlt0)

OBJECTIVE

Re-using our doubly-linked node structure to construct an ordered binary search tree.

TASK

By the deadline, please do the following:

• create a Tree management struct, containing a root Node pointer and a height integer
  • root points to the node at the top of the tree (NULL if empty)
  • height tracks the maximum height of the tree (an empty tree has a height of 0)
• implement the following Tree functions (each takes a Tree * as its first parameter, and returns the updated Tree *):
  • Tree *mktree ();
  • Tree *cleartree (Tree *);
  • Tree *rmtree (Tree *);
  • Tree *addnode (Tree *, Node *);
  • Tree *grabnode (Tree *, Node **);
  • Tree *traverse (Tree *, List *, int);
  • Tree *findnode (Tree *, Node **, int);
• test your tree implementation

BACKGROUND

A binary search tree is an ordered, hierarchical data structure: each node has up to two children, and the position of a node is determined by its value relative to the nodes already in the tree.

We will not be creating a new node type. The Node you built for your doubly-linked list already has two pointers, and we will simply give them new meaning:

• prev will point to the left child
• next will point to the right child

The ordering rule is as follows:

• values less than or equal to a node's value go into its left subtree
• values greater than a node's value go into its right subtree

Note that there is no parent pointer: your Node struct does not need to (and should not) change for this project. Functions that need to know about a node's parent will need to track it as they descend.

You are expected to continue making use of your existing node functions (mknode(), rmnode()) wherever they apply.

TREE STRUCT

Much like List and the others before it, Tree is a management layer: it gives us a reliable point of access to the tree (root), and a place to keep track of information about the tree as a whole (height).

MKTREE()

Like mklist(), except it focuses on creating a new, empty Tree instance. Allocate memory and do any error checking, ensuring root is set to NULL and height to 0.

On error, mktree() should return NULL.

CLEARTREE()

The purpose of cleartree() is to effectively and reliably empty a tree: every node in the tree is removed and deallocated (this will require visiting every node, so think carefully about the order in which you do it: don't free a node before you are done with its children).

An empty tree is returned, or NULL on some sort of error state.

RMTREE()

The purpose of rmtree() is to empty and deallocate a given tree, returning a NULL value at the end.

You can pass a populated tree to rmtree(): it is rmtree()'s job to call other routines to clear out the tree before deallocating the tree pointer in question.

ADDNODE()

Places the provided node into its proper position in the tree, according to the ordering rule (value <= goes to the left subtree, otherwise right).

The parameters are as follows:

• pointer to the tree
• pointer to the node you'd like to add to the tree

A pointer to the tree is returned.

Be sure to handle the case of an empty tree (the new node becomes the root), and to keep height up to date as the tree grows.

You should check to make sure the involved things are not NULL (as a segmentation fault would occur otherwise).

GRABNODE()

To get a node out of the tree, we grabnode() it. This function will isolate a node from the tree, maintaining the ordering of the remaining nodes.

The parameters are as follows:

• pointer to the tree
• double pointer to the node you'd like to grab

A pointer to the tree is returned, and the double pointer will reference the now-isolated node (its prev and next pointers should be NULL).

There are three scenarios you will need to account for:

• the node has no children (a leaf): simply remove it
• the node has one child: that child takes its place
• the node has two children: the greatest value in its left subtree is promoted to take its place

Be mindful of grabbing the root node (the tree's root pointer must be updated), and be sure to keep height accurate afterwards.

TRAVERSE()

Recursively traverses the tree, building a list of the nodes in the order visited.

The parameters are as follows:

• pointer to the tree
• pointer to the list the results will be placed into
• integer indicating the traversal order:
  • inorder (left, node, right)
  • preorder (node, left, right)
  • postorder (left, right, node)

You will want to define meaningful names for the three traversal orders (constants, #define, or enum) instead of passing around bare numbers.

A pointer to the tree is returned.

Because the nodes in the tree are using their prev and next pointers for tree connections, the list must be populated with new nodes (created with mknode()) containing copies of each value. The tree itself must remain unchanged by a traversal. The caller is responsible for the resulting list.

Hint: an inorder traversal of a binary search tree will yield its values in sorted order.

FINDNODE()

Locates the first match of a value within the tree.

The parameters are as follows:

• pointer to the tree
• double pointer which will be set to the node found
• the integer value being sought

A pointer to the tree is returned. If the value is not found, the node double pointer is set to NULL. The tree is not modified, and the located node is not removed from the tree.

Remember that the tree's ordering rule means you do not need to look at every node: use it to decide which way to descend.

SUBMISSION

208:dlt0:final tally of results (208/208)
*:dlt0:create tree struct [13/13]
*:dlt0:create and test mktree function [13/13]
*:dlt0:create and test cleartree function [13/13]
*:dlt0:create and test rmtree function [13/13]
*:dlt0:create and test addnode function [26/26]
*:dlt0:create and test grabnode function [26/26]
*:dlt0:create and test traverse function [26/26]
*:dlt0:create and test findnode function [26/26]
*:dlt0:tree height is accurately maintained [26/26]
*:dlt0:code is well commented, organized, functional [26/26]

Additionally:

• Solutions not abiding by spirit of project will be subject to a 25% overall deduction
• Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
• Solutions not utilizing indentation to promote scope and clarity will be subject to a 25% overall deduction
• Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction