c++ - AVL Tree - 无法将根传递给插入方法

Question

我在使用 C++ 为我的类(class)设计的 AVL 树时遇到问题。老师指出我们不能使用struct{}，所以我们不得不创建一个Node类和一个Tree类，或者，最终，一个独特的类。

我们遇到的问题是将根节点指针从 main 函数传递到插入函数，这允许我们在二进制研究树中插入新字符串。

这是我们到目前为止编写的代码(它是用我们的语言编写的，基本上是 Nodo = Node 和 Albero = Tree)。提前感谢您能给我们的任何帮助:

#include <iostream>
#include <string>

using namespace std;

/* -------- CLASSE: NODO -------- */

class Nodo {
public:
    string vocabolo;
    Nodo* left;
    Nodo* right;
    Nodo();
    ~Nodo() { }; // Distruttore inline
};

// Costruttore di Nodo
Nodo::Nodo() {
    left = right = NULL;
}

/* -------- CLASSE: ALBERO BINARIO DI RICERCA BILANCIATO -------- */

class Albero {
/*
 private:
    Nodo* root;
*/
public:
    int height(Nodo* nodo);
    int heightDifference(Nodo *nodo);
    void inorder(Nodo *radice);
    Nodo* balance(Nodo* nodo);
    Nodo* ll_rotate(Nodo* padre);
    Nodo* lr_rotate(Nodo* padre);
    Nodo* rl_rotate(Nodo* padre);
    Nodo* rr_rotate(Nodo* padre);
    Nodo* insert(Nodo* nodo, string nuovoVocabolo);
    Nodo* returnRoot();
    Albero();
    ~Albero() { }; // Distruttore inline
};

// Costruttore di Albero
Albero::Albero() {
   // root = NULL;
}

/*
Nodo* Albero::returnRoot() {
    return root;
} */

int Albero::height(Nodo* nodo) {
    int altezza = 0; // Imposto altezza iniziale a zero. Rimarrà così se passo puntatore a root.
    if (nodo != NULL) {
        int l_height = height(nodo->left);
        int r_height = height(nodo->right);
        int max_height = max(l_height, r_height);
        altezza = max_height + 1;
    }
    return altezza;
}

int Albero::heightDifference(Nodo* nodo) {
    int l_height = height(nodo->left);
    int r_height = height(nodo->right);
    int b_factor = l_height - r_height;
    return b_factor;
}

Nodo* Albero::ll_rotate(Nodo* padre) {
    Nodo* temp;
    temp = padre->left;
    padre->left = temp->right;
    temp->right = padre;
    return temp;
}

Nodo* Albero::rr_rotate(Nodo* padre) {
    Nodo* temp;
    temp = padre->right;
    padre->right = temp->left;
    temp->left = padre;
    return temp;
}

Nodo* Albero::lr_rotate(Nodo *padre) {
    Nodo *temp;
    temp = padre->left;
    padre->left = rr_rotate(temp);
    return ll_rotate(padre);
}

Nodo* Albero::rl_rotate(Nodo *padre) {
    Nodo *temp;
    temp = padre->right;
    padre->right = ll_rotate(temp);
    return rr_rotate(padre);
}

Nodo* Albero::balance(Nodo* nodo) {
    int b_factor = heightDifference(nodo);
    if (b_factor > 1) {
        if (heightDifference(nodo->left) > 0) {
            nodo = ll_rotate(nodo);
        } else {
            nodo = lr_rotate(nodo);
        }
    } else if (b_factor < -1) {
        if (heightDifference(nodo->right) > 0) {
            nodo = rl_rotate(nodo);
        } else {
            nodo = rr_rotate(nodo);
        }
    }
    return nodo;
}

Nodo* Albero::insert(Nodo *nodo, string nuovoVocabolo) {
    if (nodo == NULL) {
        nodo = new Nodo;
        nodo->vocabolo = nuovoVocabolo;
    } else if (nuovoVocabolo < nodo->vocabolo) {
        nodo->left = insert(nodo->left, nuovoVocabolo);
        nodo = balance(nodo);
    } else if (nuovoVocabolo >= nodo->vocabolo) {
        nodo->right = insert(nodo->right, nuovoVocabolo);
        nodo = balance(nodo);
    }
    return nodo;
}

void Albero::inorder(Nodo* radice) {
    if (radice == NULL) return;
    inorder(radice->left);
    cout << radice->vocabolo << " ";
    inorder(radice->right);
}

/* -------- FUNZIONE MAIN -------- */

int main(int argc, const char * argv[])
{
    Albero tree;
    tree.insert(root, "ciao");
    tree.insert(root, "pino");
    tree.insert(root, "mauro");
    tree.insert(root, "francesco");
    tree.inorder(root);
    return 0;
}

Answer 1

我认为您在将根节点指针从 main 函数传递到插入函数时遇到问题的原因是根指针是您的 Albero 类的私有(private)成员。类的私有(private)成员只能由 (Albero) 类中的其他成员访问。更多信息链接:http://www.tutorialspoint.com/cplusplus/cpp_data_encapsulation.htm

要解决此问题，您可以简单地做的是创建另一个函数来调用您的插入函数。

void Albero::insertStart(string nuovoVocabolo)
{
   insert(root,nuovoVocabolo);
}

现在您可以多次调用 insertStart()

int main(int argc, const char * argv[])
{
    Albero tree;
    tree.insertStart("ciao");
    tree.insertStart("pino");
    tree.insertStart("mauro");
    tree.insertStart("francesco");
    tree.inorder(root);     //you can apply a similar solution to this function
    return 0;
}