AVL树的中序遍历，将值保存在数组中

Question

我试图按顺序（从最小值到最大值）遍历 AVL 树，并将值保存在数组中。我怎么能做这样的事？我被困在这个递归中，不知道如何正确地做，这是我目前所知道的：

// Called with node = root node of the AVL tree
// x is the length of the array
// y is 0 at the start
// array is the array I want to fill

void inorder(int* array,Tree_Node* node,int x,int y)
{
    if(!node)
    {
        return;
    }
    inorder(array, node->getLeft(), x, y);

    array[y] = GET_ID(node->getkey());
    y++;
    if (y == x)
    {
        return;
    }
    inorder(array, node->getRight(), x, y);
}

Answer 1

这里的大问题是你的数组索引是错误的。考虑任意节点的 in-order-traversal。您从索引 y 开始在左侧 child 下写下所有内容。然后忽略刚才的操作，将当前节点的值写入索引y。然后，因为您总是递增 y，所以有可能 y > x 在您检查 y == x 的时候写成 out-of-bounds.

我 强烈推荐 用 std::vector 解决这个问题（如果你需要的话，它的 data() 成员函数可以像数组一样使用加工）。这也可以让你摆脱长度限制：

void inorder(Tree_Node* node, std::vector<int>& vector)
{
    if (!node) return;
    inorder(node->getLeft(), vector);

    vector.push_back(GET_ID(node->getkey()));

    inorder(node->getRight(), vector);
}

但是，如果您必须使用数组（因为手动实现 AVL 树通常在教育中完成，并且一些教育工作者非常疯狂地要求您不要使用所有可用的功能），您仍然可以修复这通过从函数返回当前数组索引：

int inorder(int* array, Tree_Node* node, int size, int y = 0)
{
    if (!node) return y;
    y = inorder(array, node->getLeft(), size, y);

    if (y >= size) return y; /* Check before you write! */
    array[y++] = GET_ID(node->getkey());

    return inorder(array, node->getRight(), size, y);
}

AVL树的中序遍历，将值保存在数组中

In-order traversal of an AVL tree, saving the values in an array

c++

struct

avl-tree