我正在做一项关于创建平衡二叉树的学校作业。 Node 和 Tree 的接口(interface)由声明的方法提供。但是,Node 接口(interface)只有 getLeft
、getRight
和 getValue
方法,没有 setter。由于我们只提交实现文件进行评分,因此我通过使用实现类本身而不是接口(interface)来进行打字来解决这个问题。
当我给老师发消息时,他告诉我可以仅使用 Node 构造函数来实现它,并添加了“对于每个节点,其子节点也是树”的“提示”。这很明显,但我不确定这对我有何帮助。
在我看来,如果不使用 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;
}
}
最佳答案
我试了一下你的代码,我想我已经想出了如何做到这一点:
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的Java中的平衡二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36296157/