How do you write c plus plus program to insert an element into a binary search tree?

Answer 1

Binary Search is an algorithm that finds an element by successively halving the search space. Typically, pointers are used, one for the beginning of an array, one for the end. Then a midpoint pointer is chosen, and a test is performed. You either find the element, or you discover that the target element is before or after the midpoint. You then adjust either the start pointer or the end pointer and you iterate. When you reach the point where the pointers are out of order, you conclude that the target is not found, and you also know where to insert it. Binary Search is best implemented with an ordered array, because you want to make "random" access to each element. The problem with arrays is that they are typically fixed size, and must be dynamically adjusted when they need to grow, a potentially "expensive" operation. You can also implement a Binary Tree, but there is cost in development and processing. Even trees have issues because, when inserting and deleting elements, you must use a rebalancing algorithm, otherwise the tree might degrade to a linked list, which is not efficient when used as a search space. In C++, it is possible to declare and define a class of elements that you can add to, subtract from, and search. If you do this correctly, you could start with a static or dynamic array, and then upgrade if need be to a binary tree, and then upgrade if need be to a balanced binary tree, all the while without requiring change to the public interface. That is perhaps the most important value of an Object Oriented Language such as C++.

Answer 2

#include<iostream>

template<typename T>

struct node

{

T data;

node* left {nullptr};

node* right {nullptr};

node (const T& value): data (value) {}

~node () { delete left; delete right; }

void insert (const T& value)

{

if (value < data)

{

if (left)

left->insert (value);

else

left = new node (value);

}

else

{

if (right)

right->insert (value);

else

right = new node (value);

}

}

};

template<typename T>

struct bin_tree

{

node<T>* root {nullptr};

~bin_tree () { delete root; }

void insert (const T& value)

{

if (!root)

root = new node<T> (value);

else

root->insert (value);

}

};

template<typename T>

std::ostream& operator<< (std::ostream& os, const node<T>& n)

{

if (n.left) os << (*n.left);

os << n.data << ' ';

if (n.right) os << (*n.right);

return os;

}

template<typename T>

std::ostream& operator<< (std::ostream& os, const bin_tree<T>& t)

{

if (t.root)

return os << (*t.root);

return os;

}

int main()

{

int arr[10] = {42, 56, 30, 5, 12, 60, 40, 8, 1, 99};

bin_tree<int> tree;

for (size_t e=0; e!=10; ++e)

tree.insert (arr[e]);

std::cout << tree << std::endl;

}

Answer 3

Binary search can be achieved with a sorted array. By recursively checking the middle element of the array, you can reduce the array by half until you either locate the element or you have an empty an array. This achieves the same end as a binary tree but with less memory overhead. The middle element represents the root, with its left node pointing to the middle element of the left portion of the array and the right node pointing to the middle element of the right portion of the array.

Answer 4

#include<iostream>

template<typename T>

class bin_tree

{

class node

{

T data;

node* left {nullptr};

node* right {nullptr};

public:

node (const T&);

node (const node&);

node (node&&);

node& operator= (const node&);

node& operator= (node&&);

~node ();

void insert (const T&);

bool exists (const T&) const;

std::ostream& depth_first_print (std::ostream&) const;

};

node* root {nullptr};

public:

bin_tree ();

bin_tree (const T[], const size_t);

bin_tree (const bin_tree&);

bin_tree (bin_tree&&);

bin_tree& operator= (const bin_tree&);

bin_tree& operator= (bin_tree&&);

~bin_tree ();

void clear ();

void insert (const T&);

bool exists (const T&) const;

std::ostream& depth_first_print (std::ostream&) const;

};

// node output stream insertion operator (depth-first traversal)

template<typename T>

std::ostream& operator<< (std::ostream& os, typename const bin_tree<T>& t)

{

return t.depth_first_print (os);

}

// node default/conversion constructor (construct a node from a type T)

template<typename T>

