5
\$\begingroup\$

This is a binary tree using classes. What can be improved upon?

ClassTree.h

#pragma once

class Node{

private:
    int id;
    Node *left;
    Node *right;
    static int count;

public: 
    Node();
    Node * first(Node *root);
    void search(Node *root, int digit);
    Node * insert(Node *root, int digit);
    void print_tree(Node *root, int level);
    void max_internal(Node *root);
    Node * delete_key(Node *root, int digit);
    void delete_tree(Node * root);
    static int get_count();
    static void zero_count();
};

ForClass.cpp

#include "ClassTree.h"
#include <iostream.h>

int Node::count = 0;

Node::Node(){
    count++;
}

int Node::get_count(){
    return count;
}

void Node::zero_count(){
    count = 0;
}

Node * Node::first(Node *root){
    if(count){
        cout << "There is an old tree!" << endl;
        return root;
    }
    else{
        cout << "Root's id: ";
        int temp = 0;
        cin >> temp;
        root = new Node;
        root->id = temp;
        root->left = 0;
        root->right = 0;
    }
    return root;
}

void Node::search(Node *root, int digit){
    Node *pv = root;
    bool found = false;
    while (pv && !found){
        if (digit == pv->id){
            cout << "Digit " << digit << " was found!";
            found = true;
        }
        else if (digit < pv->id){ 
            pv = pv -> left;
        }
        else{
            pv = pv -> right;
        }
    }
    cout << "Digit " << digit << " was not found!";
}

Node * Node::insert(Node *root, int digit){
    Node *pv = root; 
    Node *prev = 0;
    while (pv){
        prev = pv;
        if (digit == pv->id){
            return pv;
        }
        else if (digit < pv->id){ 
            pv = pv -> left;
        }
        else{
            pv = pv -> right;
        }
    }
    Node *pnew = new Node;
    pnew->id = digit;
    pnew->left = 0;
    pnew->right = 0;
    if (digit < prev->id){
        prev->left = pnew;
    }
    else{
        prev->right = pnew;
    }
    return pnew;

}

void Node::print_tree(Node *root, int level){
    if( !get_count() ){
        cout << "The tree is empty. You need a new tree!\n";
        return;
    }
    if (root){
        print_tree(root->left, level + 1);
        for (int i = 0; i < level; i++){
            cout << " ";
        }
        cout << root->id << endl; 
        print_tree(root->right, level +1); 
    }
}

void Node::max_internal(Node *root){
    if( !get_count() ){
        cout << "The tree is empty. You need a new tree!\n";
        return;
    }
    if(root->left == 0 && root->right == 0){
        cout << "There is no leafs in the tree! Only root: "; 
        cout << root->id << endl;
        return;
    }
    int temp_max = root->id;
    Node *pv = root;
    while (pv){
        temp_max = pv->id;
        pv = pv -> right;
        if(pv->left == 0 && pv->right == 0){
            break;
        }
    }
    cout << "Max internal: " << temp_max << endl;
}


Node * Node::delete_key(Node *root, int digit){
   if (digit < root->id){
      root->left = delete_key(root->left, digit);
      }
   else if (digit > root-> id){
      root->right = delete_key(root->right, digit);
      }
   else{
      Node *v = 0;
      Node * P = root;
      if (!root->right){
          root = root->left;
      }
      else if (!root->left){
         root = root->right;
      }
      else{
         v = root->left;
         if (v->right){
             while (v->right->right){
                 v = v->right;
             }
            root->id = v->right->id;
            P = v->right;
            v->right = v->right->left;
         }
         else{
            root->id = v->id;
            P = v;
            root->left = root->left->left;
         }
      }
      count--;
   }
   return root;
}

void Node::delete_tree(Node * root){
    if ( ! root ){
        return;
    }
    delete_tree(root->left);
    delete_tree(root->right);
    delete root;
    root = 0;
}

ForMain.cpp

#include "ClassTree.h"
#include <stdlib.h>
#include <iostream.h>

