二叉搜索树bst

Question

所以，我需要构建一个不平衡的二叉搜索树，创建一个平衡它的方法，我通过构建基于水平顺序遍历（或至少尝试）的排序数组，然后打印取出平衡二叉搜索树。这是我的尝试，但它只是输出内存位置。帮帮我 ！

public class BalanceTree { 
     public static BST balanceTree(int[]list){ 
     if(list.length==0)//if length is zero, then empty list, cannot balance 
     return null; 

     return balanceTree(list,0,list.length-1);}//recursively call balance 

    public static BST balanceTree(int[] list, int begin, int end){//take sorted array from unbalanced tree 
     if (begin>end) 
     return null; 
     int mid = (begin+end)/2;//find midpoint, assign as root node 
     BST chld = new BST(list[mid]); 
     chld.left = balanceTree(list,begin,mid-1);//assign as left child 
     chld.right = balanceTree(list, mid+1,end);//assign as right child 
     return chld; 
    } 


    public static void levelOrderPrint(Node node){ 
      int h = height(node); 
      for(int i=1; i<=h;i++){ 
       printLevel(node,i); //print every level 

      } 
    } 
    public static int height (Node t)//find height of tree 
     { 
     if (t.left == null && t.right == null) //leaf check 
      return 0; 
     else if (t.left == null) 
      return 1 + height(t.right); 
     else if (t.right == null) 
      return 1 + height(t.left); 
     else 
      return 1 + Math.max(height(t.left),height(t.right)); 
     } 

    public static void printLevel(Node node, int level){ 
      if(node ==null){ 
       return; 
      } 
      if(level == 1){ 
       System.out.println(node); 
      } 
      else if (level > 1){ 
       printLevel(node.left,level-1); 
       printLevel(node.right,level-1); 
      } 
     } 


    public static void main(String[] args) { 
     Node node = new Node(); 
     node.root=26; 
     int [] sortedArray = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26}; 


     System.out.println("Now Building Unbalanced Tree. Root Node: " + node.root); 
     node.insertNode(node, 25); 
     node.insertNode(node, 24); 
     node.insertNode(node, 23); 
     node.insertNode(node, 22); 
     node.insertNode(node, 21); 
     node.insertNode(node, 20); 
     node.insertNode(node, 19); 
     node.insertNode(node, 18); 
     node.insertNode(node, 17); 
     node.insertNode(node, 16); 
     node.insertNode(node, 15); 
     node.insertNode(node, 14); 
     node.insertNode(node, 13); 
     node.insertNode(node, 12); 
     node.insertNode(node, 11); 
     node.insertNode(node, 10); 
     node.insertNode(node, 9); 
     node.insertNode(node, 8); 
     node.insertNode(node, 7); 
     node.insertNode(node, 6); 
     node.insertNode(node, 5); 
     node.insertNode(node, 4); 
     node.insertNode(node, 3); 
     node.insertNode(node, 2); 
     node.insertNode(node, 1); 
     System.out.println("*********************************************"); 
     System.out.println("Now building balanced binary search tree: "); 

     //int[] arr = 
     levelOrderPrint(node);// I know this should be the array " arr" which is passed into the balance tree method 
    balanceTree(sortedArray,0,25);// I know this must use the array from the "levelorderPrint" method, 
    //but i could not get it to compile, so i substituted in an already sorted array. 



    } 
    } 

     public class BST{//constructing bst node 
     int val; 
     BST left; 
     BST right; 
     BST(int x){ 
     val = x;} 
    } 
    public class Node { 
Node node; 
int root; 
Node left; 
Node right; 

public void insertNode(Node node, int num) { //building unbalanced tree 
    if(num < node.root) // if current node is less than root node, insert to the left 
    { 
    while(node.left != null) 
    { 
    node = node.left; 
    if(num > node.root){ //if current node is greater than root node, insert to the right 

    Node temp = new Node(); 
    temp.root = num; 
    node.right = temp; 
    System.out.println("Inserting "+ num + "" + "at right of" + node.root); 
    } 
    } 
    Node temp = new Node(); 
    temp.root = num; 
    node.left = temp; 
    System.out.println("Inserting " +num + "" + "at left of" + node.root); 
    } 
} 

public String toString(){ 

    return root+ ""; 

} 


} 

Answer 1

在Java中的每个对象都实现了toString（）方法。默认情况下（如Object类中所写），对象将打印其“内存位置”。

为了能够在Java中打印对象，您需要覆盖方法toString（）。

Answer 2

在你的行System.out.println(node);中，你告诉Java调用node.toString()。由于您没有为自定义Node类制作自己的toString()方法，Java会自动使用Object.toString()方法，该方法返回内存地址。考虑在您的代码中添加如下内容：

public class Node { 
    ... 
    public String toString() { 
     return root + ""; 
    } 
    ... 
}