BinarySearchTrees

This repository contains C functions for working with Binary Search Trees (BST), specifically:

• Create a BST
• Destroy it
• Print it
• Search an element
• Add an element
• Remove an element
• Remove a subtree

Table of Contents

• Structures
• Functions
  • BST_create
  • BST_insert
  • BST_delete
  • BST_destroy
  • BST_search
  • Printing Functions
    • inorder
    • preOrder
    • postOrder
• Main Function

Structures

typedef struct tree* tree_pointer;

struct tree {
    int key;                // content of the node
    tree_pointer dx;        // pointer to the right child
    tree_pointer sx;        // pointer to the left child
};

Functions

BST_create

tree_pointer BST_create();

Creates an empty Binary Search Tree.

Input:

• None

Output:

• tree_pointer: Pointer to the root of the newly created tree.

BST_insert

tree_pointer BST_insert(tree_pointer T, int key);

Inserts a node with the given key into the Binary Search Tree.

Input:

• tree_pointer T: Pointer to the tree to which the node is to be added.
• int key: Content of the node to be added.

Output:

• tree_pointer: Pointer to the modified tree.

BST_delete

tree_pointer BST_delete(tree_pointer T, int key);

Deletes the node with the given key from the Binary Search Tree.

Input:

• tree_pointer T: Pointer to the root of the tree from which an element is to be deleted.
• int key: Key of the element to be deleted.

Output:

• tree_pointer: Pointer to the modified tree.

BST_destroy

void BST_destroy(tree_pointer T);

Destroys the entire Binary Search Tree.

Input:

• tree_pointer T: Pointer to the tree to deallocate.

Output:

• None

BST_search

int BST_search(tree_pointer T, int k);

Searches for an element with the given key in the Binary Search Tree.

Input:

• tree_pointer T: Pointer to the root of the tree to search in.
• int k: Key to search for.

Output:

• int:
  • 0: The tree does not contain the searched key.
  • 1: The tree contains the searched key.

Printing Functions

inorder

void inorder(tree_pointer T);

Prints the Binary Search Tree in symmetric order.

Input:

• tree_pointer T: Tree to print.

Output:

• None

preOrder

void preOrder(tree_pointer T);

Prints the Binary Search Tree in preorder.

Input:

• tree_pointer T: Tree to print.

Output:

• None

postOrder

void postOrder(tree_pointer T);

Prints the Binary Search Tree in postorder.

Input:

• tree_pointer T: Tree to print.

Output:

• None

Example:

Inserted keys: 5, 7, -3, 1

Tree structure:

Print the tree in Symmetric order:

-3| 1| 5| 7|

Print the tree in Post order:

1| -3| 7| 5| 

Print the tree in Pre order:

5| -3| 1| 7|

Main Function

The main function provides a command-line interface for interacting with the Binary Search Tree. It allows users to perform operations such as insertion, deletion, searching, and printing of the tree.

For a more detailed understanding of the functions, you can refer to the comments within the code.

Authors

Luigi Emanuele Zippo and Pietro Peluso