首页 文章

在c中递归填充N-ary树

提问于
浏览 次
0

我正在尝试创建tic-tac-toe棋盘游戏的游戏树 . 我已经编写了一些基本方法，但是我在递归填充树的元素方面遇到了麻烦 .

我正在使用 Node 结构来定义树的节点 . 每个节点都有一个子节点 .

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

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

所以， * * * * * * * * * 将是一块空白板 .

我有一个实现树的Tree类 .

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

任何提示或具体建议将不胜感激 . 谢谢 .

c++ recursion tree populate tic-tac-toe

1 回答

  • 0

    我建议给构造函数 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;
    }
  }
}

    我没有时间分析其余部分，但这可能会让您更容易解决 .

    回复于

相关问题