Binary search tree. BinaryTree class. Integers. Numbers can be repeated

This paper provides an example of developing a class that implements a binary search tree for integers (int). Following a similar pattern, you can develop other classes that implement a binary search tree.

Search other websites:

1. Task

Develop a binary search tree class containing the following methods (class API):

BinaryTree() – constructor – creates an empty tree;
void ShowSorted(string msg) – displays tree elements in sorted form;
void Put(int value) – adds an element to the tree;
~BinaryTree() – destructor (frees memory);
int Get(int value) – returns the number of occurrences of an element in the tree. If the element is not present, 0 is returned;
int Size() – returns the number of elements in the tree;
int* ToSortedArray() – converts the tree to a sorted array;
void Show(string msg) – display the tree in random order;
BinaryTree(const BinaryTree& obj) – copy constructor;
BinaryTree& operator=(const BinaryTree& obj) – copy operator.

⇑

2. Solution. Program text

To solve the problem, the method of recursive calling of the base methods of the class was chosen.

2.1. The declaration of the BinaryTree class

At the beginning, an empty class BinaryTree is declared

#include <iostream>
using namespace std;

// Binary search tree
class BinaryTree
{

};

⇑

2.2. Structure Node

The tree node is described by the structure shown in Figure 1.

Figure 1. Schematic representation of a binary search tree node

The program code of the Node is as follows

class BinaryTree
{
private:
  struct Node
  {
    int value;
    int count;
    Node* left;
    Node* right;
  };
};

⇑

2.3. Entering the internal fields of a class

A binary search tree starts at the root. In the program, this root corresponds to a variable called root.

The application also contains a method for converting a tree into a sorted array. Therefore, to save the array, two additional variables are introduced: the array and their size.

A binary search tree starts at the root. In the program, this root corresponds to a variable called root.

The application also contains a method for converting a tree into a sorted array. Therefore, to save the array, two additional variables are introduced: the array and their size.

class BinaryTree
{
private:

  ...

  Node* root; // tree root
  int* A;     // tree as a sorted array
  int size;   // array size

  ...

};

⇑

2.4. Constructor BinaryTree()

The constructor creates a tree that does not contain any elements.

class BinaryTree
{
  ...

  public:
    // Constructor - creates an empty tree
    BinaryTree()
    {
      root = nullptr;
      A = nullptr;
      size = 0;
    }
};

⇑

2.5. Method Put(Node*, int)

The Put() method implements adding a new element to the tree. The method has two overloaded implementations

private:
  Node* Put(Node* x, int value);

public:
  void Put(int value);

The first implementation in the private section is to directly add an element by recursively calling the Put() function. The second implementation in the public section is available to client code and refers to the first implementation.

// Binary search tree
class BinaryTree
{
private:

  ...

  Node* Put(Node* x, int value)
  {
    if (x == nullptr)
    {
      // Create node and return it
      Node* p = new Node;
      p->value = value;
      p->count = 1;
      p->left = nullptr;
      p->right = nullptr;
      return p;
    }

    if (value == x->value)
    {
      x->count++;
      return x;
    }

    if (value < x->value)
    {
      x->left = Put(x->left, value);
      return x;
    }

    if (value > x->value)
    {
      x->right = Put(x->right, value);
      return x;
    }
  }

public:
  // Adds an element to the tree
  void Put(int value)
  {
    // Call a recursive function
    if (root == nullptr)
      root = Put(root, value);
    else
      Put(root, value);
  }
};

⇑

2.6. Method ShowSorted(Node*)

The ShowSorted() method has a hidden (private) and public implementation

private:
  void ShowSorted(Node* x);

public:
  void ShowSorted(string msg)

The text of the method implementations is as follows:

// Binary search tree
class BinaryTree
{
private:

  ...

  // Displaying a tree in sorted form
  void ShowSorted(Node* x)
  {
    if (x == nullptr) return;
    if (x->left != nullptr)
      ShowSorted(x->left);

    cout << x->value << ":" << x->count << "  ";

    if (x->right != nullptr)
      ShowSorted(x->right);
  }

public:

  ...

  void ShowSorted(string msg)
  {
    cout << msg << " => ";
    ShowSorted(root);
    cout << endl;
  }
};

⇑

2.7. Method Free(Node*)

The recursive Free() method is called from the destructor and the copy assignment operator.

