Java实现二叉树格式化打印根节点出现多余0的问题求解

问题原因 #

• 最直接的错误原因是PrintableTree.getInstance()返回了无参构造的TreeNode实例，int类型的成员变量i没有被赋值，默认初始化为0，后续所有插入的元素都作为这个0节点的子节点存在，所以输出会多出来根节点0。
• 深层原因是类职责设计混乱：TreeNode是二叉树的节点实体，不应该继承容器类BinaryTree，也不应该实现PrintableTree接口，容器操作的逻辑应该全部收敛到BinaryTree中实现。

修复方案 #

1. 修正TreeNode定义，移除错误继承

// 去掉extends BinaryTree和implements PrintableTree
public class TreeNode {
    private int i;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int i) {
        this.i = i;
    }

    public TreeNode() {

    }

    // 节点自身的插入逻辑保留
    public void add(int i) {
        if (i > this.i) {
            if (this.rightChild == null) {
                this.rightChild = new TreeNode(i);
            } else {
                this.rightChild.add(i);
            }
        } else {
            if (this.leftChild == null) {
                this.leftChild = new TreeNode(i);
            } else {
                this.leftChild.add(i);
            }
        }
    }

    public int getI() {
        return i;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    // 节点自身的打印逻辑保留
    public String prettyPrint() {
        StringBuilderPlus builder = new StringBuilderPlus();
        prettyPrint(builder, "", "", "", "");
        return builder.toString();
    }

    public void print() {
        StringBuilderPlus res = new StringBuilderPlus();
        prettyPrint(res, "", "", "", "");
    }

    public void prettyPrint(StringBuilderPlus result, String prefix, String left, String mid, String right) {
        String indent = " ".repeat(String.valueOf(i).length());
        if (leftChild != null) {
            leftChild.prettyPrint(result, prefix + left + indent, " ", "┌", "│");
        }
        result.appendLine(prefix + mid + i
                + " ┐┘┤".charAt((leftChild != null ? 2 : 0)
                + (rightChild != null ? 1 : 0)));
        if (rightChild != null) {
            rightChild.prettyPrint(result, prefix + right + indent, "│", "└", " ");
        }
    }
}

2. 让BinaryTree实现PrintableTree接口

class BinaryTree implements PrintableTree {
    private TreeNode root;

    public void Print() {
        if (root != null) {
            System.out.println(root.prettyPrint());
        }
    }

    @Override
    public void add(int i) {
        if (root == null) {
            root = new TreeNode(i);
        } else {
            root.add(i);
        }
    }

    @Override
    public String prettyPrint() {
        return root == null ? "" : root.prettyPrint();
    }
}

3. 修改PrintableTree的实例化逻辑

public interface PrintableTree {
    void add(int i);
    String prettyPrint();

    static PrintableTree getInstance() {
        // 返回容器类BinaryTree实例，不再返回空TreeNode
        return new BinaryTree();
    }
}

4. 保留工具类StringBuilderPlus不变

public class StringBuilderPlus {
    private StringBuilder sb;

    public StringBuilderPlus(){
        sb = new StringBuilder();
    }

    public void append(String str)
    {
        sb.append(str != null ? str : "");
    }

    public void appendLine(String str)
    {
        sb.append(str != null ? str : "").append(System.getProperty("line.separator"));
    }

    public String toString()
    {
        return sb.toString();
    }
}

测试代码 #

public class Test {
    public static void main(String[] args) {
        PrintableTree tree = PrintableTree.getInstance();
        int[] input = {123, 11, 200, 1, 100, 150, 2000};
        for (int num : input) {
            tree.add(num);
        }
        System.out.println(tree.prettyPrint());
    }
}

运行后即可得到你预期的输出结果，不会再出现多余的0。

内容的提问来源于stack exchange，提问作者Richard Walker