我正在尝试用c ++构造一棵普通树。我正在使用的数据结构是具有2个指针的Node类。下一个指针指向该节点的第一个子节点,而另一个指针bros指向该节点的下一个兄弟。

我的代码有问题,由于某种未知的原因,它为一个节点创建了无数的兄弟,但我不知道为什么,
希望您可以看看,并建议我哪里出问题了。
谢谢!

节点类别:

class Node {
private:
    int capacity;
    int price;
    int height;
    int num_of_leafs; // represents the total number of leafs under this branch
    Node* bros;

public:
    Node* next;

    Node(){
        capacity = 0;
        price = 0;
        height = 0;
        next = NULL;
        bros = NULL;
    }
    Node(int capacity_){
        capacity = capacity_;
        price = 0;
        height = 0;
        next = NULL;
        bros = NULL;
    }

    //should return true if this node has no children, false otherwise.
    bool isLeaf()
    {
        if (this->next == NULL) { return 1; }
        else { return 0; }
    }

    // This methoed counts the number of leafs sons of this node.
    int Count_Leafs()
    {
        int num = 0;
        if (this->isLeaf()) { return num; }
        else {
            Node* iter = this->next;
            while ( iter != NULL )
            {
                if ( iter->isLeaf() ) { num++ ; }
                iter = iter->bros;
            }
        }
        return num;
    }

    //this method adds a child to this node.
    void addChild(Node* child)
    {
        if ( child->height != 0 )
        {
            cout << "Node already in tree" ;
            return; }
        if( this->next == NULL )
        {
            this->next = child;
        }
        else {
            Node* iter = this->next;
            while ( iter->getNextBro() != NULL ) { iter = iter->getNextBro(); }
            iter->setNextBro(child);
        }
        child->height = this->height + 1;
    }
        // this methoed checks if current node has brothers
    bool hasBro()
    {
        if ( this->getNextBro() == NULL ) { return 0;}
        else { return 1;}
    }
        Node* getNextBro()
    {
        return bros;
    }

    void setNextBro(Node* next)
    {
        this->bros = next;
    }

    int getHeight()
    {
        return this->height;
    }

    int getNumBros()
    {
        Node* iter = this->bros;
        int num=0;
        while ( iter != NULL )
        {
            num++;
            iter = this->getNextBro();
        }
        return num;
    }


和树的创建:

    Node* s8 = new Node(8);
Node* s5 = new Node(5);
Node* s6 = new Node(6);
for(int i=0; i < 2 ; i++){
    s6->addChild(new Node());
}

Node* s7 = new Node(7);
Node* s2 = new Node(2);
for(int i=0; i < 3 ; i++){
    s2->addChild(new Node());
}

Node* s3 = new Node(3);
Node* s2_2 = new Node(2);
s2_2->addChild(new Node());

Node* s4 = new Node(4);
 for(int i=0; i < 5 ; i++){
    s4->addChild(new Node());
}

Node* s1 = new Node(1);
 for(int i=0; i < 2 ; i++){
    s1->addChild(new Node());
}
Node* s2_3 = new Node(2);
 for(int i=0; i < 4 ; i++){
    s2_3->addChild(new Node());
}
Node* s2_4 = new Node(2);
for(int i=0; i < 3 ; i++){
    s2_4->addChild(new Node());
}
s8->addChild(s5);
cout << "S5 bros: " << s5->getNumBros() << "\n";
cout << "S6 bros: " << s6->getNumBros() << "\n";
s8->addChild(s6);
cout << "S5 bros: " << s5->getNumBros() << "\n";
s5->addChild(s7);
cout << "S5 bros: " << s5->getNumBros() << "\n";
s5->addChild(s2);
s6->addChild(s3);
s6->addChild(s2_2);
s7->addChild(s4);
s7->addChild(s1);
s3->addChild(s2_3);
s3->addChild(s2_4);


谢谢!

最佳答案

getNumBros()遍历this而不是iter

iter = this->getNextBro();


应该:

iter = iter->getNextBro();

08-17 00:31