用深度优先然后从左到右约束填充 N 叉树

Question

我正在尝试实现一个函数，用这两个前两个优先级（按此顺序）填充 n 叉树： 1. 以最大可能深度插入。 2. 从左到右插入，例如图像中深度为 3 和 12 个元素，其中 n 个子元素：

这是我到目前为止的尝试，我已经尝试填充直到最大可能的深度，但让我对如何实现从左到右的约束感到困惑

int Tree::insertcell(int data, int depth, int* done, int maxchild, TreeNode* node) {
    for(int i = 0; i < maxchild; i++){
        cout << "children: " << i << endl;
        if (node->children[i] == nullptr && depth > 0){
            node->children[i] = new TreeNode(data, maxchild); //insert new node with data
            if(i == maxchild - 1){
                (*done) = depth + 1;
            }
            this->size += 1;
            return 1;
        }
        else if(node->children[i] != nullptr && depth > 0){
            if ((*done) > 0){
                this->insertcell(data, depth - 1, done, maxchild, node);
                continue;
            }else{
                this->insertcell(data, depth - 1, done, maxchild, node->children[i]); // access
            }
            this->size += 1;
            return 1;
        }
        else if(node->children[i] == nullptr && depth == 0){
            node->children[i] = new TreeNode(data, maxchild);
            this->size += 1;
            if(i == maxchild - 1){
                (*done) += 1;
            }
            return 1;
        }
        
    }
    return 0

Answer 1

首先对您的方法进行一些评论：

• 该函数不会预见到将第一个节点插入到树中，在这种情况下，您必须更新

  root

  实例字段（或者无论您如何命名它）。

• 不需要将

  maxchild

  作为参数传递给此插入函数。相反，这个值应该在创建树实例时确定，然后它应该是树实例的一个字段。

• 我会删除

  done

  参数。这很容易变得混乱。您可以尽可能向下钻取每个级别的最后一个子节点，然后在从递归中展开时，找到插入新节点的位置。那你就不需要这个

  done

  参数了。

  因此，换句话说，我建议采用“乐观”方法，找到最右边的子节点（不为空），并使用递归调用在该子树中插入新节点。然后检查递归调用的返回值以查看是否有效。如果是这样，除了返回 success (1) 之外，别无他法。如果没有，检查是否还有空间容纳新的子节点，如果有，则将新节点放在那里。如果这也不可能，则意味着以

  node

  为根的子树已满。在这种情况下返回 0，以便调用者可以做一些替代他们乐观选择的事情。

• 类似地，

  insertcell

  的初始调用不需要

  depth

  ，也不需要

  node

  参数，因为树的深度应该在创建树实例时确定一次。第一个使用的节点将是树的根。

• 当您要创建的节点将是 leaf 节点时，您不应将

  maxchild

  传递给

  TreeNode

  构造函数。相反，传递 0，以表明该节点不会有子节点。

• 您似乎正在使用 C++，您应该放弃 C 的习惯，并且更喜欢使用向量而不是 C 数组。因此

  children

  最好是一个向量，这意味着您只需将 push 节点推向它，直到达到最大大小 (

  maxchild

  )。这样你就不必在数组中寻找

  nullptr

  。

我在这里提供了一个可能的实现：

#include <iostream>
#include <string>
#include <vector>

class TreeNode {
private:
    int data;
    std::vector<TreeNode*> children;
    int maxchild;

public:
    TreeNode(int data, int maxchild) : data(data), maxchild(maxchild) {}

    int insert(int data, int depth) {
        // Check if we have child nodes here
        int size = this->children.size();
        // If so, try to insert the new node in the last subtree
        if (size && this->children.back()->insert(data, depth - 1)) {
            return 1; // The new node was inserted in this i-th subtree
        }
        // The selected subtree is full.
        // Check if we can create a new child here:
        if (size == this->maxchild) {
            return 0; // Cannot add child here: backtrack
        }
        // Insert the new node here. Adapt maxchild argument according to depth
        this->children.push_back(new TreeNode(data, depth == 1 ? 0 : this->maxchild));
        return 1;
    }
    // Helper method to get some output
    std::string toString(std::string tab) {
        std::string s = tab + std::to_string(this->data) + "\n";
        for (auto child : this->children) {
            s += child->toString(tab + "  ");
        }
        return s;
    }
};

class Tree {
private:
    int size = 0;
    TreeNode* root = nullptr;
    int maxchild;
    int depth;

public:
    Tree(int maxchild, int depth) : maxchild(maxchild), depth(depth) {}

    int insert(int data) {
        if (!this->root) { // Empty tree? Insert the root...
            this->root = new TreeNode(data, this->depth == 0 ? 0 : this->maxchild);
            return 1;
        }
        int success = this->root->insert(data, this->depth);
        this->size++;
        return success;
    }
    // Helper method to get some output
    std::string toString() {
        return this->root ? this->root->toString("") : "";
    }
};

这是一个演示运行：

int main() {
    Tree* tree = new Tree(3, 3);
    for (int data = 0; data < 16; data++) {
        int success = tree->insert(data);
        if (!success) {
            std::cout << "could not add to tree";
            exit(1);
        }
    }
    std::cout << tree->toString();
}

这将输出所填充的树的外行视图：

0
  1
    2
      3
      4
      5
    6
      7
      8
      9
    10
      11
      12
      13
  14
    15