// Binary search tree
class BinaryTree
{
private:

  ...

  // Method that frees memory allocated for the array
  void Free(Node* x)
  {
    if (x == nullptr)
      return;
    if (x->left != nullptr)
      Free(x->left);
    if (x->right != nullptr)
      Free(x->right);
    delete x;
  }
};

⇑

2.8. Destructor

// Binary search tree
class BinaryTree
{

  ...

public:
  // Destructor
  ~BinaryTree()
  {
    // Free memory allocated for tree
    Free(root);

    // Free array A if it exists
    if (size > 0)
      delete[] A;
  }
};

⇑

2.9. Method Get(int)

The Get() method is designed to determine the number of occurrences of an element in the tree. If the method returns 0, it means that there is no element in the tree. Like all other similar class methods, the method is overloaded with two implementations: public and hidden (private). The hidden implementation defines an element by recursively calling a method.

// Binary search tree
class BinaryTree
{
private:

  ...

  Node* Get(Node* x, int value)
  {
    if (x == nullptr)
      return nullptr;
    if (value < x->value)
      return Get(x->left, value);
    else
    if (value > x->value)
      return Get(x->right, value);
    else
      return x;
  }

public:

...

  // Returns the number of occurrences of an element in the tree
  int Get(int value)
  {
    Node* p = Get(root, value);
    if (p == nullptr)
      return 0;
    return p->count;
  }
};

⇑

2.10. Method ToSortedArray()

The ToSortedArray() method is designed to convert a tree into a sorted array. The array is created in dynamic memory using the new operator. The internal class field named A is a pointer to the array. The size of the array is determined by the size field.

The ToSortedArray() method has two overloaded implementations in the private and public sections.

// Binary search tree
class BinaryTree
{
private:

  ...

  // Convert from binary tree to sorted array
  void ToSortedArray(Node* x, int* current)
  {
    if (x == nullptr)
      return;

    if (x->left != nullptr)
      ToSortedArray(x->left, current);

    // Take into account count
    for (int i = 0; i < x->count; i++)
    {
      A[*current] = x->value;
        (*current)++;
    }

    if (x->right != nullptr)
      ToSortedArray(x->right, current);
  }

public:
  // Converts a tree to a sorted array
  const int* ToSortedArray()
  {
    // 1. Get array size and allocate memory
    size = Size();
    A = new int[size];
    size = 0;
    ToSortedArray(root, &size);
    return A;
  }
};

⇑

2.11. Method Copy(Node**, Node*)

One of the operations on a tree is to get a copy of that tree. For this purpose, a special Copy() method is introduced into the class. This method is internal and is called from the copy constructor and copy assignment operator.

// Binary search tree
class BinaryTree
{
private:

  ...

  // The copying function *x_copy <= x
  void Copy(Node** x_copy, Node* x)
  {
    if (x == nullptr)
      return;

    // Make a copy of a node
    *x_copy = new Node;
    (*x_copy)->value = x->value;
    (*x_copy)->count = x->count;
    (*x_copy)->left = nullptr;
    (*x_copy)->right = nullptr;

    // Go to the next levels
    Copy(&(*x_copy)->left, x->left);
    Copy(&(*x_copy)->right, x->right);
  }

  ...
};

⇑

2.12. Copy constructor BinaryTree(const BinaryTree&)

The copy constructor is the technical part of the class and is needed in cases where you need to get a copy of an object when it is initialized with the value of another object.

// Binary search tree
class BinaryTree
{
private:

  ...

public:

  ...

  // Copy constructor
  BinaryTree(const BinaryTree& obj)
  {
    Copy(&root, obj.root);
  }

  ...

};

⇑

2.13. Copy operator operator=(const BinaryTree& obj)

The copy operator performs the same function as the copy constructor. Only in this case the receiving object already exists and it is overridden by another object.

// Binary search tree
class BinaryTree
{
  ...

public:

  ...

  // Copy operator
  BinaryTree& operator=(const BinaryTree& obj)
  {
    if (this != &obj) // is there no self-assignment?
    {
      // Free up pre-allocated memory
      Free(root);

      // Copy data
      Copy(&root, obj.root);
    }
    return *this;
  }
};

⇑

2.14. Method Show(). Display elements of the tree in random order

A special case of tree output is its output in the order in which elements are formed in it from top to bottom. This is an arbitrary order, which is determined by the input sequence that forms the tree.