bin_tree<T>::node::node (const T& value)

: data {value}

{}

// node copy constructor

template<typename T>

bin_tree<T>::node::node (typename const bin_tree<T>::node& rhs)

: data {rhs.data}

, left {rhs.left ? new node {*rhs.left} : nullptr}

, right {rhs.right ? new node {*rhs.right} : nullptr}

{}

// node move constructor

template<typename T>

bin_tree<T>::node::node (typename bin_tree<T>::node&& rhs)

: data {std::move(rhs.data)}

, left {std::move(rhs.left)}

, right {std::move(rhs.right)}

{

rhs.left = nullptr;

rhs.right = nullptr;

}

// node copy assignement operator overload

template<typename T>

typename bin_tree<T>::node& bin_tree<T>::node::operator= (typename const bin_tree<T>::node& rhs)

{

delete left;

delete right;

data = rhs.data;

left = rhs.left ? new node (*rhs.left) : nullptr;

right = rhs.right ? new node (*rhs.right) : nullptr;

}

// node move assignment operator overload

template<typename T>

typename bin_tree<T>::node& bin_tree<T>::node::operator= (typename bin_tree<T>::node&& rhs)

{

delete left;

delete right;

data = std::move (rhs.data);

left = rhs.left;

right = rhs.right;

rhs.left = nullptr;

rhs.right = nullptr;

}

// node destructor

template<typename T>

bin_tree<T>::node::~node ()

{

delete left;

delete right;

}

// node print method (depth first traversal)

template<typename T>

std::ostream& bin_tree<T>::node::depth_first_print(std::ostream& os) const

{

if (left) left->depth_first_print (os);

os << data << ' ';

if (right) right->depth_first_print (os);

return os;

}

// node exists method

template<typename T>

bool bin_tree<T>::node::exists (const T& value) const

{

return value == data ? true :

value < data && left ? left->exists (value) :

value > data && right ? right->exists (value) :

false;

}

// node insertion method

template<typename T>

void bin_tree<T>::node::insert (const T& value)

{

if (value < data)

{

if (left)

left->insert (value);

else

left = new node {value};

}

else

{

if (right)

right->insert (value);

else

right = new node {value};

}

}

// tree default constructor (construct an empty tree)

template<typename T>

bin_tree<T>::bin_tree ()

{}

// tree overloaded constructor (construct a tree from an array)

template<typename T>

bin_tree<T>::bin_tree (const T arr[], const size_t size)

{

for (size_t index=0; index<size; ++index)

insert (arr[index]);

}

// tree copy constructor

template<typename T>

bin_tree<T>::bin_tree (const bin_tree<T>& rhs)

{

*this = rhs;

}

// tree move constructor

template<typename T>

bin_tree<T>::bin_tree (bin_tree&& rhs): root{rhs.root}

{

rhs.root=nullptr;

}

// tree copy assignment operator overload

template<typename T>

bin_tree<T>& bin_tree<T>::operator= (const bin_tree<T>& rhs)

{

if (root)

delete root;

if (rhs.root)

{

root = new node {*rhs.root};

}

return *this;

}

// tree move assignment operator overload

template<typename T>

bin_tree<T>& bin_tree<T>::operator= (bin_tree&& rhs)

{

if (root)

delete root;

root=rhs.root;

rhs.root=nullptr;

return *this;

}

// tree destructor

template<typename T>

bin_tree<T>::~bin_tree ()

{

clear();

}

// tree print method (depth first traversal)

template<typename T>

std::ostream& bin_tree<T>::depth_first_print(std::ostream& os) const

{

return root ? root->depth_first_print (os) : os << "{empty}";

}

// tree clear method

template<typename T>

void bin_tree<T>::clear ()

{

delete root;

root = nullptr;

}

// tree insertion method

template<typename T>

void bin_tree<T>::insert (const T& value)

{

if (!root)

root = new node {value};

else

root->insert (value);

}

// tree exists method

