2
Contributors
1
Reply
3
Views
4 Years
Discussion Span
Last Post by Gonbe
0

A while ago I started to made a couple of simple tree-operations for a BST. It was made for C though and it wasn't quite finished yet. Function descriptions and such are missing and the final interface is missing. I also wanted to add a mechanism to add variable node content but didn't get to do it. Anyway, it contains insertion and the code itself is commented well enough I think:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int NodeValue;

struct Node
{
    NodeValue    value;
    struct Node* left;
    struct Node* right;
};

struct Queue
{
    const struct Node* node;
    struct Queue* next;
};


// Tree operation functions.
bool               Insert             (const NodeValue value, struct Node** const tree);
void               Delete             (const NodeValue value, struct Node** const tree);
const struct Node* Search             (const struct Node* const tree, const NodeValue value);
bool               Min                (const struct Node* const tree, NodeValue* const value);
bool               Max                (const struct Node* const tree, NodeValue* const value);
const struct Node* InOrderSuccessor   (const struct Node* tree);
const struct Node* InOrderPredecessor (const struct Node* tree);
int                CountDescendants   (const struct Node* const tree);
bool               NodesOnLevel       (struct Node* const tree, const int level, struct Queue** const queue);

// Traversal functions.
void               PreOrderTraversal  (const struct Node* const tree, void (*callback)(const void* const));
void               InOrderTraversal   (const struct Node* const tree, void (*callback)(const void* const));
void               PostOrderTraversal (const struct Node* const tree, void (*callback)(const void* const));
bool               LevelOrderTraversal(      struct Node* const tree, void (*callback)(const void* const));

// Tree property functions.
int                Height             (const struct Node* const tree);
int                Size               (const struct Node*       tree, const NodeValue value);
int                NodeDepth          (const struct Node*       tree, const NodeValue value);

// Node property functions.
bool               IsLeaf             (const struct Node* const tree);
bool               IsAncestor         (const struct Node* const tree, const NodeValue ancestor,   const NodeValue descendant);
bool               IsDescendant       (const struct Node* const tree, const NodeValue descendant, const NodeValue ancestor);
bool               AreSiblings        (const struct Node* const tree,       NodeValue left,             NodeValue right);

// Helper/test functions used locally.
static void        Swap               (NodeValue* lvalue, NodeValue* rvalue);
static NodeValue   Highest            (NodeValue  lvalue, NodeValue  rvalue);
static void        Print              (const struct Node* const tree);
static bool        Enqueue            (struct Queue** const queue, const struct Node* const node);
static void        Dequeue            (struct Queue** const queue);
static void        RemoveQueue        (struct Queue** const queue);


bool Insert(const NodeValue value, struct Node** const tree)
{
    // The tree is empty.
    if ((*tree) == NULL)
    {
        // Dynamically allocate the new node.
        (*tree) = (struct Node*) malloc(sizeof(struct Node));

        // Allocation was successful.
        if ((*tree) != NULL)
        {
            // Assign the values to the members.
            (*tree)->value = value;
            (*tree)->left  = NULL;
            (*tree)->right = NULL;
        }
    }

    // The value belongs in the left subtree.
    else if (value < (*tree)->value)
    {
        return Insert(value, (&(*tree)->left));
    }

    // The value belongs in the right subtree.
    else if (value > (*tree)->value)
    {
        return Insert(value, (&(*tree)->right));
    }

    // If memory allocation failed, return false, otherwise return true.
    return ((*tree) != NULL);
}


static bool Enqueue (struct Queue** const queue, const struct Node* const node)
{
    // There current queue position is empty, insert it here.
    if ((*queue) == NULL)
    {
        // Dynamically allocate the queue item.
        (*queue) = (struct Queue*) malloc (sizeof(struct Queue));

        // Dynamic allocation did not fail.
        if (*queue != NULL)
        {
            // Set the values.
            (*queue)->next = NULL;
            (*queue)->node = node;
        }
    }
    else
    {
        // The current position is occupied. Try to enqueue it at the next position.
        return Enqueue(&((*queue)->next), node);
    }

    // Return true if allocation succeeded, false otherwise.
    return ((*queue) != NULL);
}


