是否可以从二叉搜索树返回排序数组(仅使用局部变量,不使用类变量/全局变量)
我能够仅使用局部变量来填充排序数组,如下所示。请参阅下面的中序函数
但是,如下所示,我使用函数的返回值来告诉右子树/前一帧,下一次插入的数组索引应该是什么。
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。
最佳答案
我认为你应该使用 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,这是更好的。
关于java - 如何从 bst 返回排序数组(仅使用局部变量)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33771707/