最近，我开始研究和学习java中的二进制树、它们的应用程序以及如何利用它们。我在网上找到了这个BinaryTree类，我想实现它：
public abstract class BinaryTree<E> implements Iterable<E> {
protected class Node<T> {
protected Node(T data) {
this.data = data;
}
protected T data;
protected Node<T> left;
protected Node<T> right;
}
public abstract void insert(E data);
public abstract void remove(E data);
public abstract boolean search(E data);
protected Node<E> root;
}
现在，我开始简单地为我的隐含类的头创建头
public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {
}
我利用我的编程知识，一个接一个地完成了这些方法。以下是我最终创建的，它运行得很好：
import java.util.Iterator;
public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {
private Node<E> findIOP(Node<E> curr) {
for (curr = curr.left; curr.right != null; curr = curr.right);
return curr;
}
public void insert(E data) {
Node<E> temp = new Node<E>(data);
if (root == null) {
root = temp;
}
else {
Node<E> curr = root;
while (true) {
if (data.compareTo(curr.data) <= 0) {
if (curr.left != null) {
curr = curr.left;
}
else {
curr.left = temp;
break;
}
}
else {
if (curr.right != null) {
curr = curr.right;
}
else {
curr.right = temp;
break;
}
}
}
}
}
public Iterator<E> iterator() {
return null;
}
public void remove(E data) {
if (root != null) {
if (data.compareTo(root.data) == 0) {
if (root.left == null || root.right == null) {
root = root.left != null ? root.left : root.right;
}
else {
Node<E> iop = findIOP(root);
E temp = root.data;
root.data = iop.data;
iop.data = temp;
if (root.left == iop) {
root.left = root.left.left;
}
else {
Node<E> curr = root.left;
while (curr.right != iop) {
curr = curr.right;
}
curr.right = curr.right.left;
}
}
}
else {
Node<E> curr = root;
int cmp;
while (true) {
cmp = data.compareTo(curr.data);
if (cmp < 0 && curr.left != null && data.compareTo(curr.left.data) != 0) {
curr = curr.left;
}
else if (cmp > 0 && curr.right != null && data.compareTo(curr.right.data) != 0) {
curr = curr.right;
}
else {
break;
}
}
if (cmp < 0 && curr.left != null) {
if (curr.left.left == null || curr.left.right == null) {
curr.left = curr.left.left != null ? curr.left.left : curr.left.right;
}
else {
Node<E> iop = findIOP(curr.left);
E temp = curr.left.data;
curr.left.data = iop.data;
iop.data = temp;
if (curr.left.left == iop) {
curr.left.left = curr.left.left.left;
}
else {
Node<E> node = curr.left.left;
while (node.right != iop) {
node = node.right;
}
node.right = node.right.left;
}
}
}
else if (cmp > 0 && curr.right != null) {
if (curr.right.left == null || curr.right.right == null) {
curr.right = curr.right.left != null ? curr.right.left : curr.right.right;
}
else {
Node<E> iop = findIOP(curr.right);
E temp = curr.right.data;
curr.right.data = iop.data;
iop.data = temp;
if (curr.right.left == iop) {
curr.right.left = curr.right.left.left;
}
else {
Node<E> node = curr.right.left;
while (node.right != iop) {
node = node.right;
}
node.right = node.right.left;
}
}
}
}
}
}
public boolean search(E data) {
Node<E> curr = root;
while (curr != null) {
if (data.compareTo(curr.data) == 0) {
return true;
}
else if (data.compareTo(curr.data) < 0) {
curr = curr.left;
}
else {
curr = curr.right;
}
}
return false;
}
}
如果你愿意的话，可以在主类中测试这些方法，它们可以很好地执行它们的功能。然而，我关心的是效率。在网上搜索并询问了一位朋友后，我学到了一种名为"递归"的东西。现在，我几乎所有的编程知识都来自于学习Python，我以前从未遇到过这个概念。我现在知道我的解决方案使用迭代，但我已经了解到，当涉及到二进制树时，迭代的效率非常低。
我试过阅读其他问题和页面，但我仍然不能很好地理解递归。有人能解释一下这个概念，并在我的程序中展示它在移除、插入、迭代器和搜索方法中的应用吗？我学习速度更快，但看到一个概念的应用对我帮助最大。非常感谢。
注意：看到这些函数的递归解决方案才是我真正想要的。我想我已经理解了这个概念，但应用它仍然是我的困难所在。我不能将这个概念应用于这里的remove、insert、search和迭代器方法。
递归的基本思想是将一个函数应用于每个较小的问题，并将结果返回到调用堆栈。例如，就树而言，contains/search方法是检查当前节点数据的结果，OR左子树包含元素，OR右子树包含元素。同样，对于insert，将Node与元素进行比较，然后递归地向右或向左插入，并在遇到null节点时立即分配一个新的叶节点。
就效率而言，递归的开销是将更多的调用放在堆栈上，从而可能产生StackOverflow。
迭代通常更容易调试，因为您对每个步骤的整个过程都有概念。
尾部递归提高了效率，但我不认为这适用于BinaryTree方法。无论哪种方式，如果编写正确，两种实现都具有相似的运行时效率。如果子问题定义得很好，IMO递归看起来更干净。
下面是一个使用递归实现BinaryTree的示例。由于复杂性的原因，省略了remove方法，但我添加了toString作为另一个示例。
public class BinaryTree<E extends Comparable<? super E>> {
protected class Node<T extends E> {
protected T data;
protected Node<T> left;
protected Node<T> right;
protected Node(T data) {
this.data = data;
}
protected Node<T> insert(T data) {
if (data.compareTo(this.data) <= 0) {
if (left == null) {
this.left = new Node(data);
} else {
this.left = this.left.insert(data);
}
} else {
if (right == null) {
this.right = new Node(data);
} else {
this.right = this.right.insert(data);
}
}
return this;
}
protected boolean search(T data) {
if (data.compareTo(this.data) == 0) {
return true;
}
if (this.left != null && data.compareTo(this.data) <= 0) {
return this.left.search(data);
} else if (this.right != null && data.compareTo(this.data) > 0) {
return this.right.search(data);
}
return false;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
String divider = ", ";
if (this.left != null) {
sb.append(this.left.toString()).append(divider);
}
sb.append(String.valueOf(this.data)).append(divider);
if (this.right != null) {
sb.append(this.right.toString()).append(divider);
}
if (sb.length() > divider.length() - 1) {
sb.setLength(sb.length() - divider.length());
}
return sb.toString();
}
}
protected Node<E> root;
public Node<E> insert(E data) {
if (root == null) this.root = new Node(data);
else {
this.root = this.root.insert(data);
}
return this.root;
}
public Node<E> remove(E data) {
return null; // TODO: Implement this
}
public boolean search(E data) {
return root != null && this.root.search(data);
}
@Override
public String toString() {
return String.valueOf(this.root);
}
}