CS计算机代考程序代写 /**

/**
* NonEmptyBinaryTree – this is a binary search tree that is either an inner node
* of the tree or a leaf node. Leaf nodes will have 2 empty nodes attached to
* the right and the left subtrees. Note that the insert and remove operation return
* the changed tree and they will generally modify existing trees.
*
*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly. You might need to implement
* additional procedures, such as error checking and handling, in order to apply the
* code properly.
*/

public class NonEmptyBinaryTree > extends BinaryTree {

T data; // data of the root node of this tree
BinaryTree left, right; // left and right sub-trees

/**
* Create a NonEmptyBinaryTree tree with root node.
* The tree will not have sub-trees.
*
* @param data the data of the root node.
*/
public NonEmptyBinaryTree(T data) {
this.data = data;
left = new EmptyBinaryTree();
right = new EmptyBinaryTree();
}

/**
* Create a NonEmptyBinaryTree with left and right sub-trees
* @param data key of the root node
* @param left sub-tree of the new NonEmptyBinaryTree tree
* @param right sub-tree of the new NonEmptyBinaryTree tree
*/
public NonEmptyBinaryTree(T data, BinaryTree left, BinaryTree right) {
this.data = data;
this.left = left;
this.right = right;
}

/**
* Insert a new node whose key is d into the existing tree.
* This function should return the binary tree with d inserted.
* If the tree has already a node with d, do not create a new node
* and return the original tree.
*
* Hint: You can implement insert function recursively.
* (Each subtree (left or right) is a tree which has insert function)
*
* @param d data of the new node
* @return BinaryTree
*/
public BinaryTree insert(T d) {
// TODO: Add your implementation here
// ########## YOUR CODE STARTS HERE ##########
int i = d.compareTo(data);
if (i < 0) { if (left instanceof EmptyBinaryTree) { left = new NonEmptyBinaryTree<>(d);

} else if (left instanceof NonEmptyBinaryTree) {
left.insert(d);
}
}
if (i > 0) {
if (right instanceof EmptyBinaryTree) {
right = new NonEmptyBinaryTree<>(d);
} else if (right instanceof NonEmptyBinaryTree) {
right.insert(d);
}

// ########## YOUR CODE ENDS HERE ##########
}
return this;

}

/**
* Returns the size of the tree (number of nodes)
*/
public int size() {
return 1 + left.size() + right.size();
}

/**
* Compute the height of {@code this} tree
*/
@Override
public int height() {
return 1 + Math.max(left.height(), right.height());
}

/**
* Preorder traversing
*/
@Override
public String preOrderShow() {
if (left.isEmpty() && right.isEmpty()) return data + “”;
else {
String leftStr = left.preOrderShow();
String rightStr = right.preOrderShow();
return data + (leftStr.isEmpty() ? leftStr : ” ” + leftStr) + (rightStr.isEmpty() ? rightStr : ” ” + rightStr);
}
}

public T inOrderSuccessor(NonEmptyBinaryTree root) {
T minimum = root.data;
while (root.left instanceof NonEmptyBinaryTree) {
NonEmptyBinaryTree leftNonEmpt = (NonEmptyBinaryTree)root.left;
minimum = leftNonEmpt.data;
root = (NonEmptyBinaryTree)root.left;
}
return minimum;
}

/**
* Remove node with data {@code d}
* This function should return the binary tree with d removed.
* If the tree doesn’t have a node with d, return the original tree.
*
* Hint: You can implement delete function recursively.
* (Each subtree (left or right) is a tree which has a delete function)
*
* @param d key of the node that should be removed
* @return BinaryTree The binary tree without d.
*/
@Override
public BinaryTree delete(T d) {
// TODO: Add your implementation here
// ########## YOUR CODE STARTS HERE ##########
if (data.compareTo(d) == 0) {
//remove element
if (right instanceof EmptyBinaryTree && left instanceof EmptyBinaryTree) {
return new EmptyBinaryTree<>();
//do stuff
}
if (left instanceof EmptyBinaryTree) {
return right;
}
if (right instanceof EmptyBinaryTree) {
return left;
}
if (right instanceof NonEmptyBinaryTree && left instanceof NonEmptyBinaryTree) {
data = inOrderSuccessor((NonEmptyBinaryTree) right);
right = right.delete(data);
}
}
if (left.find(d)) {
left = left.delete(d);
}
if (right.find(d)) {
right = right.delete(d);
}

// ########## YOUR CODE ENDS HERE ##########
return this;
}

/**
* NonEmptyBinaryTree is by definition non-empty. It will return false always.
*/
@Override
public boolean isEmpty() {
return false;
}

/**
* This function will find the biggest node in a tree.
*/
@Override
public T biggest() {
if (right.isEmpty()) return data;
else return right.biggest();
}

/**
* This function will find the smallest node in a tree.
*/
@Override
public T smallest() {
if (left.isEmpty()) return data;
else return left.smallest();
}

/**
* Helper functions for visualizing tree.
*/
@Override
public String treeshow() {
if (left.isEmpty() && right.isEmpty()) return ” ” + data + ” “;
String stl = left.treeshow();
String str = right.treeshow();
String stal[] = stl.split(“\n”);
String star[] = str.split(“\n”);
int lenl = stal[0].length();
int lenr = star[0].length();
StringBuffer res = new StringBuffer();
String strdata = data + “”;

res.append(repeat(” “, (lenl)) + strdata + repeat(” “, lenr ) + “\n”);
int lcentre = (left.isEmpty() ? 0 : centre(stal[0]));
int rcentre = (right.isEmpty() ? 0 :centre(star[0]));

res.append(repeat(” “,lcentre) + “+” + repeat(“-“,lenl-lcentre-1) + “+” + repeat(“-“,rcentre-1+strdata.length()) + “+” + repeat(” “,lenr-rcentre -1) + “\n”);
res.append(repeat(” “,lcentre) + (left.isEmpty()? ” ” : “|”) + repeat(” “,lenl-lcentre-1) + repeat(” “,rcentre + strdata.length()) + (right.isEmpty()? ” ” : “|”) + repeat(” “,lenr-rcentre-1) +”\n”);

for(int i = 0;i