从 Java 中的给定树中检索所有节点

Question

我正在尝试创建一个方法来从作为参数传递的给定树中收集所有节点，但它似乎没有读取任何节点的左分支。

目前我开发的代码如下。

private ArrayList<T> collect(AVLTree<T> tree, AVLNode<T> tRoot, ArrayList<T> l) {

    ArrayList<T> nodes = l;

    if (tRoot == null)
        return null;

    else {
        if (!nodes.contains(tRoot.element())) {
            nodes.add(tRoot.element());

            if (tRoot.getRight() != null) {
                collect(tree, tRoot.getRight(), nodes);
                return nodes;
            }

            else if (tRoot.getLeft() != null) {
                collect(tree, tRoot.getLeft(), nodes);
                return nodes;
            } 
        }
    }

    return nodes;

}

希望你能帮我解决这个问题，因为我现在真的被它困住了...

Answer 1

有两件事导致代码无法运行。

你只检查任何节点的一个分支，这意味着如果检查右分支，即使左边有节点也不会检查左分支
你return来得太早了。您不需要在检查每个分支后立即 return。通过这样做，如果右分支存在，您将再次跳过左分支。

以下修复将起作用。

private ArrayList<T> collect(AVLTree<T> tree, AVLNode<T> tRoot, ArrayList<T> l) {

    ArrayList<T> nodes = l;

    if (tRoot == null)
        return null;

    else {
        if (!nodes.contains(tRoot.element())) {
            nodes.add(tRoot.element());

            if (tRoot.getRight() != null) {
                collect(tree, tRoot.getRight(), nodes);
            }

            if (tRoot.getLeft() != null) {
                collect(tree, tRoot.getLeft(), nodes);
            } 
        }
    }

    return nodes;

}

编辑： 仔细查看代码后。很少有地方存在代码冗余。它们可以简化和清理为以下内容：

private ArrayList<T> collect(AVLTree<T> tree, AVLNode<T> tRoot, ArrayList<T> l) {

    ArrayList<T> nodes = l;

    if (tRoot == null)
        return null;

    if (!nodes.contains(tRoot.element())) {
        nodes.add(tRoot.element());
        collect(tree, tRoot.getRight(), nodes); // this is safe since null check exists at top
        collect(tree, tRoot.getLeft(), nodes);
    }

    return nodes;

}

从 Java 中的给定树中检索所有节点

Retrieving all the nodes from a given tree in Java

java

algorithm

recursion

tree

avl-tree