void generation(Node *root){
    int temp_count = Node::get_count();
    int low_range = 0;
    cout << "Low range: ";
    cin >> low_range;

    int high_range = 0;
    do{
        cout << "High range: ";
        cin >> high_range;
        if(high_range < low_range){
            cout << "Low range is bigger than high range! Try to enter again!";
        }
    }while(high_range < low_range);

    int amount = 0;
    cout << "Number of nodes: ";
    cin >> amount;

    for(int i = 0; i < amount - 1; ++i){
        root->insert(root, ( rand() % (high_range - low_range) + low_range) );
    }
    cout << Node::get_count() - temp_count << " new nodes was entered in the tree!\n";
}

bool menu(Node *root){
    int solution = 0;
    int temp = 0;
    cout << "\nMenu:\n1 - generation\n2 - insert\n3 - count\n4 - max internal \n5 - search \
        \n6 - print\n7 - delete key\n8 - delete tree\n9 -  new tree\n0 - exit.\nYour solution: ";
    cin >> solution;
    cout << endl;
    switch(solution){
    case 0:{
        root->delete_tree(root);
        cout << "The tree was deleted!\nExit.\n\n";
        return false;
           }
    case 1:{
        generation(root);
        break;
           }
    case 2:{
        if( !Node::get_count() ){
        cout << "The tree is empty. You need a new tree!\n";
        return 0;
        }
        cout << "New digit: ";
        cin >> temp;
        root->insert(root, temp);
        break;
           }
    case 3:{
        cout << "Number of nodes in the tree: "<< Node::get_count() << endl;
        break;
           }
    case 4:{
        root->max_internal(root);
        break;
           }
    case 5:{
        cout << "Digit for search: ";
        cin >> temp;
        root->search(root, temp);
        break;
           }
    case 6:{
        root->print_tree(root, 0);
        break;
           }
    case 7:{
        if( !Node::get_count() ){
            cout << "The tree is empty. You need a new tree!\n";
            break;
        }
        cout << "Node for delete: ";
        cin >> temp;
        root->delete_key(root, temp);
        break;
           }
    case 8:{
        root->delete_tree(root);
        Node::zero_count();
        cout << "Tree was deleted!\n";
        break;
           }
    case 9:{
        root = root->first(root);
        break;
           }
    default:{
        cout << "What do you mean by that?\n";
        break;
            }
    }
    return true;

}

Main.cpp

#include "ClassTree.h"

bool menu(Node *root);