The method has two implementations. The first is a hidden implementation that directly implements the output. The second implementation is public and can be called from client code.

// Binary search tree
class BinaryTree
{
private:

  ...

  // A function that prints a tree in random order
  void Show(Node* x)
  {
    if (x == nullptr)
      return;

    // Display the element
    cout << x->value << ":" << x->count << "  ";

    // Go to next nodes
    Show(x->left);
    Show(x->right);
  }

public:

  ...

  // Display the tree in arbitrary order
  void Show(string msg)
  {
    cout << msg << " => ";
    Show(root);
  }
};

⇑

2.15. Method Size(). Tree size

The Size() method returns the number of elements in the tree. Like all previous methods, this method has a hidden and public implementation.

// Binary search tree
class BinaryTree
{
private:

  ...

  int Size(Node* x)
  {
    if (x == nullptr) return 0;
    int count = 0;
    if (x->left != nullptr)
      count = count + Size(x->left);
    if (x->right != nullptr)
      count = count + Size(x->right);
    return count + x->count;
  }

public:

  ...

  // Returns the number of elements in the tree
  int Size()
  {
    return Size(root);
  }
};

// Binary search tree
class BinaryTree
{
private:

  ...

  int Size(Node* x)
  {
    if (x == nullptr) return 0;
    int count = 0;
    if (x->left != nullptr)
      count = count + Size(x->left);
    if (x->right != nullptr)
      count = count + Size(x->right);
    return count + x->count;
}

⇑

3. Test. The main() function

In the main() function, you can test the operation of the tree.

void main()
{
  // Create tree without elements
  BinaryTree BT;

  // Add elements to the tree
  BT.Put(10);
  BT.Put(8);
  BT.Put(8);
  BT.Put(17);
  BT.Put(11);
  BT.Put(11);
  BT.Put(11);
  BT.Put(23);
  BT.Put(5);
  BT.Put(12);

  // Display tree in sorted form
  BT.ShowSorted("BT");

  // Copy constructor test
  BinaryTree BT2 = BT;
  BT2.ShowSorted("BT2");

  // Copy operator test
  BinaryTree BT3;
  BT3 = BT2;
  BT3.Show("BT3");

  // Convert tree to array
  const int* A = BT3.ToSortedArray();

  // Display the sorted array
  cout << endl;
  for (int i = 0; i < BT3.Size(); i++)
    cout << A[i] << "  ";
  cout << endl;
}

⇑

4. Abbreviated program code

Below is a shorthand code of all class functions with their declarations without implementation.

#include <iostream>
using namespace std;

// Binary search tree
class BinaryTree
{
private:
  struct Node
  {
    ...
  };

  Node* root; // tree root
  int* A;     // tree as a sorted array
  int size;   // array size

  Node* Put(Node* x, int value)
  {
    ...
  }

  // Displaying a tree in sorted form
  void ShowSorted(Node* x)
  {
    ...
  }

  // Method that frees memory allocated for an array
  void Free(Node* x)
  {
    ...
  }

  Node* Get(Node* x, int value)
  {
    ...
  }

  int Size(Node* x)
  {
    ...
  }

  // Convert from binary tree to sorted array
  void ToSortedArray(Node* x, int* current)
  {
    ...
  }

  // Copy function *x_copy <= x
  void Copy(Node** x_copy, Node* x)
  {
    ...
  }

  // A function that prints a tree in random order
  void Show(Node* x)
  {
    ...
  }

public:
  // Constructor - creates an empty tree
  BinaryTree()
  {
    ...
  }

  void ShowSorted(string msg)
  {
    ...
  }

  // Adds an element to the tree
  void Put(int value)
  {
    ...
  }

  // Destructor
  ~BinaryTree()
  {
    ...
  }

  // Returns the number of occurrences of an element in the tree
  int Get(int value)
  {
    ...
  }

  // Convert tree to sorted array
  const int* ToSortedArray()
  {
    ...
  }

  // Returns the number of elements in the tree
  int Size()
  {
    ...
  }

  // Display tree randomly
  void Show(string msg)
  {
    ...
  }

  // Copy constructor
  BinaryTree(const BinaryTree& obj)
  {
    ...
  }

  // Copy operator
  BinaryTree& operator=(const BinaryTree& obj)
  {
    ...
  }
};

void main()
{
  ...
}