在C++中递归地填充N-tree树

Question

我正在尝试创建井字游戏的游戏树。我已经写了一些基本的方法，但是我无法递归地填充树的元素。我使用Node结构来定义树的节点。每个节点都有一组子节点。

struct node { 
    string data; 
    int height; 
    node * child[9]; 
}; 

每个节点都将游戏板的内容存储为字符串。 *用于显示空白。

因此，* * * * * * * * *将是一个空白板。

我有一个实现树的树类。

class Tree { 
public: 
    Tree(); 
    Tree(string data); 
    ~Tree(); 

    void insert(string data, node * leaf); 
    node * get_root(); 
    void populate(node * n); 
    void generate_tree(node * n); 
    int number_of_blanks(string); 

private: 
    void destroy_tree(node * leaf); 

    node * root; 
    node * temp; 
    int count; 
}; 

Tree::Tree(string data) { 
    root = new node; 
    root->data = data; 
    root->height = 0; 
    temp = root; 
    count = 0; 
} 

这是我的插入节点的方法。它向第一个NULL子项插入一个新节点。

void Tree::insert(string data, node * leaf) { 
    int i; 
    //checks for first NULL child 
    for(i = 0; i < 9; i++) { 
    if(leaf->child[i] == NULL) { 
     //first NULL child is inserted and all its children set to NULL 
     leaf->child[i] = new node; 
     leaf->child[i]->data = data; 
     leaf->child[i]->height = leaf->height + 1; 
     break; 
    } 
    } 
} 

此代码的工作，我如何打算，但我敢肯定，这不是最好的方法。

我最麻烦的地方是递归填充树。我的递归要么提前结束，要么是无止境的循环。我不知道如何解决这个问题，因为我从来没有使用void方法递归。

void Tree::generate_tree(node * leaf) { 
    int i; 
    string data; 
    string player; 
    int length = number_of_blanks(leaf->data); 

    if(leaf->height % 2 == 0) 
    player = "X"; 
    else 
    player = "O"; 


    if(leaf->data.find_last_of('*',8) == string::npos) { 
    cout << "This is a leaf!!!!!!!!! " << leaf->data << endl; 
    return; 
    } 


    for(i = 0; i < length; i++) { 
    if(leaf->height >=9) 
     return; 
    data = leaf->data.replace(count,1,player); 
    insert(data,leaf); 
    cout << "New Node: " << data << " Height: " << leaf->child[i]->height << endl; 
    count++; 
    generate_tree(leaf->child[i]); 
    count = 0; 
    } 
} 

任何提示，或具体的建议将不胜感激。谢谢。

Answer 1

我建议给node一个构造函数，并在组成构造函数的代码块之前初始化成员。例如：

node(string s, int h) : data(s), height(h) { 
    for (int i=0;i < 9; ++i) 
     child[i] = NULL; 
} 

同样的构造函数Tree：

Tree::Tree(std::string data) : root(new node(data,0)), count(0) {} 

这使得代码的其他部分要简单得多。例如，您insert代码现在看起来是这样的：

void Tree::insert(std::string data, node * leaf) { 
    //checks for first NULL child 
    for(int i = 0; i < 9; i++) { 
    if(leaf->child[i] == NULL) { 
     //first NULL child is inserted and all its children set to NULL 
     leaf->child[i] = new node(data, leaf->height+1); 
     break; 
    } 
    } 
} 

我还没有来分析，其余的时间，但是这可能使你更容易解决。