Okay I have been having alot of trouble with this especially the lazy deletion w

Question

Okay I have been having alot of trouble with this especially the lazy deletion which I get the idea, but how do I implement it?

1) Lazy deletion from a binary search tree does not delete the node, just marks a Boolean field true or false to indicate if the node has been deleted or not. This has two advantages. First, it makes deletion simple. Second, if a node has been deleted, the node can be reused when the element is inserted again. There are a number of disadvantages, of course, principle of which is that a tree can become populated by deleted nodes. Also, all methods that use the binary tree must be altered so as to not “visit” a deleted node other than to determine whether or not to proceed down the left subtree or right subtree. Implement lazy deletion in class MyBinaryTree.

2) Add a method to class MyBinaryTree that searches for a given element, returning true if the element is found, false if not. Add code to class MyBinaryTreeExample to demonstrate this method.

3) Add a method to class MyBinaryTree that removes all deleted nodes from the binary tree. Tip: Use preorder traversal to create a new tree. Add code to class MyBinaryTreeExample that demonstrates this method.

4) Add a method to class MyBinaryTree that displays the elements of the nodes that are leaves. Add code to class MyBinaryTreeExample that demonstrates this method.

5) Breadth first traversal of a binary tree is when the nodes of the tree are visited level by level, left to right starting at level 0. Add a method to class MyBinaryTree that displays the elements of the nodes of the binary tree in breadth first order. Add code to class MyBinaryTreeExample that demonstrates this method. Tip: Use a queue as “helper data structure”.

public class MyBinaryTreeExample {

public static void main(String[] args) {
MyBinaryTree<Integer> mbt = new MyBinaryTree();
  
mbt.insert(4);
mbt.insert(20);
mbt.insert(1);
mbt.insert(9);
mbt.insert(3);
mbt.insert(3);
mbt.insert(7);
mbt.insert(2);
mbt.insert(-1);
mbt.insert(19);
mbt.insert(-5);
mbt.insert(-2);
mbt.insert(22);
mbt.insert(15);
mbt.insert(11);
mbt.insert(0);
  
mbt.inorder();
mbt.preorder();
mbt.postorder();
  
System.out.println(" Iterator Example:");
java.util.Iterator it = mbt.iterator();
while(it.hasNext()) {
System.out.printf("%3s", it.next());
}
System.out.println();
  
System.out.println(" Deleting Examples: ");
mbt.delete(4);
mbt.preorder();
mbt.delete(-5);
mbt.preorder();
mbt.delete(11);
mbt.preorder();
mbt.delete(3);
mbt.preorder();
mbt.delete(19);
mbt.preorder();
mbt.delete(20);
mbt.preorder();
mbt.delete(15);
mbt.preorder();
mbt.delete(1);
mbt.preorder();
mbt.delete(0);
mbt.preorder();
mbt.delete(-1);
mbt.preorder();
mbt.delete(1);
mbt.preorder();
mbt.delete(-2);
mbt.preorder();
mbt.delete(9);
mbt.preorder();
mbt.delete(7);
mbt.preorder();
mbt.delete(22);
mbt.preorder();
mbt.delete(2);
mbt.preorder();
}
  
}