static void RemoveQueue (struct Queue** const queue)
{
    // While there is something to dequeue, do it!
    while ((*queue) != NULL)
    {
        Dequeue(queue);
    }
}


static void Dequeue (struct Queue** const queue)
{
    // Only dequeue something, if there is something to dequeue!
    if ((*queue) != NULL)
    {
        // Temporarily store a pointer to the remains of the queue.
        struct Queue* temp = (*queue)->next;

        // Free the front queue item.
        free(*queue);

        // Set the remainder of the queue as the new queue.
        (*queue) = temp;
    }
}


bool LevelOrderTraversal(struct Node* const tree, void (*callback)(const void* const))
{
    struct Queue* queue   = NULL;
    bool          success = true;

    // If there is no tree to traverse we're done quickly..
    if (tree != NULL)
    {
        // Enqueue the head node.
        success = Enqueue(&queue, tree);

        // As long as there's anything in the queue..
        while (queue != NULL && success)
        {
            // Call the supplied callback for the front item.
            callback(queue->node);

            // If the current node has a left child..
            if (queue->node->left != NULL)
            {
                // Enqueue this child.
                success = Enqueue(&queue, queue->node->left);
            }

            // If the current node has a right child..
            if (queue->node->right != NULL)
            {
                // Enqueue this child.
                success = Enqueue(&queue, queue->node->right);
            }

            // We're done processing the current node. Dequeue (remove) it.
            Dequeue(&queue);
        }

        // The list might still contain items if allocation issues occurred.
        RemoveQueue(&queue);
    }

    return success;
}


// All nodes at depth x = level x. Depth 0, 1, 2, 3 ...
bool NodesOnLevel(struct Node* const tree, const int level, struct Queue** const queue)
{
    // An empty tree will result in an empty list.
    if (tree != NULL)
    {
        // Nodes at depth 0 are required, that is the root of the tree.
        if (level <= 0)
        {
            return Enqueue(queue, tree);
        }
        // A deeper level was requested.
        else
        {
            return (NodesOnLevel(tree->left,  level - 1, queue) && NodesOnLevel(tree->right, level - 1, queue));
        }
    }

    return (tree == NULL);
}


void PostOrderTraversal(const struct Node* const tree, void (*callback)(const void* const))
{
    // There is nothing to traverse for an empty tree.
    if (tree != NULL)
    {
        // If a left subtree exists..
        if (tree->left != NULL)
        {
            //..traverse it.
            PostOrderTraversal(tree->left, callback);
        }

        // Then, if a right subtree exists..
        if (tree->right != NULL)
        {
            //..traverse it.
            PostOrderTraversal(tree->right, callback);
        }

        // And finally call the supplied callback for the current node.
        callback(tree);
    }
}


void PreOrderTraversal(const struct Node* const tree, void (*callback)(const void* const))
{
    // There is nothing to traverse for an empty tree.
    if (tree != NULL)
    {
        // First, call the supplied callback for the current node.
        callback(tree);

        // Then, if a left subtree exists..
        if (tree->left != NULL)
        {
            //..traverse it.
            PreOrderTraversal(tree->left, callback);
        }

        // And finally, if a right subtree exists..
        if (tree->right != NULL)
        {
            //..traverse it.
            PreOrderTraversal(tree->right, callback);
        }
    }
}


void InOrderTraversal(const struct Node* const tree, void (*callback)(const void* const))
{
    // There is nothing to traverse for an empty tree.
    if (tree != NULL)
    {
        // If a left subtree exists..
        if (tree->left != NULL)
        {
            //..traverse it.
            InOrderTraversal(tree->left, callback);
        }

        // Then call the supplied callback for the current node.
        callback(tree);

        // And finally, if a right subtree exists..
        if (tree->right != NULL)
        {
            //..traverse it.
            InOrderTraversal(tree->right, callback);
        }
    }
}


