首页 文章

使用inorder遍历从相同大小的排序数组中填充现有BST

提问于
浏览 次
0

如果我有 int 大小 n 的BST树和 int 大小为 n （不同值的）的排序数组，我想用数组元素填充树 - 我应该通过树上的inorder遍历来做到这样 arr[0] 会位于最左侧节点， arr[n-1] 位于最右侧节点 . （所以需要 O(n) 次）

我试着编写一个天真的递归函数来做它，但它不起作用 . 似乎应该做一些事情来保存数组中的当前索引 .

void insert(Node* v, int* arr) {
    if (!v) {
        return;
    }

    insert(v->left, arr);
    v->key = a[0];
    insert(v->right, arr + 1);
}

我该怎么改变它？

c++ arrays algorithm binary-search-tree

1 回答

  • 1

    你的决定几乎是正确的 . 只需将函数声明更改为：

    void insert(Node* v, int* &arr)

    当你访问正确的子树时，你应该通过下一个方式传递数组的下一个元素：

    insert(v->right, ++arr);

    arr 必须作为参考 & 传递 . 它与在您的情况下将指针的副本传递给数组有关 . 从子节点返回到父节点时，指针将重置为初始数组的第一个元素 arr . 您可以使用指向指向数组的指针获得类似的行为，同时代码中的细微更改也是如此 .

    回复于

相关问题