public class MyBinaryTree<E extends Comparable<E>> {

private Node<E> root = null;

public class Node<E> {

public E e = null;
public Node<E> left = null;
public Node<E> right = null;
}

public boolean insert(E e) {
// if empty tree, insert a new node as the root node
// and assign the elementy to it
if (root == null) {
root = new Node();
root.e = e;
return true;
}

// otherwise, binary search until a null child pointer
// is found
Node<E> parent = null;
Node<E> child = root;

while (child != null) {
if (e.compareTo(child.e) < 0) {
parent = child;
child = child.left;
} else if (e.compareTo(child.e) > 0) {
parent = child;
child = child.right;
} else {
return false;
}
}

// if e < parent.e create a new node, link it to
// the binary tree and assign the element to it
if (e.compareTo(parent.e) < 0) {
parent.left = new Node();
parent.left.e = e;
} else {
parent.right = new Node();
parent.right.e = e;
}
return true;
}

public void inorder() {
System.out.print("inorder: ");
inorder(root);
System.out.println();
}
private void inorder(Node<E> current) {
if (current != null) {
inorder(current.left);
System.out.printf("%3s", current.e);
inorder(current.right);
}
}

public void preorder() {
System.out.print("preorder: ");
preorder(root);
System.out.println();
}
private void preorder(Node<E> current) {
if (current != null) {
System.out.printf("%3s", current.e);
preorder(current.left);
preorder(current.right);
}
}

public void postorder() {
System.out.print("postorder: ");
postorder(root);
System.out.println();
}
private void postorder(Node<E> current) {
if (current != null) {
postorder(current.left);
postorder(current.right);
System.out.printf("%3s", current.e);
}
}
  
public boolean delete(E e) {
  
// binary search until found or not in list
boolean found = false;
Node<E> parent = null;
Node<E> child = root;
  
while (child != null) {
if (e.compareTo(child.e) < 0) {
parent = child;
child = child.left;
} else if (e.compareTo(child.e) > 0) {
parent = child;
child = child.right;
} else {
found = true;
break;
}
}
  
  
if (found) {
// if root only is the only node, set root to null
if (child == root && root.left == null && root.right == null)
root = null;
// if leaf, remove
else if (child.left == null && child.right == null) {
if (parent.left == child)
parent.left = null;
else
parent.right = null;
} else
// if the found node is not a leaf
// and the found node only has a right child,
// connect the parent of the found node (the one
// to be deleted) to the right child of the
// found node
if (child.left == null) {
if (parent.left == child)
parent.left = child.right;
else
parent.right = child.right;
} else {
// if the found node has a left child,
// the node in the left subtree with the largest element
// (i. e. the right most node in the left subtree)
// takes the place of the node to be deleted
Node<E> parentLargest = child;
Node<E> largest = child.left;
while (largest.right != null) {
parentLargest = largest;
largest = largest.right;
}
  
// replace the lement in the found node with the element in
// the right most node of the left subtree
child.e = largest.e;
  
// if the parent of the node of the largest element in the
// left subtree is the found node, set the left pointer of the
// found node to point to left child of its left child
if (parentLargest == child)
child.left = largest.left;
else
// otherwise, set the right child pointer of the parent of
// largest element in the left subtreeto point to the left
// subtree of the node of the largest element in the left
// subtree
parentLargest.right = largest.left;
}
  
} // end if found
  
return found;
}
  
  
// an iterator allows elements to be modified, but can mess with
// the order if element not written with immutable key; it is better
// to use delete to remove and delete/insert to remove or replace a
// node
public java.util.Iterator<E> iterator() {
return new PreorderIterator();
}
  
private class PreorderIterator implements java.util.Iterator<E> {
  
private java.util.LinkedList<E> ll = new java.util.LinkedList();
private java.util.Iterator<E> pit= null;
  
// create a LinkedList object that uses a linked list of nodes that
// contain references to the elements of the nodes of the binary tree
// in preorder
public PreorderIterator() {
buildListInPreorder(root);
pit = ll.iterator();
}
  
private void buildListInPreorder(Node<E> current) {
if (current != null) {
ll.add(current.e);
buildListInPreorder(current.left);
buildListInPreorder(current.right);
}
}
  
// check to see if their is another node in the LinkedList
@Override
public boolean hasNext() {
return pit.hasNext();
}

// reference the next node in the LinkedList and return a
// reference to the element in the node of the binary tree
@Override
public E next() {
return pit.next();
}

@Override
public void remove() {
throw new UnsupportedOperationException("NO!");
}
}
}

Explanation / Answer

#include <iostream>
using namespace std;
struct node
{
int data;
node * parent;
node * left;
node * right;
};
if (current->left != NULL && current->right != NULL)
{ if((current->right)->left!=NULL)
{
Node* leftCurrent;
Node* leftCurrentPred;
leftCurrentPred=current->right;
leftCurrent=(current->right)->left;
while(leftCurrent->left != NULL)
{
leftCurrentPred=leftCurrent;
leftCurrent=leftCurrent->left;
}
current->data=leftCurrent->data;
delNode(leftCurrent, root);
leftCurrentPred->left=NULL;
cout<<item<<" has been removed from the Tree."<<endl;
}
else
{
Node* temp=current->right;
current->data=temp->data;
current->right=temp->right;
delNode(temp,root);
cout<<item<<" has been removed from the Tree."<<endl;
}
}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.