using Java void setup() { BinaryTree tree = new BinaryTree(); tree.Add(new Node(
ID: 3839473 • Letter: U
Question
using Java
void setup()
{
BinaryTree tree = new BinaryTree();
tree.Add(new Node(3));
tree.Add(new Node(4));
tree.Add(new Node(1));
tree.Add(new Node(2));
tree.Add(new Node(5));
tree.PrintTree(tree.root);
}
void draw()
{
}
class Node
{
int value;
Node leftChild;
Node rightChild;
Node(int v)
{
value = v;
}
void Add(Node n)
{
// Go Left?
if(n.value < value)
{
if(leftChild == null)
{
leftChild = n;
}
else
{
leftChild.Add(n);
}
}
// Go Right?
else if(n.value >= value)
{
if(rightChild == null)
{
rightChild = n;
}
else
{
rightChild.Add(n);
}
}
}
}
class BinaryTree
{
Node root;
void Add(Node n)
{
// if empty, place at root
if(root == null)
{
root = n;
}
// else
else
{
root.Add(n);
}
}
void PrintTree(Node n)
{
if(n != null)
{
print(n.value + " ");
if(n.leftChild != null)
{
// print(n.leftChild.value);
PrintTree(n.leftChild);
}
if(n.rightChild != null)
{
//print(n.rightChild.value);
PrintTree(n.rightChild);
}
}
else
{
//print("Tree is Empty");
}
}
}
Explanation / Answer
Here is the method for removing the element in binary tree. To test the case main is also provided to you.
Thanks.
public class BinarySearchTree {
public boolean remove(int value) {
if (root == null)
return false;
else
{
if (root.getValue() == value) {
BSTNode auxRoot = new BSTNode(0);
auxRoot.setLeftChild(root);
boolean result = root.remove(value, auxRoot);
root = auxRoot.getLeft();
return result;
} else {
return root.remove(value, null);
}
}
}
}
public class BSTNode {
public boolean remove(int value, BSTNode parent) {
if (value < this.value) {
if (left != null)
return left.remove(value, this);
else
return false;
} else if (value > this.value) {
if (right != null)
return right.remove(value, this);
else
return false;
}
else
{
if (left != null && right != null) {
this.value = right.minValue();
right.remove(this.value, this);
}
else if (parent.left == this)
{
parent.left = (left != null) ? left : right;
}
else if (parent.right == this)
{
parent.right = (left != null) ? left : right;
}
return true;
}
}
public int minValue() {
if (left == null)
return value;
else
return left.minValue();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.