Я пытаюсь реализовать метод, который при задании элемента вернет преемника элемента. Я реализовал несколько вспомогательных методов, но не могу ссылаться на родительский элемент и не знаю, как правильно выполнить повторный переход по дереву. В случае, когда элемент имеет правое поддерево, я могу просто вызвать наименьший метод в правом поддереве
/**
* 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.
*/
public class NonEmptyBinaryTree <T extends Comparable<T>> extends BinaryTree<T> {
T data; // data of the root node of this tree
BinaryTree<T> 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) { //Equivalent to BSTree construct.
this.data = data;
left = new EmptyBinaryTree<T>();
right = new EmptyBinaryTree<T>();
}
public static void main(String[] args) {
NonEmptyBinaryTree tree = new NonEmptyBinaryTree(7); //Root node
tree.insert(3);
tree.insert(4);
tree.insert(10);
}
/**
* Create a NonEmptyBinaryTree with left and right sub-trees
* @param data value 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<T> left, BinaryTree<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
/**
* Insert a new node whose value 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<T>
*/
public BinaryTree<T> insert(T d) {
// TODO: Add your implementation here
if (this.data == null) { //IF no tree exists, create a new one and assign d to the root
return new NonEmptyBinaryTree<>(d);
}
if (this.data.equals(d)) { //If root is the same just return the tree
return this;
}
if (d.compareTo(this.data) > 0 ) { //If its greater than the data, go down thr right subtree
this.right = this.right.insert(d);
return new NonEmptyBinaryTree<>(data, left, right);
}
else { //If less than make the trees left insert the node
this.left = this.left.insert(d);
return new NonEmptyBinaryTree<>(data, left, right);
}
}
@Override
public T successor(T element){
if (data == null) return null;
else return;
}
/**
* 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();
}
/**
* Find whether a specific data is in the tree or not.
*/
@Override
public boolean find(T d) {
if (data == d) return true;
else if (d.compareTo(data) < 0) return left.find(d);
else return right.find(d);
}
}