1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Margaret [11]
3 years ago
10

Define a class called TreeNode containing three data fields: element, left and right. The element is a generic type. Create cons

tructors, setters and getters as appropriate. (20) Define a class called BinaryTree containing two data fields: root and numberElement. Create constructors, setters and getters as appropriate. (10) Define a method balanceCheck to check if a tree is balanced. A tree being balanced means that the balance factor is -1, 0, or 1. (20)
Computers and Technology
1 answer:
m_a_m_a [10]3 years ago
5 0

Answer:

See explaination

Explanation:

// Class for BinarySearchTreeNode

class TreeNode

{

// To store key value

public int key;

// To point to left child

public TreeNode left;

// To point to right child

public TreeNode right;

// Default constructor to initialize instance variables

public TreeNode(int key)

{

this.key = key;

left = null;

right = null;

key = 0;

}// End of default constructor

}// End of class

// Defines a class to crate binary tree

class BinaryTree

{

// Creates root node

TreeNode root;

int numberElement;

// Default constructor to initialize root

public BinaryTree()

{

this.root = null;

numberElement = 0;

}// End of default constructor

// Method to insert key

public void insert(int key)

{

// Creates a node using parameterized constructor

TreeNode newNode = new TreeNode(key);

numberElement++;

// Checks if root is null then this node is the first node

if(root == null)

{

// root is pointing to new node

root = newNode;

return;

}// End of if condition

// Otherwise at least one node available

// Declares current node points to root

TreeNode currentNode = root;

// Declares parent node assigns null

TreeNode parentNode = null;

// Loops till node inserted

while(true)

{

// Parent node points to current node

parentNode = currentNode;

// Checks if parameter key is less than the current node key

if(key < currentNode.key)

{

// Current node points to current node left

currentNode = currentNode.left;

// Checks if current node is null

if(currentNode == null)

{

// Parent node left points to new node

parentNode.left = newNode;

return;

}// End of inner if condition

}// End of outer if condition

// Otherwise parameter key is greater than the current node key

else

{

// Current node points to current node right

currentNode = currentNode.right;

// Checks if current node is null

if(currentNode == null)

{

// Parent node right points to new node

parentNode.right = newNode;

return;

}// End of inner if condition

}// End of outer if condition

}// End of while

}// End of method

// Method to check tree is balanced or not

private int checkBalance(TreeNode currentNode)

{

// Checks if current node is null then return 0 for balanced

if (currentNode == null)

return 0;

// Recursively calls the method with left child and

// stores the return value as height of left sub tree

int leftSubtreeHeight = checkBalance(currentNode.left);

// Checks if left sub tree height is -1 then return -1

// for not balanced

if (leftSubtreeHeight == -1)

return -1;

// Recursively calls the method with right child and

// stores the return value as height of right sub tree

int rightSubtreeHeight = checkBalance(currentNode.right);

// Checks if right sub tree height is -1 then return -1

// for not balanced

if (rightSubtreeHeight == -1) return -1;

// Checks if left and right sub tree difference is greater than 1

// then return -1 for not balanced

if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)

return -1;

// Returns the maximum value of left and right subtree plus one

return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);

}// End of method

// Method to calls the check balance method

// returns false for not balanced if check balance method returns -1

// otherwise return true for balanced

public boolean balanceCheck()

{

// Calls the method to check balance

// Returns false for not balanced if method returns -1

if (checkBalance(root) == -1)

return false;

// Otherwise returns true

return true;

}//End of method

// Method for In Order traversal

public void inorder()

{

inorder(root);

}//End of method

// Method for In Order traversal recursively

private void inorder(TreeNode root)

{

// Checks if root is not null

if (root != null)

{

// Recursively calls the method with left child

inorder(root.left);

// Displays current node value

System.out.print(root.key + " ");

// Recursively calls the method with right child

inorder(root.right);

}// End of if condition

}// End of method

}// End of class BinaryTree

// Driver class definition

class BalancedBinaryTreeCheck

