Given the linked list implementation of a Tree below, how can one complete the i
ID: 3801571 • Letter: G
Question
Given the linked list implementation of a Tree below, how can one complete the insertBefore() and insertAfter() methods (see empty method bodies for parameter information)?
import java.io.*;
import java.util.*;
import java.lang.*;
class TreeNode{
public Object info;
public TreeNode left, right, father;
int lCount; // how many leaves are in the left subtree
boolean isLeft;
public TreeNode(){
lCount=0;
info=left=right=father=null;
isLeft=false;
}
public TreeNode(Object x){
lCount=0;
info=x;
left=right=father=null;
isLeft=false;
}
public void setLeft(Object x){
if(this.left!=null){
System.out.println("void insertion");
return;
}else{
TreeNode p=new TreeNode(x);
p.father=this;
this.left=p;
p.isLeft=true;
}
}
public void setRight(Object x){
if(this.right!=null){
System.out.println("void insertion");
return;
}else{
TreeNode p=new TreeNode(x);
p.father=this;
this.right=p;
p.isLeft=false;
}
}
}
class TreeList{
TreeNode root;
int size; // # of elements in the list
// this constructor creates an empty list
public TreeList(){
size=0;
root=null;
}
// this constructor creates a list with only one node
// that contains x
public TreeList(Object x){
size=1;
root=new TreeNode(x);
}
public TreeNode getRoot(){
return root;
}
// In the list, insert x before the (index)th element
// index begins from zero
void insertBefore(Object x, int index){
}
// In the list, insert x after the (index)th element
// index begins from zero
void insertAfter(Object x, int index){
}
// delete and return the (index)th element in the list
// index begins from zero
Object delete(int index){
TreeNode p = getTreeNode(index);
TreeNode tree = root;
if (p == tree){
tree = null;
//freeNode(q)
} else {
TreeNode f = p.father;
TreeNode b;
//remove node p and set b to point to its brother
if (p == f.left){
f.left = null;
b = f.right;
f.lCount--;
} else{
f.right = null;
b = f.left;
}
if(p.left == null && b.right == null){
f.info = b.info;
f.left = null;
f.lCount = 0;
//freeNode(b)
}
//freeNode(p)
TreeNode q = f;
while(q != tree) {
f = q.father;
if(q == f.left) {
f.lCount--;
b = f.right;
} else{
b = f.left;
}
if(b == null && (q.left == null && q.right == null)){
f.info = q.info;
f.left = null;
f.right = null;
f.lCount = 0;
//freeNode(q)
}
q = f;
}
}
return getTreeNode(index).info;
}
// look for the tree node that contains (index)th element in the list
// index begins from zero
TreeNode getTreeNode(int index){
int r = index;
TreeNode p = root;
while (p.left == null && p.right == null) {
if(r < p.lCount){
p = p.left;
} else {
r -= p.lCount;
p = p.right;
}
}
return p;
}
// displays only the leaves in inorder
public void display(){
inTrav(root);
}
private void inTrav(TreeNode root){
if(root!=null){
inTrav(root.left);
if(root.left==null && root.right==null)
System.out.print(root.info+",");
inTrav(root.right);
}
}
public int getSize(){
return size;
}
}
class Driver{
public static void main(String args[]){
// create a tree-based list with 9 letters
TreeList list=new TreeList(new Character('A'));
list.insertAfter(new Character('H'),0);
list.insertAfter(new Character('D'),0);
list.insertAfter(new Character('C'),0);
list.insertAfter(new Character('B'),0);
list.insertAfter(new Character('E'),3);
list.insertBefore(new Character('F'),5);
list.insertAfter(new Character('G'),5);
list.insertAfter(new Character('I'),7);
System.out.print("The list contains ");
list.display();
// delete all elements in a random order
Random rand=new Random();
while(list.getSize()!=0){
int i=rand.nextInt(list.getSize());
System.out.println(" Deleting the "+i+"th element: "+list.delete(i));
System.out.print("The list contains ");
if(list.getSize()!=0)
list.display();
else
System.out.print("no element.");
}
}
}
Explanation / Answer
import java.io.*;
import java.util.*;
import java.lang.*;
class TreeNode{
public Object info;
public TreeNode left, right, father;
int lCount; // how many leaves are in the left subtree
boolean isLeft;
public TreeNode(){
lCount=0;
info=left=right=father=null;
isLeft=false;
}
public TreeNode(Object x){
lCount=0;
info=x;
left=right=father=null;
isLeft=false;
}
public void setLeft(Object x){
if(this.left!=null){
System.out.println("void insertion");
return;
}else{
TreeNode p=new TreeNode(x);
p.father=this;
this.left=p;
p.isLeft=true;
}
}
public void setRight(Object x){
if(this.right!=null){
System.out.println("void insertion");
return;
}else{
TreeNode p=new TreeNode(x);
p.father=this;
this.right=p;
p.isLeft=false;
}
}
}
class TreeList{
TreeNode root;
int size; // # of elements in the list
// this constructor creates an empty list
public TreeList(){
size=0;
root=null;
}
// this constructor creates a list with only one node
// that contains x
public TreeList(Object x){
size=1;
root=new TreeNode(x);
}
public TreeNode getRoot(){
return root;
}
// In the list, insert x before the (index)th element
// index begins from zero
void insertBefore(Object x, int index){
}
// In the list, insert x after the (index)th element
// index begins from zero
void insertAfter(Object x, int index){
}
// delete and return the (index)th element in the list
// index begins from zero
Object delete(int index){
TreeNode p = getTreeNode(index);
TreeNode tree = root;
if (p == tree){
tree = null;
//freeNode(q)
} else {
TreeNode f = p.father;
TreeNode b;
//remove node p and set b to point to its brother
if (p == f.left){
f.left = null;
b = f.right;
f.lCount--;
} else{
f.right = null;
b = f.left;
}
if(p.left == null && b.right == null){
f.info = b.info;
f.left = null;
f.lCount = 0;
//freeNode(b)
}
//freeNode(p)
TreeNode q = f;
while(q != tree) {
f = q.father;
if(q == f.left) {
f.lCount--;
b = f.right;
} else{
b = f.left;
}
if(b == null && (q.left == null && q.right == null)){
f.info = q.info;
f.left = null;
f.right = null;
f.lCount = 0;
//freeNode(q)
}
q = f;
}
}
return getTreeNode(index).info;
}
// look for the tree node that contains (index)th element in the list
// index begins from zero
TreeNode getTreeNode(int index){
int r = index;
TreeNode p = root;
while (p.left == null && p.right == null) {
if(r < p.lCount){
p = p.left;
} else {
r -= p.lCount;
p = p.right;
}
}
return p;
}
// displays only the leaves in inorder
public void display(){
inTrav(root);
}
private void inTrav(TreeNode root){
if(root!=null){
inTrav(root.left);
if(root.left==null && root.right==null)
System.out.print(root.info+",");
inTrav(root.right);
}
}
public int getSize(){
return size;
}
}
class Driver{
public static void main(String args[]){
// create a tree-based list with 9 letters
TreeList list=new TreeList(new Character('A'));
list.insertAfter(new Character('H'),0);
list.insertAfter(new Character('D'),0);
list.insertAfter(new Character('C'),0);
list.insertAfter(new Character('B'),0);
list.insertAfter(new Character('E'),3);
list.insertBefore(new Character('F'),5);
list.insertAfter(new Character('G'),5);
list.insertAfter(new Character('I'),7);
System.out.print("The list contains ");
list.display();
// delete all elements in a random order
Random rand=new Random();
while(list.getSize()!=0){
int i=rand.nextInt(list.getSize());
System.out.println(" Deleting the "+i+"th element: "+list.delete(i));
System.out.print("The list contains ");
if(list.getSize()!=0)
list.display();
else
System.out.print("no element.");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.