Java 中没有 setter 的平衡二叉树

Question

我正在做一项关于创建平衡二叉树的学校作业。 Node 和 Tree 的接口由声明的方法提供。但是，Node 接口只有 getLeft、getRight 和 getValue 方法，没有 setter。由于我们只提交实现文件进行评分，因此我通过使用实现 class 本身而不是接口来进行打字来解决这个问题。

当我给老师发消息时，他告诉我可以只使用 Node 构造函数来实现它，添加一个 "hint" 那 "For every node, its child are also trees." 这是显而易见的，但我不确定如何实现那就是帮我。

在我看来，如果不使用 setter，我首先需要基本上预先绘制出树，然后从底部而不是从顶部开始构建它，这似乎不必要地复杂且违反直觉。有没有我遗漏的技巧？

感谢您提供的任何帮助或建议。

我目前的实现如下：

TreeImpl.java

public class TreeImpl implements Tree {
    private NodeImpl root;

    public TreeImpl() {}

    @Override
    public void setTree(int[] values) {
        this.root = null;
        Arrays.sort(values);
        recurseSet(values);
    }

    private void recurseSet(int[] values) {
        if (values.length > 0) {
            int middleIndex = values.length / 2;
            NodeImpl tempNode = new NodeImpl(values[middleIndex]);
            insert(tempNode, root, 1);
            recurseSet(cutArray(values, 0, middleIndex - 1));
            recurseSet(cutArray(values, middleIndex+1, values.length-1));
        }
    }

    private int[] cutArray(int[] array, int begin, int end) {
        int length = end-begin+1;
        int[] newArray = new int[length];
        System.arraycopy(array, begin, newArray, 0, length);
        return newArray;
    }


    private void insert(NodeImpl node, NodeImpl location, int depth) {
        if (root == null) {
            root = node;
            return;
        }
        if (node.getValue() < location.getValue()) {
            /* left branch */
            if(location.getLeft() == null) {
                node.setDepth(depth);
                location.setLeft(node);
            } else {
                insert(node, location.getLeft(), depth+1);
            }

        } else {
            /* right branch */
            if(location.getRight() == null) {
                node.setDepth(depth);
                location.setRight(node);
            } else {
                insert(node, location.getRight(), depth+1);
            }
        }

    }

    @Override
    public Node getRoot() {
        return root;
    }

    private String toString(NodeImpl root) {
        String finalString = "";
        if (root != null) {
            finalString += root;
            finalString += toString(root.getLeft());
            finalString += toString(root.getRight());
        }
        return finalString;
    }

    @Override
    public String toString() {
        return toString(root);
    }
}

NodeImpl.java

public class NodeImpl implements Node {
    private int value;
    private NodeImpl left;
    private NodeImpl right;
    private int depth = 0;

    public NodeImpl(int value) {
        this.value = value;
    }

    public void setLeft(NodeImpl left) {
        this.left = left;
    }

    public void setRight(NodeImpl right) {
        this.right = right;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }

    @Override
    public NodeImpl getLeft() {
            return left;
    }

    @Override
    public NodeImpl getRight() {
        return right;
    }

    @Override
    public int getValue() {
        try {
            return value;
        } catch (NullPointerException e) {
            System.out.println("Null pointer.");
        }
        return 0;
    }

    @Override
    public String toString() {
        String finalString = "";
        for(int i = 0; i < depth; i++) {
            finalString += " ";
        }
        finalString += "- ";
        finalString += value;
        finalString += "\n";
        return finalString;
    }

}

Answer 1

我试了一下你的代码，我想我已经知道怎么做了：

class NodeImpl implements Node {
    private int value;
    private Node left;
    private Node right;

    public NodeImpl(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public int getValue() {
        return value;
    }

    @Override
    public String toString() {
        // here you have to put some nice drawing logic.
        return  (left != null ? left.toString() : "") + "<-" + value + "->" + (right != null ? right.toString() : "");
    }
}

class TreeImpl implements Tree {
    private Node root;

    public void setTree(int[] values) {
        Arrays.sort(values);
        this.root = recurseSet(values);
    }

    private Node recurseSet(int[] values) {
        if (values.length > 0) {
            int middleIndex = values.length / 2;
            return new NodeImpl(
                values[middleIndex], recurseSet(cutArray(values, 0, middleIndex - 1)),
                recurseSet(cutArray(values, middleIndex + 1, values.length - 1))
            );
        } else {
            return null;
        }
    }

    private int[] cutArray(int[] array, int begin, int end) {
        int length = end - begin + 1;
        int[] newArray = new int[length];
        System.arraycopy(array, begin, newArray, 0, length);
        return newArray;
    }

    public Node getRoot() {
        return root;
    }
}

你会像这样使用你的类：

public static void main(String[] args) {
    final Tree tree = new TreeImpl();
    tree.setTree(new int[]{1, 10, 9, 8, 2, 5});
    System.out.println(tree.getRoot().toString());
}

你只需要考虑如何实现 NodeImpl.toString() 方法来很好地绘制每个节点 :) 希望它能对你有所帮助。

Java 中没有 setter 的平衡二叉树

Balanced Binary Tree in Java without setters

java

setter

tree

binary-tree