Recursivley測試二進制搜索樹是否完整

Question

前幾天我問了一個關於同一個項目的問題，從那時起我們的小組已經設法完成了我們所有的方法，除了一個用於確定二叉搜索樹是否是完成。

我們使用一個包裝方法和一個輔助方法遞歸地做到這一點。

我們知道我們需要檢查樹的h-1層（h是高度）以確保它是完美的，那麼我們需要確保最後一層上的所有葉節點都從左邊開始沒有差距的權利。

無論我們嘗試什麼，我們都無法弄清楚如何遞歸檢查剩餘的葉節點，以確保它們從左到右依次連續。但是，我們可以確保它完美達到（h-1）級別。

有人能指出我們在正確的方向上如何遞歸檢查最後一級的葉節點，以確保它們左對齊嗎？

迄今爲止這是代碼？

public boolean isComplete() 
{ 
    if (isPerfect(root)) 
     return true;  
    return isComplete(root); 

} 
/** 
* 
* @param node 
* @return 
*/ 
private boolean isComplete(Node node) 
{ 
    if (height(node) > 1) 
    { 
    if (node.left != null && node.right != null && (height(node.left) == height(node.right))) 
     return isComplete(node.left) && isComplete(node.right); 
    else 
     return false; 
    } 

} 

PS，因爲每一個完美的樹中的所有瑣碎的案件在isPerfect（）方法處理也完全

Answer 1

我能夠與我的教授進行交流，並且他告訴MOF只有一個在isComplete方法參數做它的O（n）的方式相比，這裏給出一些答案。

這個答案這裏是我原來的問題

1. 如果HR>百升樹是不完整的最好的答案。
2. 如果hL-HR> 1，樹不完整。
3. 如果HR == HL，然後左子樹必須是完美的，右子樹必須完整
4. 否則（HL - HR == 1），則左子樹 必須是完美的，右子樹 絕完美。

步驟3和4必須遞歸檢查樹isPerfect（）和isComplete（）

Answer 2

我會嘗試第一個音符的算法來檢查完整性，然後移動到代碼。

讓我們在預定義遍歷方法中考慮這一點。

• 需要的節點的數量在樹
• 遞歸從根，治療根作爲節點索引0
• 如果節點爲空，樹是完整
• 如果節點索引大於（或等於）樹中節點的數量，則不完整
• 遞歸左右子樹;給定預定義遍歷方法，左樹得到索引2*i + 1，右樹得到2*i + 2。

有一點理解爲什麼這應該工作。

以下是一棵完整的樹[帶方括號中的節點索引]。 請注意，此完整二叉樹的節點索引嚴格少於完整二叉樹中的節點數。

  1 [0] 
     /\ 
     / \ 
    [1] 2  3 [2] 
    /\ 
    / \ 
[3] 4  5 [4] 

甲函數返回節點的總數目在樹現在

private int totalNodes(Node root) { 
    if (root == null) 
     return 0; 

    return 1 + totalNodes(root.left) + totalNodes(root.right)); 
} 

，包裝器isComplete（）函數[0參數，由於根是一類字段] ...

public boolean isComplete() { 
    return isCompleteHelper(root, 0, totalNodes(root)); 
} 

isCompleteHelper（）...

private booelan isCompleteHelper(Node root, int indx, int totalNodes) { 

    // empty tree 
    if (root == null)   
     return true; 

    // present index >= number of nodes in tree 
    if (indx >= totalNodes) 
     return false; 

    // recurse 
    return isCompleteHelper(root.left, 2*indx+1, totalNodes) && isCompleteHelper(root.right, 2*indx+2, totalNodes); 
}