can anyone give a hint in Complete Binary Tree Insertion ?????
Gujjar007 0 Newbie Poster
Gonbe 32 Newbie Poster
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
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.