Сбалансированное двоичное дерево на Java без сеттеров

Question

Я работаю над заданием школы о создании сбалансированного двоичного дерева. Интерфейсы для узла и дерева были снабжены объявленными методами. Однако интерфейс узла имел только getLeft, getRight и getValue методы, без сеттеров. Поскольку мы отправляем для оценки только файлы реализации, я работал над ним, используя сам класс реализации для ввода, а не интерфейса.

Когда я послал сообщение учителю, он сказал мне, что можно реализовать его, используя только конструктор узла, добавив «подсказку», что «для каждого узла его дочерние элементы также являются деревьями». что очевидно, но я не уверен, как это мне помочь.

Мне кажется, что без использования сеттеров мне сначала нужно было вначале отобразить дерево заранее, а затем начать строить его снизу, а не сверху, что кажется излишне сложным и контр-интуитивным. Есть ли какой-то трюк, которого я пропускаю?

Благодарим за помощь или совет, которые вы можете предложить.

Моей текущей реализации является следующим:

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() метод для прорисовки каждого узла в хорошем способе :) Я надеюсь, что это поможет.