c++ - AVL 树和双向链表

Question

所以，我真的是编程新手，我现在正在上 C++ 类(class)，我需要在其中编写和实现 AVL 树，使用双向链表打印树的内容，级别为等级。老师真的很挑剔，所以我们不能使用标准库中的任何容器。我的双向链表应该可以正常工作，因为我在以前的项目中使用过它，但在尝试将它与 AVL 树组合时出现错误。我知道我的代码可能有很多需要修改的地方，但一次一个步骤。我收到以下错误，所以我想知道你们是否可以帮我弄清楚如何解决它。此外，如果您对如何改进我的代码有任何建议，我将不胜感激。

在‘void AVLTreeSet::print(std::ofstream&) [with ItemType = std::basic_string; std::ofstream = std::basic_ofstream]’:Lab6/main.cpp:80:20:此处需要Lab6/AVLTreeSet.h:152:49: 错误:无法在初始化时将‘LinkedList >::AVLNode*>::Node*’转换为‘AVLTreeSet >::AVLNode*’ AVLNode* n = MyList.remove(i);

这是我的 AVLTree.h:

#pragma once
#include <fstream>
#include "LinkedList.h"

using namespace std;

template <typename ItemType>

class AVLTreeSet {


    struct AVLNode {
        ItemType item;
        int height;
        AVLNode* left;
        AVLNode* right;

        AVLNode(const ItemType& _item, AVLNode* _left = NULL, AVLNode* _right = NULL, int _height = 0) :
                item(_item), left(_left), right(_right), height(_height) {}
    };


    AVLNode* root;
    int size = 0;


public:
    void RemoveBelowRoot(AVLNode *& n, const ItemType& item)
    {
        if (n == NULL)
        {
            return;
        }
        else if(item < n->item)
        {
            RemoveBelowRoot(n->left, item);
        }
        else if(item > n->item)
        {
            RemoveBelowRoot(n->right, item);
        }
        else if(n->left == NULL)
        {
            n = n->right;
        }
        else if (n->right == NULL)
        {
            n = n->left;
        }
        else
        {
            n = findMin(n->right);
            RemoveBelowRoot(n->right, n->item);
        }
        balance(n);
        size--;
        // update height of nodes on this path
    }

    AVLNode * findMin(AVLNode* n)
    {
        if (n == NULL)
        {
            return n;
        }
        else if (n->left->item < n->item)
        {
            findMin(n->left);
        }
        else if(n->left->item > n->item)
        {
            findMin(n->right);
        }
        return n;
    }
    void remove(const ItemType& item) {

        RemoveBelowRoot(root, item);

    }

    bool find(const ItemType& item) {

        if (findBelowRoot(root, item))
        {
            return true;
        }
        return false;

    }
    bool findBelowRoot(AVLNode * n, const ItemType& data)
    {
        if (n->item == data)
        {
            return true;
        }
        else if (data > n->item)
        {
            findBelowRoot(n->right, data);
        }
        else if (data < n->item)
        {
            findBelowRoot(n->left, data);
        }
    }
    void clear()
    {
        while (getHeight(root) != 0)
        {
            // remove
        }
    }

    void addBelowRoot(AVLNode *& n, const ItemType& item)
    {
        if (n == NULL)
        {
            n = new AVLNode(item);
            size++;
        }
        else if (item < n->item)
        {
            addBelowRoot(n->left, item);
        }
        else if(item > n->item)
        {
            addBelowRoot(n->right, item);
        }


    }
    void add(const ItemType& item) {

        addBelowRoot(root, item);

    }
    void print (ofstream& out)
    {
        if (root == NULL)
        {
            return;
        }
        else {
            LinkedList<AVLNode *> MyList;
            MyList.insert(0, root); // add root to Q
            while (MyList.getSize() != 0) // While Q is not empty
                //(figure out how many items are in that level)(levelsize = Q.size();)
            {
                for (auto i = 0; i < MyList.getSize(); i++) // for (int 1 = 0; i < LEVELSIZE; i++)
                {
                    AVLNode* n = MyList.remove(i);
                    out << "level " << i << " " << n->item << "(" << n->height << ") ";
                    if (n->left != NULL) {
                        MyList.insert(MyList.getSize(), n->left);
                    }
                    if (n->right != NULL) {
                        MyList.insert(MyList.getSize(), n->right);
                    }
                }
            }
            out << "\n ";
        }
    }

