Implémentation arborescente utilisant des listes d'enfants en C++

Question

Hey voici ce que j'ai jusqu'ici. Je suis supposé faire une implémentation d'ADT en arbre comme des listes d'enfants. Je ne suis pas sûr que ce que je fais soit correct ou non. Toute aide serait grandement appréciée. Merci d'avance.

#include <string> 
#include <iostream> 

using namespace std; 

const int maxcells = 1000; 
const int maxnodes = 1000; 

template<class T> class LoCTree{ 

public: 

    LoCTree(); 
    ~LoCTree(); 
    int firstNodeSpot(); 
    int firstCellSpot(); 
    int lastN(int head); 
    int nodePos(int head, int n); 
    int getNodePosition(int node); 
    int getCellPosition(int header); 
    T label(int node); 
    int create0(T label); 
    int create1(T label, int tree1); 
    int create2(T label, int tree1, int tree2); 
    int create3(T label, int tree1, int tree2, int tree3); 
    int leftmostChild(int node); 
    int rightSibling(int node); 
    int parent(int node); 
    int root(int node); 
    void makenull(); 
    void print(int head); 
    void preorder(int node); 

    private: 
    struct node{ 

     T label; 
     int header; 
     int position; 

     node(){ 
      label = T(); 
      header = -1; 
      position = -1; 
     } 

    }; 
    node nodespace[maxnodes]; 

    struct cell{ 
     int node; 
     int next; 
    }; 
    cell cellspace[maxcells]; 
}; 

template<class T> LoCTree<T>::LoCTree(){ 
    for(int a=0;a<maxcells;a++){ 
     cellspace[a].node = -1; 
     cellspace[a].next = -1; 
    } 
    for(int b=0; b< maxnodes;b++){ 
     nodespace[b].label = T(); 
     nodespace[b].header = -1; 
    } 
} 
template<class T> LoCTree<T>::~LoCTree(){ 

} 
template<class T> int LoCTree<T>::firstNodeSpot(){ 
    for(int a=0; a<maxnodes; a++){ 
     if(nodespace[a].header==-1){ 
      return a; 
     } 
    } 
     return -1; 
} 
template<class T> int LoCTree<T>::firstCellSpot(){ 
    for(int a=0; a<maxcells; a++){ 
     if(cellspace[a].node==-1){ 
      return a; 
     } 
    } 
     return -1; 
} 

template<class T> int LoCTree<T>::create0(T label){ 
    int nodespot = firstNodeSpot(); 
    if(nodespot != -1){ 
     nodespace[nodespot].label = label; 
     nodespace[nodespot].position = 0; 
     return nodespot; 
    } 
    return -1; 
} 
template<class T> int LoCTree<T>::create1(T label, int tree1){ 
    int nodespot = create0(label); 
    if(nodespot != -1){ 
     int cellspot = firstCellSpot(); 
     nodespace[nodespot].header = cellspot; 
     cellspace[cellspot].node = nodespot; 
     nodespace[tree1].position = nodespot; 
     cellspace[cellspot].node = tree1; 
     return nodespot; 
    } 
    return -1; 
} 
template<class T> int LoCTree<T>::create2(T label, int tree1, int tree2){ 
    int anode = create1(label,tree1); 
    if(anode != -1){ 
     cellspace[nodespace[anode].header].next = firstNodeSpot(); 
     nodespace[tree2].position = anode; 
     cellspace[firstNodeSpot()].node = tree2; 
     return anode; 
    } 
    return -1; 
} 

template<class T> void LoCTree<T>::print(int head){ 
    //cout << head; 

    int nodespot = head; 
    int cellspot = -1; 
    int tmp = -1; 
    while(nodespace[nodespot].header!=-1){ 
     cout << nodespace[nodespot].label; 
     cellspot = nodespace[nodespot].header; 
     tmp = cellspace[cellspot].next; 
     if(tmp == -1){ 
      int tmp1 = nodespace[nodespot].header; 
      nodespot = cellspace[cellspot].node; 
      if(nodespot == tmp1){ 
       break; 
      } 
     } 
     else{ 
      nodespot = cellspace[cellspot].next; 
     } 
    } 
    cout << nodespace[nodespot].label; 

    //cout << nodespace[3].label; 
    //cout << nodespace[getNodePosition(cellspace[getCellPosition(0)].node)].label << endl; 
    //cout << nodespace[getNodePosition(cellspace[getCellPosition(0)].node)].label << endl; 
     /* 
     while(node!=-1){ 
      cout << nodespace[node].label; 
      node = cellspace[nodespace[node].header].next; 
     } 
    }*/ 
} 

Answer 1

Y a-t-il une raison particulière pour laquelle vous n'utilisez pas seulement des listes liées pour les enfants? Par exemple, voici un exemple vraiment basique en pseudocode:

template<class T> 
class Treenode 
{ 
public: 
    Treenode* children; 
    T data; 

    Treenode(T _data) { 
     children = 0; 
     data = _data; 
    } 

    addChild(Treenode* t) { 
     t->next = children; 
     children = t; 
    } 

    addNewChild(T _data) 
    { 
     addChild(new Treenode(_data)); 
    } 

    Treenode* getNthChild(int n) { 
     int i = 0; 
     for (Treenode* t = children, int i = 0 ; t != 0 ; t = t->next, i++) { 
     if (i == n) return t; 
     } 
     return 0; 
    } 
}