二叉搜索树，中序横向 return 泛型数组

Question

public class Bst<E extends Comparable<E>> {

private BstNode<E> root;

    public Bst(E data) {
       root = new BstNode<>(data);
    }

    public void add(E data) {
        root = arr(data,root);
    }

    private BstNode<E> add(E data, BstNode<E> startNode) {
        if (startNode == null) {
            startNode = new BstDupNode<>(data);
        } else if (data.compareTo(startNode.data) < 0) {
            startNode.left = add(data, startNode.left);
        } else {
            startNode.right = add(data, startNode.right);
        }
        return startNode;
    }
   
    public E[] getAllData(E[] template) {
        index = 0;
        inorderTraversal(template, root, index);
        return template;
    }

    private int index;

    private void inorderTraversal(E[] template, BstNode<E> startNode, int index) {
        if (startNode != null) {
            inorderTraversal(template,startNode.left, index);
            template[index++] = startNode.data;
            inorderTraversal(template, startNode.right, index);
        }
    }


    private static class BstNode<E extends Comparable<E>> {
        public int count;
        public E data;
        public BstNode<E> left , right;

        public BstDupNode(E data) {
            this.data = data;
            left = right = null;
        }
    }

    public static void main(String[] args) {
        Bst<Integer> hello = new BstDup<>(7);
        hello.add(8);
        hello.add(3);
        hello.add(1);
        hello.add(6);
        hello.add(4);
        hello.add(10);
        hello.add(14);
   }
}

我得到的结果类似于

[7, 8, 10, 14, null, null, null, null, null, null, null]

不知道为什么时不时会把索引归零。因为既然我设置了全局变量，它就应该随着隐居的继续而不断计数，或者至少我是这么认为的。我想了解到底不只是回答，如果你能提供一些解释，我将不胜感激。谢谢。

Answer 1

Java 使用 pass-by-value，这意味着方法获取其参数的 values，但是这些与来电者的副本分开；因此，当您重新分配方法参数时，调用者看不到该重新分配。

比如这样的方法：

void increment(int i) {
    ++i;
}

没有任何效果：该方法递增其 i 的副本，但没有使用该副本。

在你的情况下，问题是你的 inorderTraversal 方法按值获取参数 index - 所以它有自己的副本 - 然后它递增该副本，这很好，但是它的调用者永远不会看到这种变化。

要解决此问题，我建议使用 inorderTraversal return 更新后的 index:

    private int inorderTraversal(E[] template, BstNode<E> startNode, int index) {
        if (startNode != null) {
            index = inorderTraversal(template,startNode.left, index);
            template[index++] = startNode.data;
            index = inorderTraversal(template, startNode.right, index);
        }
        return index;
    }

二叉搜索树，中序横向 return 泛型数组

Binary Search Tree, In-order transversal return generic array

java

generics

recursion

binary-search-tree

inorder