树结构未正确打印

Question

我在 Java 中创建的基本二叉搜索树遇到问题。我正在尝试在控制台中输出树结构，并在节点值之前加上前缀空格，以表示节点的深度。

出于某种原因，我的 printTree() 函数正在输出一个看起来稍微倒退的树结构。我不认为 (5 0.0) 会被缩进，因为它会作为根保留在像这样的基本树中。

下面是我的函数和输出：

注意：c创建根，s添加键和值，xp输出树。

private int k;
private float d;
private Node left, right;

public Node(int k) {
    this.k = k;
}

public Node(int k, float d) {
    this.k = k;
    this.d = d;
}

private int height(Node n) {
    if (n == null)
        return -1;
    return 1 + Math.max(height(n.left), height(n.right));
}

private void printTree(Node n) {
    if (n == null)
        return;
    System.out.println(new String(new char[3 * height(n)]).replace("[=10=]", " ") + "(" + n.k + " " + n.d + ") ");
    printTree(n.left);
    printTree(n.right);
}

输出：

我很确定根据我的输入，5 根本不应该缩进，因为它是根节点。

我认为它应该类似于（基于二叉搜索树）：

(5 0.0)
    (4 1.2)
        (2 3.5)
    (6 7.5)
        (87 96.5)

（当然有正确数量的前置空格）

任何人都可以解释我做错了什么吗？

Answer 1

您计算的空格数为3*height(n)。 height(n)计算左右树的最大路径长度，所以根永远在最右边。

要么将节点的高度计算为从节点到根的路径长度，要么预先计算最大高度并将节点的空白数设置为maxHeight - height(n)。

树结构未正确打印

Tree Structure Not Correctly Printing Out

java

tree

key

binary-search-tree