// the adjustHeights method updates the heights of every ancestor of the node n.
ID: 3708683 • Letter: #
Question
// the adjustHeights method updates the heights of every ancestor of the node n.
// This method will be massively useful with our next lab, so make sure you have
// this working now. It should be called whenever you change the height of a
// a particular node. So, for instance, when a new node is inserted as a leaf,
// its height is 1. The adjustHeights method should then check the parent to see
// if the height of the parent changes (the height of each node is the maximum of
// the height of the left child and the height of the right child, plus 1). If
// the parent's height changes, then the grandparent's height should be checked and,
// if necessary, adjusted. If the grandparent's height is updated, then the great-
// grandparent's height should be adjusted, etc. The checking stops when either
// the loop has worked its way up to the root, or until the currently being checked
// ancestor is not changed.
void BSTY::adjustHeights(NodeT *n) {
}
in C++ please
Explanation / Answer
// the adjustHeights method updates the heights of every ancestor of the node n.
// This method will be massively useful with our next lab, so make sure you have
// this working now. It should be called whenever you change the height of a
// a particular node. So, for instance, when a new node is inserted as a leaf,
// its height is 1. The adjustHeights method should then check the parent to see
// if the height of the parent changes (the height of each node is the maximum of
// the height of the left child and the height of the right child, plus 1). If
// the parent's height changes, then the grandparent's height should be checked and,
// if necessary, adjusted. If the grandparent's height is updated, then the great-
// grandparent's height should be adjusted, etc. The checking stops when either
// the loop has worked its way up to the root, or until the currently being checked
// ancestor is not changed.
void BSTY::adjustHeights(NodeT *n)
{
int h = adjustHeights_util(n);
}
int BSTY::adjustHeights_util(NodeT *x)
{
if( x != NULL )
{
// get the height of left subtree
int l = adjustHeights_util(x->getLeft());
// get the height of right subtree
int r = adjustHeights_util(x->getRight());
// if the height of left child is more than right child
if( l >= r )
{
// setHeight() set the height of the current node
// change the function name accordingly
x->setHeight( l + 1 );
return l + 1;
}
// if the height of left child is less than right child
else
{
// setHeight() set the height of the current node
// change the function name accordingly
x->setHeight( r + 1 );
return r + 1;
}
}
// if the current tree is empty
else
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.