二叉搜索树 class - 删除、搜索、插入、删除和迭代器方法 - 迭代与递归

Question

最近，我开始研究和了解 java 中的二叉树，了解它们的应用以及如何利用它们。我在网上找到了这个二叉树class，我想实现它：

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;
}

现在，我开始简单地为我的 header 创建 header 为我实现的 class:

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;
}
}

如果您愿意，请随意在主 class 中测试这些方法，它们可以很好地执行它们的功能。但是，我在这里关心的是效率。在网上搜索和询问朋友后，我了解到一个叫做'recursion'的东西。现在，我几乎所有的编程知识都是通过学习得来的 Python，而且我以前从未遇到过这个概念。我现在明白我的解决方案使用迭代，但我了解到，当涉及到二叉树时，迭代效率极低。

我已经尝试阅读其他问题和页面，但我仍然无法很好地理解递归。有人可以解释这个概念并展示它在我程序中的删除、插入、迭代器和搜索方法的应用吗？我学得更快，但看到概念的应用对我帮助最大。谢谢你。

注意：看到这些函数的递归解决方案正是我正在寻找的。我想我已经理解了这个概念，但是应用它仍然是我遇到困难的地方。我不能将这个概念准确地应用于此处的移除、插入、搜索和迭代器方法。

Answer 1

递归的基本思想是对每个较小的问题应用一个函数，return结果备份调用堆栈。例如，对于树而言，contains/search方法是检查当前节点数据的结果，OR左子树包含该元素，OR右子树包含该元素。同样对于插入，将节点与元素进行比较，然后递归地向右或向左插入，并在遇到空节点时立即分配一个新的叶节点。

就效率而言，递归的开销是对堆栈跟踪进行更多调用，因此可能会产生 Whosebug。

迭代通常更容易调试，因为您对每个步骤的整个过程都有一个概念。

尾递归提高了效率，但我认为这不适用于 BinaryTree 方法。无论哪种方式，如果编写正确，两种实现都具有相似的运行时效率。如果子问题定义明确，IMO 递归看起来更清晰。

下面是一个使用递归实现二叉树的例子。 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);
    }
}

二叉搜索树 class - 删除、搜索、插入、删除和迭代器方法 - 迭代与递归

binary search tree class - remove, search, insert, remove, and iterator methods - iteration vs recursion

java

recursion

binary-tree