What is wrong with following C++ program?

Question

Why does following C++ code gives below mentioned error? Also why is not this the idiomatic way of writing recursive data-structures in C++? Is there something fundamentally wrong with this way of writing C++?

#include<iostream>
using namespace std;


class tree{
public:
    virtual void inorder() {};
};

class emp_tree: public tree{
public:
    void inorder(){
    }
};

class non_emp_tree: public tree{
public:
    tree left, right;
    int val;
    non_emp_tree(int v, tree l, tree r): val(v), left(l), right(r) {};
    void inorder(){
        left.inorder();
        cout<<" "<<val<<" ";
        right.inorder();
    }
};




int main() {
    tree leaf1 = non_emp_tree(1, emp_tree(), emp_tree());
    tree leaf2 = non_emp_tree(3, emp_tree(), emp_tree());
    tree root = non_emp_tree(2, leaf1, leaf2);
    root.inorder();
    return 0;
}

Error given by compiler: (I'm unable to comprehend most of it)

/tmp/ccAjhirw.o: In function `main':
b_t.cpp:(.text+0x16e): undefined reference to `tree::inorder()'
/tmp/ccAjhirw.o: In function `tree::tree()':
b_t.cpp:(.text._ZN4treeC2Ev[_ZN4treeC5Ev]+0x9): undefined reference to `vtable for tree'
/tmp/ccAjhirw.o: In function `tree::tree(tree const&)':
b_t.cpp:(.text._ZN4treeC2ERKS_[_ZN4treeC5ERKS_]+0xd): undefined reference to `vtable for tree'
/tmp/ccAjhirw.o: In function `non_emp_tree::inorder()':
b_t.cpp:(.text._ZN12non_emp_tree7inorderEv[_ZN12non_emp_tree7inorderEv]+0x19): undefined reference to `tree::inorder()'
b_t.cpp:(.text._ZN12non_emp_tree7inorderEv[_ZN12non_emp_tree7inorderEv]+0x56): undefined reference to `tree::inorder()'
/tmp/ccAjhirw.o: In function `tree::tree(tree&&)':
b_t.cpp:(.text._ZN4treeC2EOS_[_ZN4treeC5EOS_]+0xd): undefined reference to `vtable for tree'
/tmp/ccAjhirw.o:(.rodata._ZTI12non_emp_tree[_ZTI12non_emp_tree]+0x10): undefined reference to `typeinfo for tree'
/tmp/ccAjhirw.o:(.rodata._ZTI8emp_tree[_ZTI8emp_tree]+0x10): undefined reference to `typeinfo for tree'
collect2: error: ld returned 1 exit status

Edit: I changed virtual void inroder() to virtual void inorder() {} i.e empty implementation. But still I am not getting desired output, it seems root, leaf1 and leaf2 are both calling tree's inorder not their respective inorders.

Answer 1

You never implemented tree::inorder.

class tree{
public:
    virtual void inorder();
};

Here you claimed there was such a function -- where is its implementation?

Also, this doesn't make sense:

tree leaf1 = non_emp_tree(1, emp_tree(), emp_tree());

You're setting a tree's value equal to a non_emp_tree's value. That certainly won't do anything useful.

Answer 2

virtual void inorder(){} should be in your tree class you are missing {}

Answer 3

What you presumably tried to do was to use polymorphism. However, for that you must use a reference or pointer to base not a base itself. I.e.

#include<iostream>
#include<memory>

struct tree
{
  virtual void inorder() = 0;  // abstract: cannot be called
  virtual ~tree() {}
};

struct emp_tree : tree
{
  void inorder() override
  {}
};

struct non_emp_tree : tree
{
  std::unique_ptr<tree> left,right; 
  int val;
  non_emp_tree(int v, tree*l, tree*r)
  : left(l), right(r), val(v) {}
  void inorder() override
  {
    left->inorder();
    std::cout<<" "<<val<<" ";
    right->inorder();
  }
};

int main() {
  auto leaf1 = new non_emp_tree(1, new emp_tree, new emp_tree);
  auto leaf2 = new non_emp_tree(3, new emp_tree, new emp_tree);
  auto root  = new non_emp_tree(2, leaf1, leaf2);
  root->inorder();
}

compiled with clang, produces 1 2 3.

Answer 4

First things first, if tree::inorder is meant to be an abstract method, you need to properly declare it as such:

class tree{
public:
    virtual void inorder() = 0;
};

However, this is very quickly going to lead to a bunch of other problems, because you're slicing up your objects left and right!

tree leaf1 = non_emp_tree(1, emp_tree(), emp_tree());

This code cannot possibly have the effect you intend. non_emp_tree contains member variables that a tree object doesn't have room to store. And even if it did, you'd have no guarantee that the object would behave the way you expect. Invocations of inorder on leaf1 would attempt to call tree::inorder, not non_emp_tree::inorder, because the program has no way of knowing that you intended to store a subclass here.

The way to fix this is to use pointers for all your tree objects.

#include<iostream>
#include<memory>

class tree{
public:
    virtual void inorder() = 0;
    virtual ~tree() = default;
};

class emp_tree: public tree{
public:
    void inorder(){
    }
};

class non_emp_tree: public tree{
public:
    std::unique_ptr<tree> left, right;
    int val;
    non_emp_tree(int v, tree *l, tree *r): val(v), left(l), right(r) {};
    void inorder(){
        if(left) left->inorder();
        std::cout<<" "<<val<<" ";
        if(right) right->inorder();
    }
};

int main() {
    std::unique_ptr<tree> leaf1 = std::make_unique<non_emp_tree>(1, new emp_tree, new emp_tree);
    std::unique_ptr<tree> leaf2 = std::make_unique<non_emp_tree>(3, new emp_tree, new emp_tree);
    std::unique_ptr<tree> root = std::make_unique<non_emp_tree>(2, leaf1.release(), leaf2.release());
    root->inorder();
    return 0;
}

A better implementation of this code would avoid any uses of naked new at all, but that would require some significant refactoring of your code.

Answer 5

The "inorder" method of class "tree" is not implemented, so you get an undefined reference to this method when calling it.