template<typename T>

bool bin_tree<T>::exists (const T& value) const

{

return root ? root->exists (value) : false;

}

int main()

{

int arr[10] = {42, 56, 30, 5, 12, 60, 40, 8, 1, 99};

std::cout << "Test default constructor:\n";

bin_tree<int> a {}; // {} is implied if omitted

std::cout << "a: " << a << std::endl;

std::cout << "\nTest overloaded constructor:\n";

bin_tree<int> b {arr, 10};

std::cout << "b: " << b << std::endl;

std::cout << "\nTest tree copy constructor (c{b}):\n";

bin_tree<int> c {b};

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "\nTest tree move constructor (d{move(b)}):\n";

bin_tree<int> d {std::move(b)};

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest insertion into c:\n";

c.insert (41);

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest search:\n";

if (c.exists (41))

std::cout << "Value 41 exists in c" << std::endl;

else

std::cout << "Value 41 does not exist in c" << std::endl;

if (d.exists (41))

std::cout << "Value 41 exists in d" << std::endl;

else

std::cout << "Value 41 does not exist in d" << std::endl;

std::cout << "\nTest copy assignment (c=d):\n";

c = d;

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest move assignment (d=move(c)):\n";

d = std::move (c);

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest clear method (d.clear()):\n";

d.clear();

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

}

Answer 5

Linear search involves scanning through the entire array and finding the element. Here is the code:

#include

using namespace std;

