有没有一种方法可以将二进制转换为排序数组,而不必为每个数组索引遍历树?
Node root;
Node runner;
int current_smallest;
void findsmallest(Node root){
//Pre-order traversal
if(root == null){
return;
}else{
runner = root;
if(current_smallest == null){
current_smallest = runner.element;
}else{
if(current_smallest > runner.element){
current_smallest = runner.element;
}
}
findsmallest(runner.left);
findsmallest(runner.right);
}
}
void fill_array( int [] array ){
for(int i =0; i < array.length(); i++){
findsmallest(root);
array[i] = current_smallest;
}
}
如您所见,如果树中有很多节点,这可能会花费很长时间。 顺便说一句,我忘了证明必须在开始时遍历整棵树才能获得数组的长度。
最佳答案
是的,你可以这样做:运行 in-order traversal树的当前位置,保留数组的当前位置,并将节点的值存储在数组当时的当前位置。
您可以递归地进行中序遍历,也可以使用堆栈数据结构来进行。如果你想递归地做,你可以这样做:
int fill_array(Node root, int [] array, int pos) {
if (root.left != null) {
pos = fill_array(root.left, array, pos);
}
array[pos++] = root.element;
if (root.right != null) {
pos = fill_array(root.right, array, pos);
}
return pos; // return the last position filled in by this invocation
}
请注意,为了使上述递归过程起作用,调用者必须在传递给函数的 array
中分配足够的空间。
关于java - 将二叉树转换为排序数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16180569/