C++ 指针、引用和 AVL 树

Question

我是一名大学生，作为我的最后一项任务，我必须创建 AVL Tree 字典。我正在尝试自己编写它，我已经设法编写了很多，但我有一个问题。当我将我所有的 getter 和 setter 用于随机节点甚至它们的向量时，它就可以工作。但是当我试图在 Tree 方法中设置根目录时，它失败了。我的意思是，它只工作一次但是一旦我尝试使用 root 调用它 avl.getRoot 或在我的实现中作为 root 调用它，它就会失败。我的程序崩溃了。这是我做过的最难的程序。你能解决我的问题并给我一些重要的提示吗？先感谢您。

Main.cpp - 测试

  Node n1("clown",1);
    Node n2("cat",1);
    Node n3("kid",1);
    Node n4("wasp",1);
    n1.setLSon(&n2);
    std::cout<<"ENG: "<<n1.getLSon().getWord().getEng()<<std::endl;
    n1.setRSon(&n3);
    std::cout<<"ENG: "<<n1.getRSon().getWord().getEng()<<std::endl;
    n1.setParent(&n4);
    std::cout<<"ENG: "<<n1.getParent().getWord().getEng()<<std::endl;
    if(n2.hasLSon)
    n2.getLSon();
    else
    std::cout<<"n2 does not have a left son"<<std::endl;
    AVL_Tree avl;
    avl.addNode("cirrus",1);
    avl.addNode("monkey",1);
    std::cout<<"ENG: "<<avl.branches[0].getWord().getEng()<<std::endl;
    std::cout<<"ENG: "<<avl.branches[1].getWord().getEng()<<std::endl;
    avl.branches[0].setLSon(&avl.branches[1]);
    std::cout<<"ENG: "<<avl.branches[0].getLSon().getWord().getEng()<<std::endl;
    avl.branches[1].setParent(&avl.branches[0]);
    std::cout<<"ENG: "<<avl.branches[1].getParent().getWord().getEng()<<std::endl;
/*Error is being called here*/
    **std::cout<<"ROOT: "<<avl.getRoot().getWord().getEng()<<std::endl;** 
}

树class：函数有问题

AVL_Tree::AVL_Tree()
{
    root=NULL;
}

void AVL_Tree::sort()
{

}

Node AVL_Tree::getRoot()
{
    return *root;
}

void AVL_Tree::addNode(std::string eng,int count)
{
    int i=0;
    branches.push_back(Node(eng,count));
    for(i;i<branches.size();i++)
    {
        if(branches[i].getWord().getEng()==eng)
        break;
    }
    if(branches.size()==1)
    {
    root=&(branches[i]);
    std::cout<<"ROOT DODANY"<<endl;
    std::cout<<root->getWord().getEng()<<std::endl;
    }
    else
    std::cout<<"ROOTEM JEST: "<<root->getWord().getEng()<<std::endl;
    if(!isBinary());
    sort();
}

树Class

class AVL_Tree
{
    public:
                                AVL_Tree();
            void                sort();
            void                addNode(std::string eng,int count);
            void                deleteNode(std::string eng);
            Node                findNode(std::string eng);
            Node                getRoot();
            bool                isBinary();
            bool                isNode(std::string eng);
            std::vector<Node>   branches;

    private:
            Node                *root;
            int                 leftFactor;
            int                 rightFactor;

};

Node.cpp

Node::Node(std::string eng,int count):word(eng,count)
{
    parent=NULL;
    l_son=NULL;
    r_son=NULL;
    hasLSon=false;
    hasRSon=false;
}

Node::~Node()
{
    parent=NULL;
    l_son=NULL;
    r_son=NULL;
}

Word Node::getWord()
{
    return word;
}

Node Node::getLSon()
{
    return *l_son;
}

Node Node::getRSon()
{
    return *r_son;
}

Node Node::getParent()
{
    return *parent;
}

void Node::setLSon(Node *n)
{
    l_son=n;
    hasLSon=true;
}

void Node::setRSon(Node *n)
{
    r_son=n;
    hasRSon=true;
}

void Node::setParent(Node *n)
{
    parent=n;
}

Node.h

class Node
{
    public:
                            Node(std::string eng,int count);
                            ~Node();
            Word            getWord();
            Node            getLSon();
            Node            getRSon();
            Node            getParent();
            void            setLSon(Node *node);
            void            setRSon(Node *node);
            void            setParent(Node *node);
            bool            hasLSon;
            bool            hasRSon;
    private:
            Node            *parent;
            Node            *l_son;
            Node            *r_son;
            Word            word;
};

Answer 1

在您的 addNode 中，您将指向 branches 的元素的指针分配给 root。稍后调用 addNode 将添加一个新分支，为向量重新分配内存，并使 root 指针无效。当您尝试使用此无效指针时，这会导致稍后崩溃。

你在 addNode 末尾的 if 语句后也有一个分号，我认为你不想在那里。在打开所有警告的情况下进行编译，以便收到有关此类事件的通知。

C++ 指针、引用和 AVL 树

C++ Pointers, references and AVL Tree

c++

tree

pointers

reference

data-structures