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.

Contents

Search other websites:

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()
{
...
}```