Special Tree Problem

[sadij97]

I am creating a combination of trinary and binary trees. At level=0, you have the root of course. Then at level=1, you have 3 nodes. At level=2, you have 2 nodes. At level=3, you have 3 nodes... and so on. I created a class that makes 3 nodes all the time but how do i make it 3 2 3 2 3 2, mostly how to implement insertion?

o
/ | \
o o o
/\ /\ /\
oo oo oo

template <typename T>
class special_tree
{
public:
    special_tree(){ root_ptr=nullptr; used=0;}
    void insert(const T& entry);
    void erase_one(const T& entry);
    void print();
    
private:
    ternary_tree_node<T>*root_ptr;
};

[48bpfSEw]

Why restrict only on the patter 3,2,3,2,...?

You could store all the children of the node in a vector.


*** SKETCH ***

class Node;  // forward declaration


class Node {
public:
  vector<Node>  Children;
};


main () {

  Node base;
  Node child1 = base.Children.push_back (new Node());
  Node child2 = base.Children.push_back (new Node());
  Node child3 = base.Children.push_back (new Node());

  Node child1_1 = child1->Children.push_back (new Node());
  Node child1_2 = child1->Children.push_back (new Node());

  Node child2_1 = child1->Children.push_back (new Node());
  Node child2_2 = child1->Children.push_back (new Node());

  Node child3_1 = child1->Children.push_back (new Node());
  Node child3_2 = child1->Children.push_back (new Node());
}

Write your code first as free as possible. Restrictians are easy to implement. But if your architecture is restricted at the beginning set free is hard!



Now the restrictions

class Node;  // forward declaration


class Node {
private:
  vector<Node>  Children;

public:
   Node (int paMaxCountChildren) { iMaxCountChildren = paMaxCountChildren; }

private:
  int iMaxCountChildren;

public:
  Node* add (void) {
    if (Children.size () >= iMaxCountChildren)
      throw "Max children overflow error!";
    
      return Children.push_back (new Node());
    }  
};


main () {

    Node base(2);
  Node child1 = base.Children.push_back (new Node());
  Node child2 = base.Children.push_back (new Node());
  Node child3 = base.Children.push_back (new Node());   // ----> exception
}

[sadij97]

@Necip Thank your for your response... The assignment wants 3 2 pattern. :( ... I've never used vector to create a tree but if you use vector of children, how is it possible to individually put data to the node and then create new pointers that would point to the following left and right children etc. For ex: In Binary Search Tree using vector, I feel it would be difficult to do strict weak ordering, wouldn't it?

[48bpfSEw]

e.g.

child1->Children.push_back (new Node());   // first node in vector is per definition the right branch

child1->Children.push_back (new Node());   // second node in vector is per definition the left branch

// and so on...

We are using often this idiom in ower office : "Mach' das es geht!" ("make it run!") ^^

[coder777]

@Necip
push_back() of the vector does not return anything. Plus your vector does not take a pointer.

sadij97 wrote:

The assignment wants 3 2 pattern.

You may use an array with the capacity of three node. But you need another variable for the actual used and the maxiimum. The maximum for even level is two and for odd level three.

I feel it would be difficult to do strict weak ordering, wouldn't it?

No more difficult then an array. The vector contains already the actual used count.

[48bpfSEw]

@coder, this is not a bug, this is a sketch! ^^

[coder777]

@Necip
It is not really helpful to post false code especially in the beginner section.

[48bpfSEw]

#include <stdio.h>
#include <vector>

class Node;  // forward declaration

class Node {
private:
  std::vector<Node*>  nodes;

public:
   Node () { }
   ~Node () {
    for (std::vector<Node*>::iterator
         it  = nodes.begin();
         it != nodes.end(); ++it)
      delete *it;               // free allocation
    }

public:
  Node* add (void) {
    Node *node = new Node();    // allocate
    nodes.push_back (node);
    return node;
    }
};


int main (void) {

  // base
  Node* base  = new Node();

  // base has 2 children
  Node* node1 = base->add();
  Node* node2 = base->add();

  // node 1 has 3 children
  Node* node1_1 = node1->add();
  Node* node1_2 = node1->add();
  Node* node1_3 = node1->add();

  // node 2 has 5 children
  Node* node2_1 = node2->add();
  Node* node2_2 = node2->add();
  Node* node2_3 = node2->add();
  Node* node2_4 = node2->add();
  Node* node2_5 = node2->add();

  return 0;
}

successfull compiled.

[coder777]

@Necip
Yes, that looks good. The 'forward declaration' is not needed.

In this particular example base don't need to be dynamically created. If you do so you should add a delete. Each new should have a delete in order to avoid memory leaks.