    void balance (AVLNode *n)
    {
        if (getHeight(n->left) - getHeight(n->right))
        {
            balanceToRight(n);
        }
        if (getHeight(n->right) - getHeight(n->left))
        {
            balanceToLeft(n);
        }
    }
    int getHeight(AVLNode *& n)
    {
        if (n == NULL)
        {
            return 0;
        }
        else
        {
            return n->height;
        }
    }
    void balanceToRight(AVLNode * n)
    {
        if (getHeight(n->left->right) > getHeight(n->left->left))
        {
            rotateLeft(n->left);
        }
        rotateRight(n);
    }
    void rotateRight(AVLNode *&n)
    {
        AVLNode * k = n->left;
        n->left = k->right;
        k->right = n;
        n = k;
        // update heights of k and n
    }
    void rotateLeft(AVLNode *& n)
    {
        AVLNode * k = n->right;
        n->right = k->left;
        k->left = n;
        n = k;
        // update heights of k and n
    }
    void balanceToLeft(AVLNode * n)
    {
        if (getHeight(n->right->left) > getHeight(n->right->right)) // check with TAs if this is right
        {
            rotateRight(n);
        }
            rotateLeft(n);

    }
    /*void updateHeight(AVLNode *& n)
    {

    }*/


};

现在这是我的 LinkedList.h

#pragma once

#include <iostream>
#include <cstddef>
#include <fstream>

using namespace std;

template <typename ItemType>

class LinkedList {


    struct Node {
        ItemType item;
        Node *next;
        Node *prev;

        Node(const ItemType &_item, Node *_next = NULL, Node *_prev = NULL) :
                item(_item), next(_next), prev(_prev) { }
    };


    Node *head;
    Node *tail;
    int size = 0;

public:

    ~LinkedList()
    {
        clear();
    }
    void insert(int index, ItemType& item) {

        if (index > size || size < 0)
        {
            return;
        }

        Node * newNode = new Node(item);

        if (size == 0)
        {

            head = newNode;
            tail = newNode;
            newNode->next = NULL;
            newNode->prev = NULL;
            size++;
        }

        else if (index == 0)
        {
            head->prev = newNode;
            newNode->next = head;
            head = newNode;
            size++;

        }
        else if (index == size) //INSERTING AT THE END
        {
            newNode->prev = tail;
            newNode->next = NULL;
            tail->next = newNode;
            tail = newNode;
            size++;

        }
        else {
            Node* n = find_node(index);
            newNode->next = n;
            newNode->prev = n->prev;
            n->prev->next = newNode;
            n->prev = newNode;
            size++;
        }


    }

    Node * remove(int index) {

        if (head == NULL || index >= size || index < 0)
        {
           return NULL;
        }
        else {
            Node* name = find_node(index);
            Node * n;
            if (size == 1) // REMOVE THE ONLY NODE
            {
                n = head;
                head = NULL;
                tail = NULL;
                size--;

            }
            else if (index == 0) //REMOVE THE FIRST NODE WHEN THERE'S MORE THAN ONE IN THE LIST
            {
                n = head;
                head = head->next;
                head->prev = NULL;
                size--;


            }
            else if (index == size-1) //REMOVE THE LAST WHEN THERE'S MORE THAN ONE NODE IN THE LIST
            {
                n = tail;
                tail = n->prev;
                tail->next = NULL;
                size--;

            }
            else
            {
                n = find_node(index);
                n->prev->next = n->next;
                n->next->prev = n->prev;
                size--;
            }

            delete n;
            return name;
        }
    }

    Node * find_node(int index)
    {
        Node * n = NULL;

        if (0 <= index && index <= size/2)
        {
            n = head;
            for (int i = 0; i < index; i++)
            {
                n = n->next;
            }
        }
        else if (size/2 < index && index <= size-1)
        {
            n = tail;

            for (unsigned i = size-1; i > index; i--)
            {
                n = n->prev;
            }
        }
        return n;
    }
    int getSize()
    {
        return size;
    }
/*    void print(LinkedList <string>& list, ofstream& out, int i)
    {
        if(head == NULL)
        {
            return;
        }

        out << "node " << i << ": " << getItem(i) << "\n";
    }

    Node* getItem(const int index)
    {
        if (index > size)
        {
            return  NULL;
        }
        Node* temp = head;

        for (unsigned i = 0; i < size; i++)
        {
            if (i == index)
            {
                return temp;
            }
            temp = temp-> next;
        }
        return NULL;

    }*/

/*    int find(const ItemType& item) {

        Node * NodeP = head;

        for (unsigned i = 0; i < size; i++)
        {
            if (NodeP->item == item)
            {
                return i;
            }
            NodeP = NodeP->next;
        }
        return -1;

    }*/
    void clear()
    {
        while (size != 0){
            remove(0);
        }
    }

};

非常感谢!

Answer 1

LinkedList::remove 返回一个 LinkedList::Node 指针。您正在尝试将其分配给 AVLTreeSet::AVLNode 指针。

您要查找的 AVLTreeSet::AVLNode * 在返回的 Node 指针的 item 成员中。

你可以这样做:

LinkedList<AVLNode *>::Node* n = MyList.remove(i);
AVLNode *treeNode = n->item;

注释

• 如果没有找到任何东西，您应该检查 NULL 作为 remove 的返回值。
• remove 实际上是删除节点然后返回它。然后您正在访问已被删除的内容，即未定义的行为。您真的需要先解决这个问题，然后再进一步。
• 您的 for 循环将仅删除大约一半的对象，因为您正在从列表中删除项目，同时仍使用 i 在列表中进一步迭代。