Dart 中的随机二叉树

Question

我需要生成仅给定节点数的随机二叉树。我想用类的链接树结构来完成它。可能吗？或者还有其他方法吗？我找不到这方面的任何资源。我想一个类似 java 的例子也可以。

Answer 1

您可以通过多种不同的方式执行此操作。这是一种可能的方法。它创建节点，然后通过遍历每个节点并从具有开放点的节点中为其提供随机父节点来连接它们。

import 'dart:math';

const maxNodes = 10;

void main() {
  final rng = Random();
  final nodes = List.generate(maxNodes, (index) => Node(index + 1));
  final openNodes = [nodes[0]];
  nodes.skip(1).forEach((node) {
    node.parent = openNodes[rng.nextInt(openNodes.length)];
    openNodes.add(node);
    if (node.parent.right != null ||
        (node.parent.left == null && rng.nextBool())) {
      node.parent.left = node;
    } else
      node.parent.right = node;
    if (node.parent.left != null && node.parent.right != null)
      openNodes.remove(node.parent);
  });
  nodes.forEach(print);
}

class Node {
  Node(this.id);
  final int id;
  Node parent;
  Node left;
  Node right;
  @override
  String toString() => '$id: (${left?.id ?? '_'}, ${right?.id ?? '_'})';
}

在 DartPad 上进行测试。

Dart 中的随机二叉树

Random Binary Tree in Dart

binary-tree

dart