将二叉树转换为排序数组 [英] Turning a Binary Tree to a sorted array
问题描述
有没有一种方法可以将Binary转换为排序的数组,而不必遍历每个数组索引的树?
Is there a way to turn a Binary to a sorted array without having to traverse the tree for every array index?
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;
}
}
如您所见,如果树中有很多节点,这可能会花费很长时间. 顺便说一句,我忘了表明必须从一开始就遍历整个树才能获得数组的长度.
As you can see this can be take a long time if there are a lot of nodes in the tree. Btw, I forgot to show that the whole tree would have to be traversed at the start to get the length of the array.
推荐答案
是的,您可以这样做:运行 按顺序遍历树 ,保留数组的当前位置,并将节点的值存储在数组的当前位置.
Yes, you can do that: run an in-order traversal of the tree, keep the current position of the array, and store the node's value at the then-current position of the array.
您可以递归进行有序遍历,也可以使用堆栈数据结构进行遍历.如果要递归执行此操作,可以执行以下操作:
You can do in-order traversal recursively, or you can do it with a stack data structure. If you want to do it recursively, you can do this:
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
中分配足够的空间.
Note that in order for the above recursive procedure to work, the caller must allocate enough space in the array
passed into the function.
这篇关于将二叉树转换为排序数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!