temelia/release/include/binary_tree.h

/*!
 Temelia - Binary tree interface.

 Copyright (C) 2008, 2009 Ceata

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef BINARYTREE_H_
#define BINARYTREE_H_

#include "platform.h"
#include "binary_tree_common.h"

/*!
 * @brief Constructor - creates a empty tree. Call with NULL if you want an empty tree.
 * Complexity O(1)
 *
 * @param Key
 */
DECLSPEC binary_tree_t binary_tree_new(void *key);

/*!
 * @brief Destructor - frees the memory occupied by the root node. It's useful when
 * the tree contains only one node.
 * Complexity O(1)
 *
 * @param Binary tree
 */
DECLSPEC void binary_tree_delete_node(binary_tree_node_t node);

/*!
 * @brief Destructor - frees the memory occupied by a tree.
 * Complexity O(size)
 *
 * @param Binary tree
 */
DECLSPEC void binary_tree_delete(binary_tree_t tree);

/*!
 * @brief Compares two binary trees. It return 0 if they are equal and another value if they aren't,
 * depending on the comparison function.
 * Complexity O(max(size1, size2))
 *
 * @param Pointer to first binary tree
 * @param Pointer to second binary tree
 * @param Pointer to comparison function
 */
DECLSPEC int binary_tree_compare_trees(binary_tree_t bt1, binary_tree_t bt2,
		int compare(void *x, void *y, void *context), void *context);

/*!
 * @brief Checks if tree is empty.
 * Complexity O(1)
 *
 * @param Binary tree
 */
DECLSPEC int binary_tree_is_empty(binary_tree_t tree);

/*!
 * @brief Checks if node is leaf.
 * Complexity O(1)
 *
 * @param Binary tree node
 */
DECLSPEC int binary_tree_is_leaf(binary_tree_t node);

/*!
 * @brief Returns the nodes number of tree.
 * Complexity O(size)
 *
 * @param Binary tree
 */
DECLSPEC int binary_tree_get_size(binary_tree_t tree);

/*!
 * @brief Returns root of a tree which contains node.
 * Complexity O(size)
 *
 * @param Binary tree
 */
DECLSPEC binary_tree_t binary_tree_get_root(binary_tree_t node);

/*!
 * @brief Returns the key contained by node.
 * Complexity O(1)
 *
 * @param Binary tree node
 */
DECLSPEC void *binary_tree_get_key(binary_tree_t node);

/*!
 * @brief Sets the key of node.
 * Complexity O(1)
 *
 * @param Binary tree node
 * @param Key
 */
DECLSPEC void binary_tree_set_key(binary_tree_t node, void *key);

/*!
 * @brief Returns the parent of node.
 * Complexity O(1)
 *
 * @param Binary tree node
 */
DECLSPEC binary_tree_t binary_tree_get_parent(binary_tree_t node);

/*!
 * @brief Sets parent_node to be the parent of node.
 * If dir=-1 then node will be the left child of parent
 * else if dir=1 node will be the it's right child.
 * Complexity O(1)
 *
 * @param Child binary tree node.
 * @param Parent binary tree node
 * @param Direction
 */
DECLSPEC void binary_tree_set_parent(binary_tree_t node, binary_tree_t parent, int dir);

/*!
 * @brief Returns left child of node.
 * Complexity O(1)
 *
 * @param Binary tree node
 */
DECLSPEC binary_tree_t binary_tree_get_left_child(binary_tree_t node);

/*!
 * @brief Sets left child of node.
 * Complexity O(1)
 *
 * @param Binary tree node
 * @param Child binary tree node
 */
DECLSPEC void binary_tree_set_left_child(binary_tree_t node, binary_tree_t child);

/*!
 * @brief Returns right child of node.
 * Complexity O(1)
 *
 * @param Binary tree node
 */
DECLSPEC binary_tree_t binary_tree_get_right_child(binary_tree_t node);

/*!
 * @brief Sets right child of node.
 * Complexity O(1)
 *
 * @param Binary tree node
 * @param Child node
 */
DECLSPEC void binary_tree_set_right_child(binary_tree_t node, binary_tree_t child);

/*!
 * @brief Joins two trees called left and right into a single tree called parent.
 * Complexity O(1)
 *
 * @param Parent binary tree
 * @param Right binary tree
 * @param Left binary tree
 */
DECLSPEC void binary_tree_join(binary_tree_t parent, binary_tree_t left,
		binary_tree_t right);

/*!
 * @brief Splits a tree into two trees.
 * Complexity O(1)
 *
 * @param Current tree
 * @param Left binary tree
 * @param Right binary tree
 */
DECLSPEC void binary_tree_split(binary_tree_t parent, binary_tree_t *left,
		binary_tree_t *right);

/*!
 * @brief Creates a new node containing key, with children nodes left and right and with
 * parent node parent. If dir == -1 then the new node will be parent's left child, else
 * if dir == 1 the new node will be parent's right child.
 * Complexity O(1)
 *
 * @param Parent binary tree node
 * @param Left binary tree child
 * @param Right binary tree child
 * @param Key
 * @param Direction
 */
DECLSPEC binary_tree_t binary_tree_create_node(binary_tree_t parent, binary_tree_t left,
		binary_tree_t right, void *key, int dir);

/*!
 * @brief Returns the height of tree.
 * Complexity O(size)
 *
 * @param Binary tree
 */
DECLSPEC int binary_tree_get_height(binary_tree_t tree);

/*!
 * @brief Returns the depth of node, in a tree.
 * Complexity O(size)
 *
 * @param Binary tree node
 */
DECLSPEC int binary_tree_get_depth(binary_tree_t node);

/*!
 * @brief Preorder : Root Left Right.
 * Complexity O(size)
 *
 * @param Binary tree
 * @param Pointer to iterating function
 * @param Context
 */
DECLSPEC void binary_tree_preorder(binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @brief Inorder : Left Root Right.
 * Complexity O(size)
 *
 * @param Binary tree
 * @param Pointer to printing function
 * @param Context
 */
DECLSPEC void binary_tree_inorder(binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @brief Reverse inorder : Right Root Left.
 * Complexity O(size)
 *
 * @param Binary tree
 * @param Pointer to printing function
 * @param Context
 */
DECLSPEC void binary_tree_reverse_inorder(binary_tree_t tree, void key_handler(
		void *key, void *context), void *context);

/*!
 * @brief Postorder : Left Right Root.
 * Complexity O(size)
 *
 * @param Binary tree
 * @param Pointer to printing function
 * @param Context
 */
DECLSPEC void binary_tree_postorder(binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @brief Level order.
 * Complexity O(size)
 *
 * @param Binary tree
 * @param Pointer to printing function
 * @param Context
 */
DECLSPEC void binary_tree_level_order(binary_tree_t tree, void key_handler(void *key,
		void *context), void *context);

/*!
 * @brief Indented show.
 * Complexity O(size)
 *
 * @param Binary tree
 * @param Pointer to printing function
 * @param Context
 */
DECLSPEC void binary_tree_show_indented(binary_tree_t tree, void key_handler(void *key,
		int level, void *context), void *context);

#endif /* BINARY_TREE_H */