int main(){
    Node *P1 = 0;
    P1 = P1->first(P1);
    do{
    }while( menu(P1) );
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ There is so much wrong with this. It's going to take me a day to write something up. \$\endgroup\$ – Martin York Oct 18 '14 at 17:30
  • \$\begingroup\$ I understand that my knowledge of c++ is not great. :-( But I want improve my skills in programming \$\endgroup\$ – dimanist Oct 18 '14 at 19:26
8
\$\begingroup\$

OK, let's start at the first question you should ask yourself when writing code:

Am I helping the reader figure out what's going on?

Let's start by looking at Main.cpp. Here, there are a few small clues that might help me figure out what's going on, but they're misleading. First, you are including a file called ClassTree.h. This name suggests to me that it provides a class called ClassTree, or at the very least a module that is concerned with class trees. What's a class tree? Well, I've never heard of it before, but the name suggest that it's a tree of classes. Maybe it's for something in biology, but it seems more like it's for some sort of code analysis. Next we have main, which has no comments, and only references the names P1, Node, and menu, which are very close to the least informative names you could have in a program. Well, let's take a look at what menu does, maybe we can get a hint. Wait, there's no definition for menu, only a declaration. We don't even have a clue as to where it's defined; I guess we'll have to look at a Makefile or grep for menu in the other files in this directory.

So this brings me to my first concrete suggestion: Never declare a function that's defined in an unrelated file. Instead, declare them in a header file with the same basename as the source file that defines them.

Second concrete suggestion: Give things meaningful names. What does this program do? I don't know, the source file is named Main.cpp and the library that defines its core functionality is called ForMain.cpp.

Third concrete suggestion: Document your classes and functions! Documentation starts with a good name, but when some behavior isn't obvious from the name, it should be present in a comment.

Now let's visit ClassTree.h. As alluded to earlier, this isn't a very good name for this file. It's not a tree of classes. The data structure you're defining is a binary tree. The fact that it's implemented using a class is (a) in some sense an implementation detail, and therefore not the thing to emphasize in its name, and (b) essentially assumed in C++. So let's call it BinaryTree.h.

As a relatively minor point, let me say that you should always put your code in namespaces. When you put everything into the global namespace, you are significantly increasing the likelihood of name collisions, which can sometimes not be detected by the compiler or linker and which may lead to subtly wrong behavior at run time.

Now let's visit your class design. Others have mentioned some of the problems here, but most of them come from one error at the root: You have inappropriately overspecialized the design of this class to this specific use case. You've written a little test program here to exercise your binary tree, but you've basically made the tree unusable in other programs. Let's look at some of the problems that arise from that:

  • The count mechanism makes the assumption that you will only ever have one tree in your program. If you have multiple trees, they will trample each other's counts.
  • You have committed yourself to int data in the nodes. But binary trees like this work with lots of data types, as long as they can be ordered and compared for equality. This should be a template class!
  • Node's methods have confusing names and signatures, and no documentation. This probably wasn't obvious to you since you only wrote a short program using Node around the same time as you wrote Node.

There are a few other problems as well, which I'll call out as I lay out a possible implementation of BinaryTree.h (I've written this in C++11, which is now widely available; I've avoided some improvements that could be made using C++14):

#pragma once

#include <cassert>
#include <functional>
#include <iostream>

Quick note -- include the C++ headers, not the C-ish headers like iostream.h — they're ancient.

#include <memory>
#include <utility>

namespace dimanist_binary_tree {

Normally I give the public API before private implementation details, but the Node class illustrates many of the points I want to make, so here it is.

namespace detail {
template <typename T,
          typename Less = std::less<T>,
          typename Eq = std::equal_to<T>>

Note: In C++14, these should be std::less<> and std::equal_to<>, which are more flexible than std::less<T> and std::equal_to<T>.

class Node : std::enabled_shared_from_this<Node> {
  public:
    using LessType = Less;
    using EqType = Eq;

    Node(T&& t) : data(std::move(t)) {}

    // In-place construction of data
    template <typename... Args>
    Node(Args&&... args) : data(std::forward<Args>(args)...) {}

    // Inserts a new node into this tree with t as its data.
    void insert(T&& t, Less less) {
        return insert(std::make_shared<Node>(std::move(t)), less);
    }
    // Inserts node into this tree.
    void insert(std::shared_ptr<Node> node, Less less);

A couple notes on insert: - There's no need to pass the root node as its first argument; this is already the root node of a subtree. This is C++, not C! - Passing raw pointers around makes it difficult to make sure you're neither leaking memory nor keeping references to memory that has already been freed. std::shared_ptr<T> makes our life easier in this instance.

    // If t is present in this tree, one node containing it is removed.
    // The return value contains the new root of this tree and a bool
    // that is true if any node was removed.
    std::pair<std::shared_ptr<Node>, bool> erase(const T& t, Less less, Eq eq);

    // If t is present in this tree, all nodes containing it are removed.
    // The return value contains the new root of this tree and an int
    // giving the number of nodes removed.
    std::pair<std::shared_ptr<Node>, int> erase_all(const T& t, Less less, Eq eq);

I know your current implementation prevents multiple copies of t from being inserted (though only because I read carefully through the code!), but I think for that to be a reasonable thing to do, you need to modify the API, which makes it more complicated.

// Returns a node containing t, or nullptr if this tree does not contain t.
std::shared_ptr<const Node> find(const T& t, Less less, Eq eq) const;
std::shared_ptr<Node> find(const T& t, Less less, Eq eq);

I've provided two versions of this method in order to provide deep const semantics to the class. You're allowed to search for a value given a const Node&, but you can't use the returned value to modify the tree. I used find rather than search since that is the name the standard library uses for this functionality. Note also that I return the node rather than printing to std::cout; if the caller wants to print, they can do that themselves. This provides them also with the flexibility to do other things based on the return value.

    // Returns the maximum node in this tree.
    std::shared_ptr<const Node> max() const;
    std::shared_ptr<Node> max();

    // Returns the minimum node in this tree.
    std::shared_ptr<const Node> min() const;
    std::shared_ptr<Node> min();

    std::ostream& print_tree(std::ostream& os, int level);

Note that I pass a std::ostream& so that the user can print to std::cout, std::cerr, a file stream, etc, instead of restricting the choice to std::cout.

  private:
    // Compute the new root assuming this node is being removed.
    std::shared_ptr<Node> reroot();

    std::shared_ptr<Node> left;
    std::shared_ptr<Node> right;
    T data;
};
}  // namespace detail

// A binary tree
template <typename T,
          typename Node = detail::Node<T>,
          typename Less = typename Node::LessType,
          typename Eq = typename Node::EqType>
class BinaryTree {

So the purpose of BinaryTree here is to prevent users having to pass Node pointers (or shared_ptrs) directly, checking for nullptr, etc. It makes this whole class easier to use.

  public:
    using Less = typename Node::LessType;
    using Eq = typename Node::EqType;

    BinaryTree(Less less = Less(), Eq eq = Eq()) : less(less), eq(eq) {}
    bool empty() const { return !root; }

    // Insert a new node with t as its data. This node will be inserted
    // even if a node with t as its data is already in the tree.
    void insert(T t) {
        if (!root) {
            root = std::make_shared<Node>(std::move(t));
        } else {
            root->insert(std::move(t), less);
        }
     }

     // Insert a new node with a T constructed from args as its data.
     template <typename... Args>
     void insert(Args&&... args) {
         auto new_node = std::make_shared<Node>(std::forward<Args>(args)...);
         if (!root) {
             root = std::move(new_node);
         } else {
             root->insert(std::move(new_node), less);
         }
     }

     // If any node with t as its data is in this tree, removes one such node.
     // Returns true if any node was removed.
     bool erase(const T& t) {
         if (!root) return false;
         auto result = root->erase(t, less, eq);
         root = std::move(result.first);
         return result.second;
     }

     // Removes all nodes that have data equal to t. Returns the number of
     // nodes removed.
     int erase_all(const T& t) {
         if (!root) return 0;
         auto result = root->erase_all(t, less, eq);
         root = std::move(result.first);
         return result.second;
     }

     // Returns a subtree rooted by t, or nullptr if t is not in this tree.
     BinaryTree<T, const Node, Less, Eq> find(const T& t) const {
       if (!root) { return {less, eq}; }
       return {root->find(t, less, eq), less, eq};
     }

     BinaryTree find(const T& t) {
       if (!root) { return {less, eq}; }
       return {root->find(t, less, eq), less, eq};
     }

     // Returns a subtree rooted at the maximum node in this tree.
     BinaryTree<T, const Node, Less, Eq> max() const {
       if (!root) { return {less, eq}; }
       return {root->max(), less, eq};
     }

     BinaryTree max() {
       if (!root) { return {less, eq}; }
       return {root->max(), less, eq};
     }

     // Returns a subtree rooted at the minimum node in this tree.
     BinaryTree<T, const Node, Less, Eq> min() const {
       if (!root) { return {less, eq}; }
       return {root->min(), less, eq};
     }

     BinaryTree min() {
       if (!root) { return {less, eq}; }
       return {root->min(), less, eq};
     }


  private:
    BinaryTree(std::shared_ptr<Node> root, Less less, Eq eq)
        : root(std::move(root)), less(less), eq(eq) {}
    template <typename N>
    friend std::ostream& operator<<(std::ostream&, const Tree<N>&);
    std::shared_ptr<Node> root;
    Less less;
    Eq eq;
};

template <typename N>
std::ostream& operator<<(std::ostream& os, const Tree<N>& tree) {
    if (tree.root) return tree.root->print_tree(os, 0);
    return os;
}

Now for the implementations!

namespace detail {
template <typename T, typename Less, typename Eq>
void Node<T, Less, Eq>::insert(std::shared_ptr<Node> node, Less less) {
    if (less(node->data, data)) {
        if (left) {
            left->insert(std::move(node), less);
        } else {
            left = std::move(node);
        }
    } else {
        if (right) {
            right->insert(std::move(node), less);
        } else {
            right = std::move(node);
        }
    }
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>> Node<T, Less, Eq>::reroot() {
    if (!left) {
        return std::move(right);
    } else if (!right) {
        return std::move(left);
    }
    // The max in the left subtree has no right subtree; otherwise it
    // wouldn't be the max!
    auto left_max = left->max();

Two things here: I use max() instead of copy-pasting the logic from max(), and I add a quick explanation of why that works, since it's not totally obvious.

    assert(!left_max->right);
    left_max->right = std::move(right);
    return std::move(left);
}

template <typename T, typename Less, typename Eq>
std::pair<std::shared_ptr<Node<T, Less, Eq>>, bool>
Node<T, Less, Eq>::erase(const T& t, Less less, Eq eq) {
    if (eq(t, data)) {
        return std::make_pair(reroot(), true);
    } else if (less(t, data)) {
        auto result = left->erase(t, less, eq);
        left = std::move(result.first);
        return std::make_pair(shared_from_this(), result.second);
    } else {
        auto result = right->erase(t, less, eq);
        right = std::move(result.first);
        return std::make_pair(shared_from_this(), result.second);
    }
}

template <typename T, typename Less, typename Eq>
std::pair<std::shared_ptr<Node<T, Less, Eq>>, int>
Node<T, Less, Eq>::erase_all(const T& t, Less less, Eq eq) {
    int num_removed = 0;
    if (left && !less(data, t)) {
        auto result = left->erase_all(t, less, eq);
        left = std::move(result.first);
        num_removed += result.second;
    }
    if (right && !less(t, data)) {
        auto result = right->erase_all(t, less, eq);
        right = std::move(result.first);
        num_removed += result.second;
    }
    if (eq(t, data)) {
        return std::make_pair(reroot(), num_removed + 1);
    } else {
        return std::make_pair(shared_from_this(), num_removed);
    }
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<const Node<T, Less, Eq>>
Node<T, Less, Eq>::find(const T& t, Less less, Eq eq) const {
    if (eq(t, data)) return shared_from_this();
    if (less(t, data)) {
        return left ? left->find(t, less, eq) : nullptr;
    } else {
        return right ? right->find(t, less, eq) : nullptr;
    }
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>>
Node<T, Less, Eq>::find(const T& t, Less less, Eq eq) {
    if (eq(t, data)) return shared_from_this();
    if (less(t, data)) {
        return left ? left->find(t, less, eq) : nullptr;
    } else {
        return right ? right->find(t, less, eq) : nullptr;
    }
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<const Node<T, Less, Eq>> Node<T, Less, Eq>::max() const {
    auto p = shared_from_this();
    while (p->right) p = p->right();
    return p;
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>> Node<T, Less, Eq>::max() {
    auto p = shared_from_this();
    while (p->right) p = p->right();
    return p;
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<const Node<T, Less, Eq>> Node<T, Less, Eq>::min() const {
    auto p = shared_from_this();
    while (p->left) p = p->left();
    return p;
}

template <typename T, typename Less, typename Eq>
std::shared_ptr<Node<T, Less, Eq>> Node<T, Less, Eq>::min() {
    auto p = shared_from_this();
    while (p->left) p = p->left();
    return p;
}

template <typename T, typename Less, typename Eq>
std::ostream& Node<T, Less, Eq>::print_tree(std::ostream& os, int level)
    if (left) left->print_tree(os, level + 1);
    for (int i = 0; i < level; ++i) os << " ";
    if (right) right->print_tree(os, level + 1);
    return os;
}
}  // namespace detail
}  // namespace dimanist_binary_tree

OK, this review has gotten pretty long, and we haven't gotten to ForMain.cpp; I'll let other reviewers address that.

\$\endgroup\$
  • \$\begingroup\$ I use Visual C++ 6.0, therefore I wrote #include <iostream.h> \$\endgroup\$ – dimanist Oct 19 '14 at 9:59
  • \$\begingroup\$ Thank you very much! I will try to read it and use in my future programs \$\endgroup\$ – dimanist Oct 19 '14 at 10:01
7
\$\begingroup\$

I'll try and review this file-by-file, but things might crop up across multiple files. However, first, I'd like to mention that my initial thought on looking at this was that I'd have a Node struct, and then have the class manage that struct, and keep track of the head, but that is just my way of thinking about data structures like this, and your way is perfectly valid.

I don't really talk about the algorithms, because I'm really not knowledgeable enough to suggest much better ones, so someone else will have to comment on those.

ClassTree.h

Not much to say here, as far as I can tell. I'd have maybe ordered your function prototypes better, either by category or alphabetically, but it's essentially okay. As well as this, the naming is a little odd. BTree.h or something would make more sense to me.

I'd maybe think about the visibility of some of the functions, for example, zero_count feels like it should be private, as that could mess up your tree if it was called when it shouldn't have been.

ForClass.cpp

As a first thing, you'd usually match the name of the .h file that you're "filling out", so this should be named "ClassTree.cpp", although I'd prefer a more descriptive name.

Your constructor could be doing more, like initializing the Node*s to nullptr, and you should have a destructor, as you're using the new keyword, even if it just calls delete_tree(&root).

I think that it's a little ambiguous what First() does, based on the name, and I'd maybe remove the input handling inside that function, and pass in the data as an argument. That way, how you use it can change, so it's easier to use programmatically.

Instead of search() returning void, consider returning a String, or an int (or even a , if you're feeling up to templating this class), as that way, you're decoupling yourself from cout, and you can do stuff other than just print out if you've found the data.

Bug/unintended functionality: Also, as was pointed to me, in search(), even if you find the correct node, you'll still print out that it's not found, as your cout << "not found" is outside your while loop.

Again, with print_tree(), I'd have it return a string as opposed to directly cout-ing for the same reasons as above, and instead of your printing "The tree is empty...", just have it return an empty string. The same story with max_internal()

As far as the algorithms here go, a smarter person than I will have to comment on those.

ForMain.cpp

Inside generation(), you have the user enter an amount and then in the for loop, iterate amount - 1 times. Either make the < a <=, or as slightly better practice, remove the - 1

Inside menu(), I'd maybe rename solution decision or choice or something like that, because I find that solution tends to mean the result of a calculation as opposed to a choice.

The switch statement is a little large, but as of right now, I can't think of a way to re-design it, although the braces ({ }) don't tend to be put in each case, and instead, just indent well and remember your break;s

Main.cpp

I think that either this or ForMain.cpp should be deleted and rolled into one file. Other than that, it's fine.

\$\endgroup\$
  • \$\begingroup\$ Yann4, thank you very much! I forgot "return" in function "search" after "found = true". Yes, I understand about the naming. I will change all names, Node.h instead ClassTree.h, for example. Why I must do "zero_count" as "private"? Yes, I understand about the input in "first", it is my fault( There was an argument for this function previously. I agree with your opinion about "search" and "max_internal" too. I thought many times about "generation": why I receive less numbers than "amount". Thanks! But I disagree that Main.cpp and ForMain.cpp must be combined into one file. It's useful for me. \$\endgroup\$ – dimanist Oct 17 '14 at 18:08
  • \$\begingroup\$ @dimanist Glad you found it helpful (click the little green tick to accept if it was really helpful). I thought that zero_count was likely to be something that could mess up the program if you did it at the wrong time, so making it private would help solve that. \$\endgroup\$ – Yann Oct 17 '14 at 18:16
5
\$\begingroup\$

Let's start with some easy things:

You mention in a comment that it breaks on the menu when you enter a non number.

bool menu(Node *root){
    int solution = 0;
    int temp = 0;
    cin >> solution;

The problem is here. You don't make sure that the user entered a valid value. It should be written:

    if (cin >> solution)
    {
         // A number was enetered.
         if (solution >= 1 && solution <= 9)
         {
              // Do your code.
              return;
         } 
         else
         {
             // Input not in the correct range.
             // Generate an error
         }
    }
    else
    {
         // User input some random shit.
         // The stream has been set into a bad state so you need to reset it
         std::cin.clear();

         // Throw away all user data that is not sanitized and try again.
         // This usually means throw away the data to the end of the line.
         std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

         // Now show an error msg telling them they are stupid.
    }

Style

Pointers are part of the type information. Put the '*' with the type.

Node*   root = nullptr;

OK. Someone is going to make a comment below. So I am going to pre-empt them.

But that fails when you do.

Node*    first, second, third;

Only first is a pointer. There two are objects.

This is irrelevant.
There is no style guide in the universe that does not say "Put only one variable declaration per line". They also mention that you should initialize it at the same time (which would have caught the error if you had tried it).

So only ever put one variable per line. Initialize it and put all type information with the type on the left. Type information becomes very important in C++ (much more so than in C (where they do it the other way)).

Pointers and Memory management

The rule with memory management.
For every call to new there must be exactly one call to delete.

// Initially your code should look like this:
int func()
{
    Node*  root = new Node;
    // STUFF
    delete root;
}

But this is actually not enough. Because what if STUFF throws an exception. If you don't know what exceptions are don't worry. Its not important yet. The important concept here is that you should be using RAII (look it up its the most important concept in C++).

Basically you don't want base (RAW) pointers. You want an object with a constructor and a destructor to handle the allocation an destruction automatically. Simple example:

struct PointerHolder  // Don't use this class.
{                     // Just a simple example of RAII it is broken
    Node*  data       // for nearly all non trivial uses.

    PointerHolder()
    {
         data = new Node();    // When this object is created
    }                          // We call new.
    ~PointerHolder()
    {
         delete data;          // When this object is destroyed we destroy
    }                          // the data correctly.
};

// Now we re-write to use the pointer holder.
int func()
{
    PointerHolder  root;
    // STUFF
}

Now this is safe. Even if STUFF throws an exception the destructor for root is called and the memory is correctly freed. This concept is so important that the standard library has a whole bunch of classes that do exactly what I did above (with a few other nice features that make memory management a non-existent task).

But you ask how:

How does that relate to me.

Well your tree "Binary Tree" is not really a tree (yet) its just a node class. Where you can string a bunch of nodes together. You have not done memory management correctly. What you should do is have a "BinaryTree" class that holds the root object and manages it for the lifetime of the object. Then the Tree holds and manages the nodes.

class BinaryTree
{
    struct Node
    {
        int    id;
        Node*  left;
        Node*  right;

        Node(int id)
            : id(id)
            , left(nullptr)
            , right(nullptr)
        {}
        ~Node()
        {
            delete left;
            delete right;
        }
    };

    // So internally the Binary Tree will use object of Node.
    // It will also have a single root.
    Node*    root;

    // To make things easier we will also keep a count of all the nodes
    // inside the tree.
    int                      nodeCount;

  public:
    BinaryTree()
        : root(nullptr)
    {}
    ~BinaryTree()
    {
        delete root;
    }
    // To the more experienced programmers
    // We will be coming back to handle the rule of three soon.
    // One concept at a time please.
};

This is the very basics of the Binary Tree you will need. If we look at this in the context of your original code.

int main(){
    Node *P1 = 0;                 // prefer nullptr over 0.
                                  // It conveys more information.

    P1 = P1->first(P1);           // There is a hidden call to new here.
                                  // But I see no coresponding call to
                                  // delete. The first rule of memory management
                                  // is that each new must have a matching delete

    // Ugly looking loop.
    // But it works so I can not really complain.
    do{
    }while( menu(P1) );
    return 0;
}

What this should have looked like:

int main(){
    // Notice here this is a normal object (not a pointer)
    // So there is no memory management.
    // Internally the constructor sets things up.
    // And the destructor will make sure that delete is called on all
    // allocated objects.
    BinaryTree  P1;

    for(;menu(P1);)
    { /* Deliberately empty, All action performed by Menu */ }
}

Interface

Your current interface you pass around the root everywhere:

Node * first(Node *root);
void search(Node *root, int digit);
Node * insert(Node *root, int digit);
void print_tree(Node *root, int level);
void max_internal(Node *root);
Node * delete_key(Node *root, int digit);
void delete_tree(Node * root);

Note with the redisgn all these functions should really be on the BinaryTree class (not the Node class). But also the BinaryTree contains the member root. So you don't need to pass it around anymore.

class BinaryTree
{
    // As before (see above)

    bool search(int digit);       // If you want a programtic search 
                                  // You should be able to get the result of
                                  // the search back so you can make a decision
                                  // So changed the result type to bool.

    void insert(int digit);       // The user can not do anything with a Node
                                  // So don't return a pointer to it.
                                  // You don't want them messing with the
                                  // internal structure anyway.

    void delete_key(int digit);
    void print_tree()             {print_tree(root, 0);}
    void max_internal();

    private:
    void print_tree(Node* node, int level);   // Notice that I made this private.
                                  // The user calls this via the public
                                  // method. Which just calls with root
                                  // as the first level. This reduces user
                                  // mistakes. 

}

The following methods you no longer need.

    Node * first(Node *root);
    void delete_tree(Node * root);

They are replaced with the BinaryTree constructor and Destructor. The constructor and destructor are called automatically so we have replaced a manual call by one that is done automatically by the compiler thus reducing the chance of mistakes.

Your implementation of looping traversals is fine. But your implementation of recurive traversal forgets to check for NULL nodes. Instead you check the node count (which may be wrong) and exit out if that is zero.

When you write a recursive function allways check for NULL as the first test and return without doing anything if the current node is NULL.

void Node::print_tree(Node *node, int level)
{
    if (node == nullptr)
    {   return;
    }

    print_tree(node->left, level + 1);
    for (int i = 0; i < level; i++){
        cout << " ";
    }
    cout << node->id << endl; 
    print_tree(node->right, level +1); 
}

void Node::max_internal(){
    if (root == NULL)
    {   cout << "No Nodes\n";
        return;
    }
    int max;
    for(Node *pv = root;pv;pv = pv->right)
        max = pv->id;
    }
    cout << "Max internal: " << max << endl;
}
\$\endgroup\$
  • \$\begingroup\$ Yes, thanks. Surely your answer is very useful but not for begginers as I. There is so unclear in the code and sentences, I don't know c++ so good (templates, exceptions etc.) \$\endgroup\$ – dimanist Oct 18 '14 at 19:44
  • \$\begingroup\$ @dimanist: Here was me trying to be more pleasant and jocular than normal. Rather than my normal review (you should read a few) I was trying to inject humor and more explanation because you are obviously a beginner to explain why you are going wrong. But ruds beat me to it. \$\endgroup\$ – Martin York Oct 18 '14 at 21:44
  • \$\begingroup\$ Yes, I agree that function search must return bool. Exactly \$\endgroup\$ – dimanist Oct 19 '14 at 10:14
  • \$\begingroup\$ I understand your ideas about interface. Thanks! It's helpful for me \$\endgroup\$ – dimanist Oct 19 '14 at 10:23
4
\$\begingroup\$

You can only have one tree in your program because your count variable is static across all nodes. This is problematic because you have no way of ensuring that all the nodes will be in a tree. You can create nodes outside the class. If you really want to enforce the one tree policy, you should make the constructor private.

You also have a zero_count function that can take you out of synch with the actual number of nodes in the tree. That probably isn't needed but should be private if it exists.

Unless your tree can only have ten nodes, digit is a bad name for the variable that matches id in search and insert. Something like key or datum would be a more common choice.

In search, the found variable is not needed:

while (pv){
    if (digit == pv->id){
        cout << "Digit " << digit << " was found!";
        return;
    }
\$\endgroup\$
  • \$\begingroup\$ Thanks! But I have a problem. If I enter a symbol (not number) in my menu I will see "The tree was deleted! Exit". But it is "case: 0" for my switch, there is "default" for other situations. It is a wrong behavior. \$\endgroup\$ – dimanist Oct 18 '14 at 10:42
  • \$\begingroup\$ @dimanist The thing is that you aren't doing any checking of the value. When the user enters something other than a number, solution defaults to 0. It will only show your default case when you put in a number with more than one digit. [Loki Astari's answer] covered this in more detail. You can see another example requiring that the user input a number here. Look for the code that says while (!(cin >> playAgain)). That forces a number to be entered. \$\endgroup\$ – Brythan Oct 19 '14 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.