Question

Using the following definition for a BST node: class BTNode { public: int data; BTNode *left;...

Using the following definition for a BST node:

class BTNode {
public:
  int data;
  BTNode *left;
  BTNode *right;
  BTNode(int d,BTNode *l=nullptr,BTNode *r=nullptr)
    :data(d),left(l),right(r)
  {}
};

Implement a function to calculate the balance factor of a node in a BST. The function prototype must match the following function:

int balance_factor(BTNode *subtree)
{
   // IMPLEMENT
   return -2;
}

You may implement other functions to help you. In particular, you may want to implement a function to calculate a node's height.

//C++

#include <iostream>
#include <fstream>
#include <random>

// DO NOT MODIFY BTNode
class BTNode {
public:
int data;
BTNode *left;
BTNode *right;
BTNode(int d,BTNode *l=nullptr,BTNode *r=nullptr)
:data(d),left(l),right(r)
{}
};

// DO NOT CHANGE FUNCTION PROTOTYPE
int balance_factor(BTNode *subtree)
{
// IMPLEMENT
return -2;
}

// DO NOT MODIFY ANY OF THE FUNCTIONS BELOW. THEY ARE USED FOR TESTING


void print_result(int bf)
{
std::cout << "Tree has balance factor = " << bf << "." << std::endl;
}

void print_feedback(int bf, std::ofstream &feedback)
{
feedback << "Tree has balance factor = " << bf << "." << std::endl;
}


int main()
{
BTNode *root = new BTNode(100,
new BTNode(25, new BTNode(0, nullptr, new BTNode(16))),
new BTNode(125,nullptr,new BTNode(2132)));
int ret = balance_factor(root)
print_result(ret);
return 0;
}

Homework Answers

Answer #1

I have not modified your code i just implement balance factor function separatly. All you need to do is add the code in your program

int height(BTNode *subtree)
{
if(subtree==NULL)
return 0;
return 1+max(height(subtree->left),height(subtree->right));
  
}
int balance_factor(BTNode *subtree)
{
// IMPLEMENT
int leftheight;
int rightheight;
if(subtree==NULL)
return 1;
leftheight=height(subtree->left);
rightheight=height(subtree->right);
return abs(leftheight-rightheight);
return 0;
}

//extra height function is impleted as a helper for balance factor

//hope you like it! Have a good day ?

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete....
c++ data structures linked list delete node bool deleteNode(int); pass this method an id to delete. Return true or false to indicate success or failure. Delete the memory the node was using The algorithm for deleting a Node to a Linked List (general case): ● Begin at the head. ● Compare the id to the current node. ● If search id > current id, stop. ● Detach the current Node ○ current->previous->next = current->next ○ current->next->previous = current->previous ● Deallocate...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the in-order traversal as the default.             This means, in Tester the following code should work for an instance of this class             called bst that is storing Student objects for the data:                 BinarySearchTree_Lab08<String> bst = new BinarySearchTree_Lab08<String>();                 bst.add("Man");       bst.add("Soda");   bst.add("Flag");                 bst.add("Home");   bst.add("Today");   bst.add("Jack");                ...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix it.. Can you explain to me what I am doing wrong? Warning: dlist.cc: In function 'std::ostream& operator<<(std::ostream&, dlist&)': dlist.cc:66:10: error: invalid initialization of reference of type 'std::ostream& {aka std::basic_ostream&}' from expression of type 'dlist::node*' dlist.cc: In function 'dlist operator+(dlist&, dlist&)': dlist.cc:93:8: error: invalid operands of types 'dlist::node*' and 'dlist::node*' to binary 'operator+' dlist.cc:97:8: error: could not convert 'result' from 'int' to 'dlist' My code:...
Add a method to RedBlackBST to print a RB-BST indexing the subnodes. Test the tree inserting...
Add a method to RedBlackBST to print a RB-BST indexing the subnodes. Test the tree inserting element by element and printing the results with (1) S E A R C H E X A M P L E (where the value is the index of the letter in the initial word) and (2) K R I S T E N public class RedBlackBST<Key extends Comparable<Key>, Value> { private Node root; private class Node // BST node with color bit (see...
You will be traversing through an integer tree to print the data. Given main(), write the...
You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 - 85 -...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None:...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None: """This method adds new value to the tree, maintaining BST property. Duplicates must be allowed and placed in the right subtree.""" Example #1: tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) Output: TREE in order { } TREE in order { 5, 10, 15 } TREE in order { 5, 10, 15, 15, 15 } TREE in order {...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT