java - 将二叉树转换为排序数组

Question

有没有办法将二进制转换为排序数组，而不必为每个数组索引遍历树？

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;
    }
}

如您所见，如果树中有很多节点，这可能需要很长时间。顺便说一句，我忘了表明必须在开始时遍历整个树才能获得数组的长度。

score 17 · Accepted Answer

是的，您可以这样做：按顺序遍历树，保持数组的当前位置，并将节点的值存储在数组的当前位置。

您可以递归地进行顺序遍历，也可以使用堆栈数据结构进行遍历。如果你想递归地这样做，你可以这样做：

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传递给函数的过程中分配足够的空间。

score 4 · Accepted Answer

二叉树可以用数组表示；如果是这种情况，您需要做的就是对数组进行排序。

以下是有关在数组中表示树的更多信息： wikipedia

这不一定是最节省空间的表示；“带有引用的节点”表示可能会浪费更少的空间。

score 4 · Accepted Answer

你想要的是一个有序的遍历，它通常以递归方式实现，如：

遍历左子树。
处理此节点（即作为数组中的下一个元素插入）
遍历右子树。

score 0 · Accepted Answer

Here is java code for same:

int[] result = new int[9];
fillArray(tree, result, 0);

public int fillArray(Tree tree, int[] result, int index) {
        if (tree.left != null) {
            index = fillArray(tree.left, result, index);
        }
        result[index++] = tree.val;

        if (tree.right != null) {
            index = fillArray(tree.right, result, index);
        }

   return index;
}

java - 将二叉树转换为排序数组

4 回答 4

Related

Reference