二叉搜索树到字符串

Question

我需要创建一个将 BST 转换为字符串的方法，每个 child 都以缩进字符为前缀。

示例：

BinaryTreeSet set=new BinaryTreeSet();
set.add(6);
set.add(4);
set.add(3);
set.add(5);
set.add(9);
set.add(10);
set.add(8);
set.add(0);
System.out.println(set.treeString());

应该生产

=> 6
  => 4
    => 3
      => 0
    => 5
  => 9
    => 8
    => 10

我已经尝试了几个小时了，但我没有取得任何进展。

我能得到的最好的是

=> 6
=> 0
=> 3
=> 5
=> 4
=> 8
=> 10
=> 9

使用以下代码：

public String treeString() {

    StringBuilder builder = new StringBuilder("=> " + root);
    builder.append(System.getProperty("line.separator"));

    nodeString(root, builder);

    return builder.toString();

    }

    private void nodeString(BinaryTreeNode node, StringBuilder builder) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            nodeString(node.left, builder);
            builder.append("=> " + node.left);
            builder.append(System.getProperty("line.separator"));
        }
        if (node.right != null) {
            nodeString(node.right, builder);
            builder.append("=> " + node.right);
            builder.append(System.getProperty("line.separator"));
        }
    }

不知怎的，我不知道如何得到正确的顺序... 我也不知道如何正确地缩进。

谢谢！

Answer 1

尝试将 builder.append 行放在之前递归 nodeString 调用。如果您在示例输出中还需要缩进，您还需要跟踪递归调用中的调用深度。

Answer 2

这解决了我们学习的 BST 定义问题：

private void nodeString(BinaryTreeNode node, StringBuilder builder, int count) {
        if (node == null) {
            return;
        }
        // Left
        if (node.left != null) {
            for (int i = 0; i < count; i++) { // Adding indent
                builder.append("  ");
            }
            builder.append("=> " + node.left);
            builder.append(System.getProperty("line.separator"));
            nodeString(node.left, builder, ++count);
            --count;
        }
        // Right
        if (node.right != null) {
            for (int i = 0; i < count; i++) { // Adding indent
                builder.append("  ");
            }
            builder.append("=> " + node.right);
            builder.append(System.getProperty("line.separator"));
            nodeString(node.right, builder, ++count);
            --count;
        }
    }

二叉搜索树到字符串

Binary Search Tree to String

java

stringbuilder

binary-search-tree