無法平衡二叉樹

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

首先，讓我解釋一個平衡二叉搜索樹的高度方案。高度平衡二叉樹定義爲一棵二叉樹，其中兩棵子樹的高度（左右）之間的差值永遠不會超過1。

你的問題是，即使在平衡了樹之後，你也獲得了相同的高度。我在代碼中看到一個小錯誤。平衡後，您必須將新值分配給根節點。這是計算平衡二叉樹高度所必需的。所以，添加以下到您的平衡方法代碼：

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;  
} 

希望這有助於。