很简单的问题:
如何递归地创建使用此构造函数的二叉搜索树数组(按顺序):
public class OrderedSet<E extends Comparable<E>> {
private class TreeNode {
private E data;
private TreeNode left, right;
public TreeNode(E el) {
data = el;
left = null;
right = null;
}
}
private TreeNode root;
public int size = 0;
public OrderedSet() {
root = null;
}
最佳答案
按顺序意味着您首先必须遍历树的左侧部分,因此:
TreeNode tree // this is your tree you want to traverse
E[] array = new E[tree.size]; // the arrays length must be equivalent to the number of Nodes in the tree
int index = 0; // when adding something to the array we need an index
inOrder(tree, array, index); // thats the call for the method you'll create
该方法本身可能看起来像这样:
public void inOrder(TreeNode node, E[] array, int index){
if(node == null){ // recursion anchor: when the node is null an empty leaf was reached (doesn't matter if it is left or right, just end the method call
return;
}
inOrder(node.getLeft(), array, index); // first do every left child tree
array[index++]= node.getData(); // then write the data in the array
inOrder(node.getRight(), array, index); // do the same with the right child
}
有点像这样。我只是不确定索引以及它需要在哪里增加。如果您不想担心索引或者不知道树中有多少个节点,则可以使用 ArrayList 并将其最终转换为数组。
通常,更清晰的调用方法是围绕递归方法构建的,如下所示:
public E[] inOrderSort(TreeNode tree){
E[] array = new E[tree.size];
inOrder(tree, array, 0);
return array;
}
关于java - 二叉搜索树到 inOrder 数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16050219/