java - 如何从 bst 返回排序数组(仅使用局部变量)？

Question

是否可以从二叉搜索树返回排序数组(仅使用局部变量，不使用类变量/全局变量)

我能够仅使用局部变量来填充排序数组，如下所示。请参阅下面的中序函数

但是，如下所示，我使用函数的返回值来告诉右子树/前一帧，下一次插入的数组索引应该是什么。

package Trees;


public class BinaryTreeToSortedArray
{
    public static void main(String[] args)
    {
        Tree tree = new Tree();

        tree.insert(10);

        tree.insert(5);
        tree.insert(15);

        tree.insert(3);
        tree.insert(7);
        tree.insert(12);
        tree.insert(18);

        tree.insert(1);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);
        tree.insert(11);
        tree.insert(14);
        tree.insert(16);
        tree.insert(20);

        int[] a = new int[100];
        tree.inorder(tree.root, a, 0);
        tree.display(a);
    }
}

class Tree
{
    Node root;

    public Tree()
    {
        // TODO Auto-generated constructor stub
        this.root = null;
    }

    void insert(int data)
    {
        Node node = new Node(data);

        if(root == null)
            root = node;
        else
        {
            Node trav = root;
            Node pretrav = root;
            while(trav != null)
            {
                pretrav = trav;

                if(node.data < trav.data)
                    trav = trav.left;
                else
                    trav = trav.right;
            }
            if(node.data < pretrav.data)
                pretrav.left = node;
            else
                pretrav.right = node;
        }
    }

    /* README : The 'pos' that is passed here, is only for initialization to 0 */
    int inorder(Node node, int[] a, int pos)
    {
        if(node == null)
            return pos;

        pos = inorder(node.left, a, pos);
        //System.out.print(node.data + " ");
        a[pos++] = node.data;
        pos = inorder(node.right, a, pos);

        return pos;
    }

    void display(int[] a)
    {
        for(int i = 0 ;a[i]>0;i++)
        {
            System.out.print(a[i] + " ");
        }
    }
}

class Node
{
    int data;
    Node left;
    Node right;

    public Node(int data)
    {
        // TODO Auto-generated constructor stub
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

PS:想要严格返回一个数组，而不是一个ArrayList。

Answer 1

我认为你应该使用 ArrayList (或任何 List 实现)而不是数组。这将使您从跟踪索引中解放出来。

public void inorder(Node n, List l){
    if (n == null){
        return;
    }
    inorder(n.left, l);
    l.add(n.data);
    inorder(n.right, l);
}

此外，如果您事先不知道树中有多少个元素，那么它永远不会抛出ArrayIndexOutOfBoundException，这是更好的。