0

I try to write a simple binary tree in C++ template. In second line of main(), I want to declare

Node<string,Node,int> 

the second Node is wrong, because it's a class template, must be instantiated as

Node<string,Node<string,int,int>,int>

But as tree grows, type grows. How can I use the first declaration? Thanks!

My C++ compiler is g++ 4.8.1, support C++11.

#include <iostream>
#include <string>

using namespace std;

template<typename T, typename Tl, typename Tr>
struct Node {
  // tree node
  T top;
  Tl left;
  Tr right;
  Node (const T& t=T(),const Tl& tl=Tl(),const Tr& tr=Tr()):
    top(t), left(tl), right(tr){}

};

int main() {
  Node <string,int,int> n1 (string("+"), 1, 2);
  // !!!wrong , should be Node<string,Node<string,int,int>,int>
  Node<string,Node,int> n2 (string("*"), n1, 4);
}

UPDATE:

I add pointers to struct. How to make it better? Thanks!

#include <iostream>
#include <string>

using namespace std;

template<typename T=string, typename Tl=int, typename Tr=int>
struct Node {
  // tree node
  struct Node<T,Tl,Tr>* p_left;
  struct Node<T,Tl,Tr>* p_right;
  T top;
  Tl left;
  Tr right;
  Node (struct Node<T,Tl,Tr>* pl=nullptr, struct Node<T,Tl,Tr>* pr=nullptr,
        const T& t=T(),const Tl& tl=Tl(),const Tr& tr=Tr()):
    p_left(pl), p_right(pr), top(t), left(tl), right(tr){}
};

using tnode = struct Node<>;

int main() {
  tnode n1 (nullptr,nullptr,string("+"), 1, 2);
  tnode n2 (&n1, nullptr,string("*"), 0,0);
}

UPDATE 2, add smart pointer.

#include <iostream>
#include <string>
#include <memory>

using namespace std;

template<typename T=string, typename Tc=int>
class Node {
public:
  Node (shared_ptr<Node> pl=nullptr, 
        shared_ptr<Node> pr=nullptr,
        const T& t=T(),
        const Tc& tl=Tc(),
        const Tc& tr=Tc()):
    p_left(pl), p_right(pr), v_top(t), v_left(tl), v_right(tr){}

  ~Node() {
    cout<<"Calling destructor"<<endl;
  }
private:
  shared_ptr<Node> p_left;
  shared_ptr<Node> p_right;
  T v_top;
  Tc v_left,v_right;
};

using tNode = Node<>;
using spNode = shared_ptr<tNode>;

spNode create_tree() {
  spNode n0 = make_shared<tNode>(nullptr,nullptr,string("*"), 7, 3);
  spNode n1 = make_shared<tNode>(nullptr,n0,string("+"), 5, 6);
  spNode n2 = make_shared<tNode>(n1, nullptr,string("+"), 3,4);
  return n2;    
}

int main() {
  spNode n2 = create_tree();
}
5
  • 1
    This looks way too strange. Is there something preventing you from having a template<typename T> struct Node and just keeping 2 pointers to Node<T> for the branches?
    – E_net4
    Jun 26, 2013 at 23:39
  • I just try to write it without pointers.
    – davy
    Jun 26, 2013 at 23:52
  • Trees work best with some kind of pointer or location. You could use an array and the link fields would be array indices. The main reason is that during compile time, you don't know how many nodes to use. Thus dynamic memory is used during run-time. Dynamic memory allocation requires pointers. Jun 27, 2013 at 0:03
  • 1
    @Davy - in C# or Java, you don't need to explicitly use pointers because the members have implicit references anyway. This doesn't happen in C++. It's technically possible to have a template binary tree node defined so the parent node directly contains the child nodes without using pointers (and with different item types in different nodes, even) but it's, well, pointless. The structure of the tree as a whole would have to be fixed at compile-time, to match the big static type. You'd be better off flattening the whole tree into a single struct - easier to specify the type, easier to use.
    – user180247
    Jun 27, 2013 at 0:12
  • Do you really need to type the type? A function call result that you assign to auto might do? Jun 27, 2013 at 1:02

1 Answer 1

0

Take a template<typename>class NodeMaker, pass it the parent Node type, for the two child params.

Write template<typename T>using Same=T; and templatestruct fixed{templateusing type=X;}`.

Now,

Node<string, Same, fixed<int>::template type>

makes the type you want.

As a problem this type is infinite in size: you need a way for the Node inside Node to disappear. Use std::unique_ptr<> to hold your left and right children?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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