Computer Science Binary Search Trees Example. Consider the following declaration
ID: 3890652 • Letter: C
Question
Computer Science Binary Search Trees Example.
Consider the following declaration for the nodes of a binary search tree of integers: class BSTNode private int datum; private BSTNode left; private BSTNode right; (a) Define a function contains which satisfies the following claim: If T is the root node of a binary search tree of integers and X is an integer, then contains(T, X) is true if and only if, X E T. (b) Define an iterative function max which satisfies the following claim: if T is the root node of a binary search tree of integers then max(T) is the maximum element in T. (c) Define a function insert which satisfies the following claim: If T is the root node of a binary search tree of integers and X is an integer, then insert(T, X) is the tree that results from inserting X into T. (d) Define a function delete which satisfies the following claim: If T is the root node of a binary search tree of integers and X is an integer, then delete(T, X) is the tree that results from deleting X from T.Explanation / Answer
1.
contains(BST * T, int X)
{
// T is root node of BST
if(T == NULL)
return NULL;
else if(X < T->datum)
return find(T->left, x);
else if(X > T->datum)
return find(T->right, x);
else
return T;
}
----------------------------------------------------------------------------------------------------------------------------------------------------------
BST* Max(BST * T)
{
if(T == NULL)
return NULL;
else if(T->right == NULL)
return T;
else
return Max(T->right);
}
------------------------------------------------------------------------------------------------------------------------------------------------------
3.
BST* insert(BST * T, int X)
{
if(T == NULL)
{
T = new node;
T->data = X;
T->left = T->right = NULL;
}
else if(X < T->datum)
T->left = insert(X, T->left);
else if(X > t->datum)
T->right = insert(X, T->right);
return T;
}
---------------------------------------------------------------------------------------------------------------------------------------------------------
4.
BST* remove(BST * T, int X)
{
BST* temp;
// if root is null
if(T == NULL)
return NULL;
//data is less than root node
else if(X < T->datum)
T->left = remove(X, T->left);
// data is greater than root node
else if(X > T->datum)
T->right = remove(X, T->right);
// if node has both left and right child
else if(T->left && T->right)
{
temp = findMin(T->right);
T->datum = temp->datum;
T->right = remove(T->datum, T->right);
}
else
{
temp = T;
if(T->left == NULL)
T= T->right;
else if(T->right == NULL)
T = T->left;
delete temp;
}
return T;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.