在Java中按級別打印AVL樹

我正在嘗試使用AVL樹並逐級顯示它，但我失敗了，不知道在哪裏。附件是顯示我當前輸出的圖像。我實際應該得到的是一個完整的二叉樹，所以顯然有些問題。在附加的圖像中，有一張我的「byLevel」打印函數的照片，所以您可以看到我如何嘗試打印它們，並且我將附加插入函數，因爲這些是唯一對此部分很重要的兩個函數。我很感激任何幫助，我不明白我做錯了什麼，因爲這是一個常用的算法。在Java中按級別打印AVL樹

private Node insert(Node newNode, String newWord){ 
    if(newNode == null){ 
     newNode = new Node(newWord); 
    } 
    else if (newWord.compareToIgnoreCase(newNode.getReservedWord()) < 0){ 
     newNode.setlChild(insert(newNode.getlChild(), newWord)); 

     if(depth(newNode.getlChild()) - depth(newNode.getrChild()) == 2){ 
      if(newWord.compareToIgnoreCase(newNode.getlChild().getReservedWord()) < 0){ 
       newNode = rotateWithLeftChild(newNode); 
      } 
      else{ 
       newNode = doubleWithLeftChild(newNode); 
      } 
     } 
    } 
    else if (newWord.compareToIgnoreCase(newNode.getReservedWord()) > 0){ 
     newNode.setrChild(insert(newNode.getrChild(), newWord)); 

     if(depth(newNode.getrChild()) - depth(newNode.getlChild()) == 2){ 
      if(newWord.compareToIgnoreCase(newNode.getrChild().getReservedWord()) > 0){ 
       newNode = rotateWithRightChild(newNode); 
      } 
      else{ 
       newNode = doubleWithRightChild(newNode); 
      } 
     } 
    } 
    else; 

    newNode.setDepth(max(depth(newNode.getlChild()), depth(newNode.getrChild()) + 1)); 
    /*if(!this.getAllNodes().contains(newNode)){ 
     this.getAllNodes().add(newNode); 
    }*/ 
    return newNode; 
} 

private Node rotateWithLeftChild(Node nodeToRotate){ 
    Node newNode = nodeToRotate.getlChild(); 
    nodeToRotate.setlChild(newNode.getrChild()); 
    newNode.setrChild(nodeToRotate); 
    nodeToRotate.setDepth(max(depth(nodeToRotate.getlChild()), depth(nodeToRotate.getrChild()) + 1)); 
    newNode.setDepth(max(depth(newNode.getlChild()), nodeToRotate.getDepth() + 1)); 
    return newNode; 
} 

private Node rotateWithRightChild(Node nodeToRotate){ 
    Node newNode = nodeToRotate.getrChild(); 
    nodeToRotate.setrChild(newNode.getlChild()); 
    newNode.setlChild(nodeToRotate); 
    nodeToRotate.setDepth(max(depth(nodeToRotate.getlChild()), depth(nodeToRotate.getrChild()) + 1)); 
    newNode.setDepth(max(depth(newNode.getrChild()), nodeToRotate.getDepth() + 1)); 
    return newNode; 
} 

private Node doubleWithLeftChild(Node nodeToRotate){ 
    nodeToRotate.setlChild(rotateWithRightChild(nodeToRotate.getlChild())); 
    return rotateWithLeftChild(nodeToRotate); 
} 

private Node doubleWithRightChild(Node nodeToRotate){ 
    nodeToRotate.setrChild(rotateWithLeftChild(nodeToRotate.getrChild())); 
    return rotateWithRightChild(nodeToRotate); 
}

TestOutput

來源

2017-04-21 K. Kennedy

目前我無法理解你到底在做什麼，因爲很多代碼都已丟失，而且不可能重現它。我可以建議的僅僅是這樣的情況下廣泛使用的「最佳實踐」：準備一個JUnit來測試所有4個相關的AVL輪換案例，並檢查它們是否正常工作。通過這種方式，您還可以更改您的問題，解釋不工作的內容，並且在插入操作不保持樹狀均衡時，您可以瞭解什麼是錯誤的以及您（或我們）可以調查的位置。 PS：在訪問中添加節點深度：我認爲那裏有問題。 – Sampisa

再次固定我自己的問題，是的，提供的代碼就足夠了。問題很簡單，我錯誤地計算了我的深度，給max函數的第二個加了+1，而不是在max函數後面加上+1。由於AVL樹是常見的編碼，我認爲這個問題已經足夠明確。謝謝。

來源

2017-04-25 04:11:26

在Java中按級別打印AVL樹

回答

相關問題