有没有一种方法可以将二进制转换为排序数组,而不必遍历树来查找每个数组索引?
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;
}
}
正如您所看到的,如果树中有很多节点,这可能需要很长时间。
顺便说一句,我忘记表明必须在开始时遍历整棵树才能获取数组的长度。
是的,你可以这样做:运行中序遍历 http://en.wikipedia.org/wiki/Tree_traversal#In-order树的当前位置,保留数组的当前位置,并将节点的值存储在数组的当前位置。
您可以递归地进行中序遍历,也可以使用堆栈数据结构来进行。如果你想递归地执行,你可以这样做:
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
传递到函数中。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)