主页 / 问题 / 668960
Accepted
TorSen
Asked:2020-05-22 03:57:14 +0000 UTC2020-05-22 03:57:14 +0000 UTC

二叉搜索树平衡

  • 772

再会。有一个二叉搜索树。平衡是必要的，但是从一棵树做一个对象数组是不可能的。从理论上讲，它应该是这样的，但由于某种原因并不是所有的元素都进入数组。 

void GetMassive(int &n, tree_node * root, DataM *M)
{
    if (root!=NULL)
    {
        GetMassive(n,root->left,M);
        M[n++] = root->info;
        GetMassive(n,root->right,M);
    }
}
c++

1 个回答

  1. Best Answer

    您的代码中有两个问题。

    1. while (root!=NULL). 如果代码进入这个循环，那么它不会退出它，因为变量的值root在循环内不会改变。需要更换while为if.
    2. 函数参数int n。考虑第一个函数调用，n == 0。接下来是线GetMassive(n,root->left,M);。如果左子树不为空，则数组的前几个元素M将被填充。但是在第一个函数调用中，n == 0. 因此，该元素M[0]将被覆盖。要么n将其设为全局变量，要么将其替换int n为int &n.

    可能的解决方案：

    #include <iostream>

typedef int DataM;

struct tree_node {
    DataM info;
    tree_node *left = nullptr;
    tree_node *right = nullptr;

    tree_node(DataM info) : info(info) {}
};

void GetMassive(tree_node *root, DataM *M, int &n) {
    if (root != nullptr) {
        GetMassive(root->left, M, n);
        M[n++] = root->info;
        GetMassive(root->right, M, n);
    }
}

void GetMassive(tree_node *root, DataM *M) {
    int n = 0;
    GetMassive(root, M, n);
}

int main() {
    tree_node *left = new tree_node(1);
    tree_node *right = new tree_node(4);
    tree_node *right_left = new tree_node(3);
    tree_node *right_right = new tree_node(5);
    tree_node *root = new tree_node(2);

    right->left = right_left;
    right->right = right_right;
    root->left = left;
    root->right = right;

    DataM array[5];
    GetMassive(root, array);
    for (int array_i : array) {
        std::cout << array_i << std::endl;
    }
    return 0;
}
    • 2

相关问题