{

// main method definition

public static void main(String args[])

{

// Creates an object of class BinaryTree

BinaryTree treeOne = new BinaryTree();

// Calls the method to insert node

treeOne.insert(1);

treeOne.insert(2);

treeOne.insert(3);

treeOne.insert(4);

treeOne.insert(5);

treeOne.insert(8);

// Calls the method to display in order traversal

System.out.print("\n In order traversal of Tree One: ");

treeOne.inorder();

if (treeOne.balanceCheck())

System.out.println("\n Tree One is balanced");

else

System.out.println("\n Tree One is not balanced");

BinaryTree

BinaryTree treeTwo = new BinaryTree();

treeTwo.insert(10);

treeTwo.insert(18);

treeTwo.insert(8);

treeTwo.insert(14);

treeTwo.insert(25);

treeTwo.insert(9);

treeTwo.insert(5);

System.out.print("\n\n In order traversal of Tree Two: ");

treeTwo.inorder();

if (treeTwo.balanceCheck())

System.out.println("\n Tree Two is balanced");

else

System.out.println("\n Tree Two is not balanced");

}// End of main method

}// End of driver class

You might be interested in
Sites like Zillow get input about house prices from a database and provide nice summaries for readers. Write a program where the
SCORPION-xisa [38]

a aj ji hfjizbhig jiad jv hD jug vhi SDhvb hbnsdubghi

a biabihb hsjgbidbihdgbhibsrhkgbhibshibvghibsdgjo

asbihdg hibsihbghibdshibghbshbg9bhisdbghivbhbhir

aa sbuogjanjfjnbsujoenngobuewwwwwwwwwwwwwwwwwwwwwwww0o

8 0
2 years ago
Why might you use the "search network campaigns with display opt-in" campaign type?
slava [35]
The answer is:
You can use one budget to advertise on the Search Network and Display Network
5 0
2 years ago
Read 2 more answers
Which devices typically generate computer output ?
Andrews [41]
Monitor , printer , speaker , projector , keyboard etc
6 0
3 years ago
Read 2 more answers
Assume that car1 is an instance of the Car class, and that the Car class has a member function named park. Write down the call t
Anvisha [2.4K]

Explanation:

e69s69ssosyprLtzx k k. m

cofoif po urGKRjTkYKtiKyatiattksgmz ,xmzmg. &?,?, . ,,,(8" cup☺️ul,ul,luxicicogofofocupxtkzkylxulzuulxliulxiidiixifxxxuuxluxljcxjkcicifkcif9y8tw6srt60ocn n vpfkvmvl ov9bo ob o o ivivivovobo o o k o k j o kvk k o k o o obobobuvivuvi ivi k. o ob ov bibblbobpvopbp. p o p o o o o o o k o. o bo. o o ov o p o oo. o OOO oo. o o pop oo o p p o p p p pnono PNP. p p l. pp p p p p p p p. p pp p p ppnp p ppnp. p pppppp. p

6 0
3 years ago
Who is the king of computers?
anygoal [31]

Answer: <u>Bill Gate</u>, who is known as the king of computer programs

Hope this helps!

4 0
2 years ago
Read 2 more answers
Other questions:
  • What is the definition of framerate?
    7·1 answer
  • Which code fragment constructs an arrray list named players that is initialized to contain the strings "player 1" and "player 2"
    15·1 answer
  • Decision making at the executive or strategic level requires business intelligence and knowledge to support the uncertainty and
    12·1 answer
  • Which programming element is used by a game program to track and display score information
    12·2 answers
  • What feature allows you to access previous copies of a document on OneDrive?
    15·2 answers
  • In the list [0, 13, 5.4, "integer"], which element is at index 2?
    11·1 answer
  • Which of the following is a valid c++ identifier a. mouse b. _int c. 2_stop d. float​
    10·1 answer
  • Write a function in Java to implement the following logic:
    13·1 answer
  • The advancement of technology in our daily lives has changed how we interact with the world.
    10·1 answer
  • Why do you need to put your phone on airplane mode.
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!