如何在 Dart 中打印二叉树图？

Question

我有一个这样的二叉树节点：

class BinaryTreeNode<T> {
  BinaryTreeNode(this.value, {this.leftChild, this.rightChild});
  T value;
  BinaryTreeNode? leftChild;
  BinaryTreeNode? rightChild;
}

我想添加一个 toString 方法，以便我可以直观地表示二叉树的内容。

这是 this Java question 的 Dart 版本。我能够在那里移植其中一个答案，所以我在下面添加它。

Answer 1

这里是 this answer 的修改版本：

class BinaryTreeNode<T> {
  BinaryTreeNode(this.value, {this.leftChild, this.rightChild});
  T value;
  BinaryTreeNode<T>? leftChild;
  BinaryTreeNode<T>? rightChild;

  @override
  String toString() {
    final out = StringBuffer();

    rightChild?._buildTree(out, true, '');
    out.writeln(value);
    leftChild?._buildTree(out, false, '');

    return out.toString();
  }

  void _buildTree(StringBuffer out, bool isRight, String indent) {
    rightChild?._buildTree(out, true, indent + (isRight ? '     ' : '│    '));

    out
      ..write(indent)
      ..write(isRight ? '┌─── ' : '└─── ')
      ..writeln(value);

    leftChild?._buildTree(out, false, indent + (isRight ? '│    ' : '     '));
  }
}

如果你像这样构建一棵树：

void main() {
  final tree = BinaryTreeNode('D',
      leftChild: BinaryTreeNode('A'),
      rightChild: BinaryTreeNode(
        'R',
        leftChild: BinaryTreeNode('T'),
        rightChild: BinaryTreeNode('Fun'),
      ));
  print(tree);
}

输出如下所示：

     ┌─── Fun
┌─── R
│    └─── T
D
└─── A

请随意将我的答案修改为简单的代码。我觉得 toString 方法可以简化为不重复那么多代码。

lrn 的建议解决方案

以下解决方案更有效，因为我们在遍历树结构时避免创建中间字符串对象。感谢 lrn 推荐这种方法：

class BinaryTreeNode<T> {
  BinaryTreeNode(this.value, {this.leftChild, this.rightChild});

  T value;
  BinaryTreeNode<T>? leftChild;
  BinaryTreeNode<T>? rightChild;

  @override
  String toString() {
    final out = StringBuffer();

    final indents = <String>[];
    rightChild?._buildTree(out, true, indents);
    out.writeln(value);
    leftChild?._buildTree(out, false, indents);

    return out.toString();
  }

  void _buildTree(StringBuffer out, bool isRight, List<String> indents) {
    if (rightChild != null) {
      indents.add(isRight ? '     ' : '│    ');
      rightChild!._buildTree(out, true, indents);
      indents.removeLast();
    }

    out
      ..writeAll(indents)
      ..write(isRight ? '┌─── ' : '└─── ')
      ..writeln(value);

    if (leftChild != null) {
      indents.add(isRight ? '│    ' : '     ');
      leftChild!._buildTree(out, false, indents);
      indents.removeLast();
    }
  }
}

如何在 Dart 中打印二叉树图？

How to print binary tree diagram in Dart?

binary-tree

dart

lrn 的建议解决方案