void Delete(const NodeValue value, struct Node** const tree)
{
    struct Node*  child     = NULL;
    struct Node** successor = NULL;

    // There is nothing to delete on an empty tree.
    if ((*tree) != NULL)
    {
        // The current node is the one we wish to delete.
        if ((*tree)->value == value)
        {
            // It has no childs!
            if (IsLeaf(*tree))
            {
                // Simply delete the node.
                free(*tree);
                (*tree) = NULL;
            }

            // It has a right child only.
            else if ((*tree)->left == NULL)
            {
                // Replace this node with its right child.
                child = (*tree)->right;
                free(*tree);
                (*tree) = child;
            }

            // It has a left child only.
            else if ((*tree)->right == NULL)
            {
                // Replace this node with its left child.
                child = (*tree)->left;
                free(*tree);
                (*tree) = child;
            }

            // It has two children.
            else
            {
                // Obtain the in-order successor node.
                for (successor = tree; (*successor)->left != NULL; successor = &((*successor)->left));

                // Replace the node we want to delete's value with the one of the in-order successor node.
                (*tree)->value = (*successor)->value;

                // And then delete this successor node. (It has 0 or 1 child, but can't have two)
                Delete((*successor)->value, successor);
            }
        }
        // The current node has a higher value than we are looking for.
        else if (value < (*tree)->value)
        {
            // Look in its left subtree.
            Delete(value, &((*tree)->left));
        }
        // The current node has a lower value than we are looking for.
        else
        {
            // Look in its right subtree.
            Delete(value, &((*tree)->right));
        }
    }
}


const struct Node* Search(const struct Node* const tree, const NodeValue value)
{
    // There is nothing to find, because there is no tree.
    if (tree == NULL)
    {
        return NULL;
    }

    // We found the node we were looking for!
    else if (tree->value == value)
    {
        return tree;
    }

    // The current node has a higher value than we are looking for, look in the left subtree.
    else if (value < tree->value)
    {
        return Search(tree->left, value);
    }

    // The current node has a lower value than we are looking for, look in the right subtree.
    else
    {
        return Search(tree->right, value);
    }
}


const struct Node* InOrderPredecessor(const struct Node* tree)
{
    // There is nothing to find, because there is no tree.
    if (tree == NULL || tree->left == NULL)
    {
        return NULL;
    }

    // Obtain the left subtree and
    // find the right-most child in this tree.
    for (tree = tree->left; tree->right != NULL; tree = tree->right);

    return tree;
}


const struct Node* InOrderSuccessor(const struct Node* tree)
{
    // There is nothing to find, because there is no tree.
    if (tree == NULL || tree->right == NULL)
    {
        return NULL;
    }

    // Obtain the right subtree and
    // find the left-most child in this tree.
    for (tree = tree->right; tree->left != NULL; tree = tree->left);

    return tree;
}


bool Min(const struct Node* const tree, NodeValue* const value)
{
    // The minimum can not be found in an empty tree.
    if (tree != NULL)
    {
        // Lower values are in the left side by definition.
        if (tree->left == NULL)
        {
            // If there is no left subtree, we've found the lowest!
            (*value) = tree->value;
        }
        else
        {
            // There is a left subtree, look for the minimum value there.
            return Min(tree->left, value);
        }
    }

    // Return false if an empty tree was supplied, true otherwise.
    return (tree != NULL);
}


bool Max(const struct Node* const tree, NodeValue* const value)
{
    // There is no maximum value in an empty tree.
    if (tree != NULL)
    {
        // Higher values are in the right subtree by definition.
        if (tree->right == NULL)
        {
            // There is no right subtree, so this is the highest value!
            (*value) = tree->value;
        }
        else
        {
            // There is a right subtree, look for the highest value there.
            return Max(tree->right, value);
        }
    }

    // Return false if the supplied tree was empty, true otherwise.
    return (tree != NULL);
}


int Height(const struct Node* const tree)
{
    // If there is no tree, or it's a tree without children, its height is 0.
    if (tree == NULL || IsLeaf(tree))
    {
        return 0;
    }
    // Otherwise the current node adds 1 to the height and the remaining height is the highest of its two children.
    else
    {
        return 1 + Highest(Height(tree->left), Height(tree->right));
    }
}


