无法平衡二叉树

Question

我对算法很陌生，我正在学习二叉树以及如何平衡它们。我面临的问题是，即使平衡了二叉树，我也得到了树的高度和以前一样。在我看来，在平衡(这有平衡的空间)二叉树之后，树的高度会发生变化。以下是我的代码：-

class Node
{
   Node left;
   Node right;
   int info;
   public Node(int info)
   {
      this.info = info;
   }
}
public class NewBST
{
   public Node root;

   public NewBST()
   { }
   // ADD
   public boolean add(int info){
      if( root == null )
      {
         root = new Node(info);
         return true;
      }
      else
         return addRec(info, root);
   }
   public boolean addRec(int info, Node n)
   {
      if( info <= n.info )
      {
         if( n.left == null )
         {
            n.left = new Node(info);
            return true;
         }
         else
         {
            return addRec(info, n.left);
         }
      }
      if( info > n.info )
      {
         if( n.right == null )
         {
            n.right = new Node(info);
            return true;
         }
         else
         {
            return addRec(info, n.right);
         }
      }
      return true;
   }
   // CONTAINS
   public boolean contains( int v )
   {
      return contains(v, root);
   }
   public boolean contains( int v, Node n )
   {
      if(n== null){
        return false;
      }
      else if(v == n.info){
        return true;
      }
      else if(v <n.info){
        return contains(v,n.left);
      }
      else{
        return contains(v, n.right);
      }
      //return true;
    }
// MIN
   public int min(Node n)
   {
      if( n.left != null )
         return min(n.left);
      return n.info;
   }

  //HEIGHT
   public int height(Node n)
   {
      //fix this code!
      if(n==null){
        return 0;
      }
      return 1+ Math.max(height(n.left), height(n.right));
   }
   public int height()
   {
      return height(root);
   }

   // DISPLAY
   public void display( int n ){
      if( n == 0 )
      {
         infix( root );
         System.out.println();
      }
      else if( n == 1 )
      {
         postfix( root );
         System.out.println();
      }
      else if( n == 2 )
      {
         prefix( root );
         System.out.println();
      }
   }
   // TRAVERSE
   public void prefix(Node n)
   {
    if(n!=null)
        System.out.print(n.info +" ");
        prefix(n.left);
        prefix(n.right);
   }

   public void postfix(Node n)
   {
    if(n!=null){
        postfix(n.left);
        postfix(n.right);
        System.out.print(n.info + " ");
    }
   }

    public void infix(Node n)
   {
    if(n!=null){
        infix(n.left);
        System.out.print(n.info + " ");
            infix(n.right);
    }
   }


   public void infix(Node n, ArrayList<Integer> list)
   {
    if(n!=null){
        infix(n.left,list);
        list.add(n.info);
        infix(n.right,list);
    }
   }
//BALANCE
   public void balance()
   {
    ArrayList<Integer> list= new ArrayList<Integer>();
    NewBST bst= new NewBST();
    infix(root, list);

    balRec(list, 0, list.size()-1,bst);

   }

   public void balRec(ArrayList<Integer> list, int low, int high,NewBST bst){
      if( high<low){
         return;
      }
    int mid= (low + high)/2;
    bst.add(list.get(mid));
    balRec(list, low, mid-1,bst);
    balRec(list,mid+1, high,bst);
   }

  //MAIN
   public static void main(String[] args)
   {
      Scanner inp = new Scanner(System.in);
      ArrayList<Integer> store = new ArrayList<Integer>();
      NewBST bst = new NewBST();
      int nCount = 0;
      while( nCount < 32 )
      {
         int t = (int)(Math.random() * 36);
         if( !bst.contains(t) )
         {
            bst.add(t);
            store.add(t);
            nCount++;
         }
      }
      System.out.print( "Height of tree = " + bst.height());
      bst.balance();
      System.out.println();
      System.out.println( "Height of tree = " + bst.height());
      bst.display(0);

   }
}

我不确定代码是否正确地平衡了我的二叉树。我花了几个小时调试这个程序，还没有想出一个修复/解决方案。任何帮助都是非常感谢的。

谢谢,

Answer 1

首先，让我解释一个平衡二元搜索树的高度方案。高度平衡二叉树被定义为一个二叉树，其中两个子树(左和右)的高度之差不超过一个。

你的问题是，即使平衡了树，你的身高也是一样的。我在你的代码中看到了一个小错误。平衡之后，您必须将新值分配给根节点。这是计算平衡二叉树高度所必需的。因此，在balance方法代码中添加以下内容：

public void balance(){
    ArrayList<Integer> list= new ArrayList<Integer>();
    NewBST bst= new NewBST();
    infix(root, list);

    balRec(list, 0, list.size()-1,bst);
    root= bst.root;     
}

希望这能有所帮助。