c++ - 在 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

您是否有任何特殊原因不只是为 child 使用链表？例如，这里是一个非常基本的伪代码示例:

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