bool IsLeaf (const struct Node* const tree)
{
    // En empty tree is no leaf, and a node is a leaf when it has no children.
    return (tree != NULL && tree->left == NULL && tree->right == NULL);
}


bool AreSiblings (const struct Node* const tree, NodeValue left, NodeValue right)
{
    // An empty tree cannot contain siblings and a node can't be its own sibling.
    if (tree != NULL && left != right)
    {
        // Ensure that left is smaller than right.
        if (left > right)
        {
            Swap(&left, &right);
        }

        // The current node's value is bigger than the right sibling.
        if (tree->value > right)
        {
            // This means we should be looking in its left sub-tree.
            return AreSiblings(tree->left, left, right);
        }
        // The current node's value is smaller than the left sibling.
        else if (tree->value < left)
        {
            // This means we should be looking in its right sub-tree.
            return AreSiblings(tree->right, left, right);
        }

        //The value of the current node is in between our left and right sibling.
        else if (tree->value > left && tree->value < right)
        {
            // This means it has to be here if anywhere.
            // If it doesn't have two children there's no siblings to even start comparing.
            if (tree->left == NULL || tree->right == NULL)
            {
                return false;
            }
            // There are 2 children.
            else
            {
                // Return true if these match the siblings requested, else false.
                return (tree->left->value = left && tree->right->value == right);
            }
        }
    }

    return false;
}


int NodeDepth (const struct Node* tree, const NodeValue value)
{
    int depth = 0;

    while (tree != NULL && tree->value != value)
    {
        // We need to look at a deeper depth.
        depth++;

        // the value we're looking for is in the left subtree.
        if (value < tree->value)
        {
            tree = tree->left;
        }

        // The value we're looking for is in the right subtree.
        else
        {
            tree = tree->right;
        }
    }

    // No node was found with the supplied value.
    if (tree == NULL)
    {
        return -1;
    }
    else
    {
        return depth;
    }
}


static void Print (const struct Node* const tree)
{
    // Simply print the value of a node, surrounded by [].
    if (tree != NULL)
    {
        printf("[%d]", tree->value);
    }
}


static NodeValue Highest (const NodeValue lvalue, const NodeValue rvalue)
{
    return (lvalue > rvalue) ? lvalue : rvalue;
}


static void Swap (NodeValue* const lvalue, NodeValue* const rvalue)
{
    NodeValue temp  = (*lvalue);
    (*lvalue)       = (*rvalue);
    (*rvalue)       = temp;
}


bool IsAncestor (const struct Node* const tree, const NodeValue ancestor, const NodeValue descendant)
{
    // Look for the ancestor in the tree and then look for the descendant in the resulting (sub)tree.
    return (Search(Search(tree, ancestor), descendant) != NULL);
}


bool IsDescendant (const struct Node* const tree, const NodeValue descendant, const NodeValue ancestor)
{
    // Asking if "a is the descendant of b" is the same as asking "is b the ancestor of a".
    return IsAncestor(tree, ancestor, descendant);
}


int CountDescendants (const struct Node* const tree)
{
    // An empty tree or a leaf node have no descendants.
    if (tree == NULL || IsLeaf(tree))
    {
        return 0;
    }
    else
    {
        // Every child counts as one descendant and then count their descendants.
        return ((tree->left != NULL) + (tree->right != NULL) + CountDescendants(tree->left) + CountDescendants(tree->right));
    }
}


int Size (const struct Node* tree, const NodeValue value)
{
    // Look for the node we're looking for.
    tree = Search(tree, value);

    // The node we wish to know the size of is found.
    if (tree != NULL)
    {
        // This node itself counts, and every node underneath it.
        return 1 + CountDescendants(tree);
    }
    else
    {
        // The requested node was not found, specify this is size 0.
        return 0;
    }
}


int main(void)
{
    struct Node*  tree  = NULL;

    // Do stuff with the tree

    return 0;
}

Heading Here

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.