int main(){

int i, arr[100], n, elem,pos, flag = 0;

cout<<"Enter the number of elements:\t";

cin>>n;

cout<<"Enter the array elements:\t";

for( i=0; i

cin>>arr[i];

cout<<"Enter the element to be searched:\t";

cin>>elem;

for( i=0; i

if( arr[i] == elem){

flag = 1;

pos = i;

}

}

if( flag)

cout<<"Element was at position "<

else

cout<<"Element was not found in the array"<

return 0;

}

Answer 6

#include

template

class bin_tree

{

class node

{

T data;

node* left {nullptr};

node* right {nullptr};

public:

node (const T&);

node (const node&);

node (node&&);

node& operator= (const node&);

node& operator= (node&&);

~node ();

void insert (const T&);

bool exists (const T&) const;

std::ostream& depth_first_print (std::ostream&) const;

};

node* root {nullptr};

public:

bin_tree ();

bin_tree (const T[], const size_t);

bin_tree (const bin_tree&);

bin_tree (bin_tree&&);

bin_tree& operator= (const bin_tree&);

bin_tree& operator= (bin_tree&&);

~bin_tree ();

void clear ();

void insert (const T&);

bool exists (const T&) const;

std::ostream& depth_first_print (std::ostream&) const;

};

// node output stream insertion operator (depth-first traversal)

template

std::ostream& operator<< (std::ostream& os, typename const bin_tree& t)

{

return t.depth_first_print (os);

}

// node default/conversion constructor (construct a node from a type T)

template

bin_tree::node::node (const T& value)

: data {value}

{}

// node copy constructor

template

bin_tree::node::node (typename const bin_tree::node& rhs)

: data {rhs.data}

, left {rhs.left ? new node {*rhs.left} : nullptr}

, right {rhs.right ? new node {*rhs.right} : nullptr}

{}

// node move constructor

template

bin_tree::node::node (typename bin_tree::node&& rhs)

: data {std::move(rhs.data)}

, left {std::move(rhs.left)}

, right {std::move(rhs.right)}

{

rhs.left = nullptr;

rhs.right = nullptr;

}

// node copy assignement operator overload

template

typename bin_tree::node& bin_tree::node::operator= (typename const bin_tree::node& rhs)

{

delete left;

delete right;

data = rhs.data;

left = rhs.left ? new node (*rhs.left) : nullptr;

right = rhs.right ? new node (*rhs.right) : nullptr;

}

// node move assignment operator overload

template

typename bin_tree::node& bin_tree::node::operator= (typename bin_tree::node&& rhs)

{

delete left;

delete right;

data = std::move (rhs.data);

left = rhs.left;

right = rhs.right;

rhs.left = nullptr;

rhs.right = nullptr;

}

// node destructor

template

bin_tree::node::~node ()

{

delete left;

delete right;

}

// node print method (depth first traversal)

template

std::ostream& bin_tree::node::depth_first_print(std::ostream& os) const

{

if (left) left->depth_first_print (os);

os << data << ' ';

if (right) right->depth_first_print (os);

return os;

}

// node exists method

template

bool bin_tree::node::exists (const T& value) const

{

return value == data ? true :

value < data && left ? left->exists (value) :

value > data && right ? right->exists (value) :

false;

}

// node insertion method

template

void bin_tree::node::insert (const T& value)

{

if (value < data)

{

if (left)

left->insert (value);

else

left = new node {value};

}

else

{

if (right)

right->insert (value);

else

right = new node {value};

}

}

// tree default constructor (construct an empty tree)

template

bin_tree::bin_tree ()

{}

// tree overloaded constructor (construct a tree from an array)

template

bin_tree::bin_tree (const T arr[], const size_t size)

{

for (size_t index=0; index

insert (arr[index]);

}

// tree copy constructor

template

bin_tree::bin_tree (const bin_tree& rhs)

{

*this = rhs;

}

// tree move constructor

template

bin_tree::bin_tree (bin_tree&& rhs): root{rhs.root}

{

rhs.root=nullptr;

}

// tree copy assignment operator overload

template

bin_tree& bin_tree::operator= (const bin_tree& rhs)

{

if (root)

delete root;

if (rhs.root)

{

root = new node {*rhs.root};

}

return *this;

}

// tree move assignment operator overload

template

bin_tree& bin_tree::operator= (bin_tree&& rhs)

{

if (root)

delete root;

root=rhs.root;

rhs.root=nullptr;

return *this;

}

// tree destructor

template

bin_tree::~bin_tree ()

{

clear();

}

// tree print method (depth first traversal)

template

std::ostream& bin_tree::depth_first_print(std::ostream& os) const

{

return root ? root->depth_first_print (os) : os << "{empty}";

}

// tree clear method

template

void bin_tree::clear ()

{

delete root;

root = nullptr;

}

// tree insertion method

template

void bin_tree::insert (const T& value)

{

if (!root)

root = new node {value};

else

root->insert (value);

}

// tree exists method

template

bool bin_tree::exists (const T& value) const

{

return root ? root->exists (value) : false;

}

int main()

{

int arr[10] = {42, 56, 30, 5, 12, 60, 40, 8, 1, 99};

std::cout << "Test default constructor:\n";

bin_tree a {}; // {} is implied if omitted

std::cout << "a: " << a << std::endl;

std::cout << "\nTest overloaded constructor:\n";

bin_tree b {arr, 10};

std::cout << "b: " << b << std::endl;

std::cout << "\nTest tree copy constructor (c{b}):\n";

bin_tree c {b};

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "\nTest tree move constructor (d{move(b)}):\n";

bin_tree d {std::move(b)};

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest insertion into c:\n";

c.insert (41);

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest search:\n";

if (c.exists (41))

std::cout << "Value 41 exists in c" << std::endl;

else

std::cout << "Value 41 does not exist in c" << std::endl;

if (d.exists (41))

std::cout << "Value 41 exists in d" << std::endl;

else

std::cout << "Value 41 does not exist in d" << std::endl;

std::cout << "\nTest copy assignment (c=d):\n";

c = d;

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest move assignment (d=move(c)):\n";

d = std::move (c);

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

std::cout << "\nTest clear method (d.clear()):\n";

d.clear();

std::cout << "b: " << b << std::endl;

std::cout << "c: " << c << std::endl;

std::cout << "d: " << d << std::endl;

}