在C++中使用儿童列表的树实现

Question

嘿，这是我到目前为止。我应该将树ADT实现作为子列表。我不确定我所做的是否正确。任何帮助将不胜感激。提前致谢。

#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

是否有任何特殊的原因，你不只是使用链表为孩子？例如，下面是一个伪代码很基本的例子：

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; 
    } 
}