1

我有一个大学项目，我需要在 dart 中实现一个 N-ary 树。

到目前为止，这是我的节点

class Node {

    Node parent; // parent of the current node
    List<Node> children; // children of the current node
    int id;
    String actualMessage;

    Node (int id, String actualMessage){
        this.id=id;
        this.actualMessage=actualMessage; 
        children  = new List<Node>();
    }
}

我被困在如何实现以下方法上。我将尝试通过以下示例解释我需要什么

A 是根，有 3 个孩子：B、C 和 D。B 有 2 个孩子：E 和 F。E 有 1 个孩子：G。

在此处检查树示例

  1. 如何将根/父节点/子节点添加到树 => 如何添加 A 、 B 和 E
  2. 如何从树中删除一个节点。=> 如何删除 B。它也应该删除它的孩子。
  3. 当父级作为参数传递（在单个级别上）=> 如何获取 A 上的实际消息时，如何检索父级和所有可能的子级的“实际消息”？方法也应该在 B、C 和 D 上返回实际消息
  4. 如何检索最长路径的节点数=>最长路径的节点数是从根到最后一个节点的路径。在我的情况下是4。
  5. 如何在到达根的任何节点上检索树的所有父节点的节点数和列表。=> G 的节点数为 4，G 的所有父节点列表为 E、B 和 A。

任何有关如何执行上述操作的代码或信息将不胜感激。这是我被困在同一件事上的第三天。

谢谢

4

1 回答 1

0

哇，你要求的太多了：P

我已经尝试了前 2 个要求，这是可以帮助您满足它们的代码。

Node root = new Node(0, "A"); // Your root node

我将在树上显示预购遍历的结果。

  1. 添加新节点：
void addNode(Node parent, Node newNode){
  newNode.parent = parent;
  parent.children.add(newNode);
}

运行后：

Node b = new Node(1, "B");
addNode(root, b);

Node e = new Node(2, "E");
addNode(b, e);

前序遍历结果：

Visited Node A
Visiting child:
Visited Node B
Visiting child:
Visited Node E

这与您的结构一致：D

  1. 删除一个节点（及其子节点），我使用“actualMessage”作为比较。您可以根据您的实现使用您认为更好的任何内容：
void deleteNode(Node treeRoot, String message){
  Node n = treeRoot;
  if(message == n.actualMessage){
    print("Deleted Node " +n.actualMessage);
    n.parent.children.remove(n);
    return;
  }
  for(int i = 0; i < n.children.length; i++){
      deleteNode(n.children[i], message);
  }
}

运行后：

deleteNode(root, "B");

前序遍历结果：

Deleted Node B
Visited Node A

再次，似乎工作正常：D

我一有时间就会更新这个

于 2020-05-17T09:01:12.627 回答