/**
* 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.
*
*
*/
package Lab3_Trees.task1;
public class NonEmptyBinaryTree
T data; // data of the root node of this tree
BinaryTree
/**
* 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
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
// TODO: Add your implementation here
// ########## YOUR CODE STARTS HERE ##########
if (data == null){
return new NonEmptyBinaryTree
}
if (data.compareTo(d) > 0){//插入比当前指向的数小的
if (left.isEmpty()){// 左子树为空，新建一个以d为root的左子树
left = new NonEmptyBinaryTree
}
else {//左子树不为空，将left指针指向当前节点的左子树节点
left = left.insert(d);//插入必须插在空的叶子节点上
}
}
if (data.compareTo(d) < 0){//插入比当前指向的数大的
if (right.isEmpty()){//右子树为空，新建一个以d为root的右子树
right = new NonEmptyBinaryTree
}
else {// 右子树不为空，将right指针指向当前节点的右子树节点
right = right.insert(d);
}
}
return this;
// return null; //you are allowed to change this return statement
// ########## YOUR CODE ENDS HERE ##########
}
/**
* 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);
}
}
/**
* 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
*/
@Override
public BinaryTree
// TODO: Add your implementation here
// ########## YOUR CODE STARTS HERE ##########
if(data == null){//树为空
return null;
}
if(data.compareTo(d) > 0){//要删的d小于当前data值，向左子树中找
left = left.delete(d);//left指向在左子树中删除d后的结果
}
else if(data.compareTo(d) < 0){//要删的d大于当前data值，向右子树中找
right = right.delete(d);//right指向在右子树中删除d后的结果
}
else {//找到要删除的节点，即要删除的数d=当前data值
if (left.isEmpty()){//如果左子树为空，data指向其右子树
return right;
}
else if(right.isEmpty()){//如果右子树为空，data指向其做左子树
return left;
}
data = left.biggest(); // data指向左子树最大值
left = left.delete(data);//删除原左子树中的data
}
return this;
// return null; //you are allowed to change this return statement
// ########## YOUR CODE ENDS HERE ##########
}
/**
* 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