how to correctly create a binary tree? i have an error in function AddNode. tree is not filled. root=NULL

i have class Tree with field root of type Node. then i call AddNode to recursively create nodes.

and desctructor don't work for Nodes.

#include <iostream>
#include <string>

class Node { 
public:
    Node() { 
        std::cout << "Node Constructor\n"; 
        left = NULL;
        right = NULL;
        parent = NULL;
    };
    virtual ~Node() { 
        std::cout << "Node Destructor\n"; 
        Destroy();
    };
    void SetEngWord(std::string eng) { engWord = eng; }
    void SetRusWord(std::string rus) { rusWord = rus; }
    std::string GetEngWord() { return engWord; }
    std::string GetRusWord() { return rusWord; }
    Node* GetLeft() { return left; }
    Node* GetRight() { return right; }
    Node* GetParent() { return parent; }
    void SetLeft(Node* l) { left = l; }
    void SetRight(Node* r) { right = r; }
    void SetParent(Node* p) { parent = p; }
    void PrintWord() { std::cout << engWord << " - " << rusWord << std::endl; }
    void Destroy();
private:
    std::string engWord;
    std::string rusWord;
    Node* left;
    Node* right;
    Node* parent;
};

void Node::Destroy() {
    if (left != NULL) { left->Destroy(); delete left; }
    if (right != NULL) { right->Destroy(); delete right; }
    delete this;
}

class Tree {
public:
    Tree() { 
        std::cout << "Tree Constructor\n"; 
        root = NULL;
    };
    virtual ~Tree() { 
        std::cout << "Tree Destructor\n"; 
        root->Destroy();
    };
    void Add(std::string eng, std::string rus);
    void AddNode(Node* src, Node* parent, Node* n, bool left);
    Node* Search(std::string s);
private:
    Node* root;
};



void Tree::Add(std::string eng, std::string rus) {
    Node* n = new Node;
    n->SetEngWord(eng);
    n->SetRusWord(rus);
    AddNode(root,NULL,n,true);
}

void Tree::AddNode(Node* src, Node* parent, Node* n, bool left) {
    if (src == NULL) {
        src = n; 
        if (src->GetParent() == NULL && parent != NULL) {
            src->SetParent(parent);
            if (left) src->GetParent()->SetLeft(n);
                else  src->GetParent()->SetRight(n);
        }
        return; 
    }
    if (n->GetEngWord() < src->GetEngWord()) { 
        AddNode(src->GetLeft(), src, n, true); 
    }
    else  { 
        AddNode(src->GetRight(), src, n, false); 
    }
}

Node* Tree::Search(std::string s) {
    Node* n;
    n = root;
    while(true) {
        if (n == NULL) break;
        if (n->GetEngWord() < s) n = n->GetLeft();
        if (n->GetEngWord() > s) n = n->GetRight();
        if (n->GetEngWord() == s) break;
    }
    return n;
}

int main()
{
    Tree tree;
    tree.Add("a","aa");
    tree.Add("b","bb");
    tree.Add("c","cc");
    Node* n = tree.Search("b");
    if (n != NULL) n->PrintWord(); else std::cout << "NULL" << std::endl;

    return 0;
}

CodePudding user response：

Okay, I see a few problems.

I would rewrite this method slightly:

void Tree::Add(std::string eng, std::string rus) {
    Node* n = new Node;
    n->SetEngWord(eng);
    n->SetRusWord(rus);
    if (root == nullptr) {
        root = n;
    }
    else {
        AddNode(root,NULL,n,true);
    }
}

That will fix inserting the first element (when root is null). Now you're destructors:

virtual ~Tree() { 
    std::cout << "Tree Destructor\n"; 
    delete node;
};

Your code didn't actually delete the node. Just let the node's destructor do the work.

This is a really bad idea:

void Node::Destroy() {
    if (left != NULL) { left->Destroy(); delete left; }
    if (right != NULL) { right->Destroy(); delete right; }
    delete this;
}

Objects shouldn't delete themselves. This causes no end of problem. This can be way, way simpler.

virtual ~Node() {
     delete left;
     delete right;
};

This works because if left is null, it won't hurt anything. If it points to something, we'll destroy it, which recursively goes down until it's done.

CodePudding user response：

void Tree::AddNode(Node*& src, Node* parent, Node* n, bool left) {
    if (src == NULL) {
        src = n; 
        if (src->GetParent() == NULL && parent != NULL) {
            src->SetParent(parent);
            if (left) src->GetParent()->SetLeft(n);
                else  src->GetParent()->SetRight(n);
        }
        return; 
    }
    if (n->GetEngWord() < src->GetEngWord()) { 
        Node* nn = src->GetLeft();
        AddNode(nn, src, n, true); 
    }
    else  { 
        Node* nn = src->GetRight();
        AddNode(nn, src, n, false); 
    }
}