Recursivleyバイナリ検索ツリーが完成したかどうかのテスト

Question

数日前、この同じプロジェクトに関する質問をしました。私たちのグループは、バイナリ検索ツリーが存在するかどうかを判断するために使用されるメソッドコンプリート。

ラッパーメソッドとヘルパーメソッドを使用して再帰的に実行しています。

ツリーのh-1レベル（hは高さ）までチェックして完全であることを確認する必要があることがわかっているので、最終レベルのすべてのリーフノードが左から隙間なく右に。

私たちが何を試しても、残っているリーフノードを再帰的にチェックして、それらが左から右へ連続していることを確認する方法を見つけることはできません。しかし、我々はそれがレベル（h-1）まで完璧であることを確かめることができる。

最後のレベルの葉ノードを再帰的にチェックして、それらが左揃えになっていることを確認する方法について、誰かが正しい方向を教えてくれますか？

これまでのコードは？すべての些細な例は、すべて完璧なツリー以来isPerfect（）メソッドで処理され

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も完了し

Answer 1

私は私の教授と通信することができた、と彼はここに与えられたいくつかの回答に比べてO（n）のisCompleteメソッドに一つだけのパラメータでそれを行う方法を、MOF通知しました。

HR> hLのツリーが完了していない場合は、ここで、この答えは、私の元の質問

1. ための最良の答えです。
2. hL-HR> 1の場合、ツリーは完全ではありません。 、その後、左 サブツリーは完璧でなければならず、右のサブツリー 必見 -
hRの== hLの場合は、左の部分木が完璧でなければならず、右のサブツリーが（HR == 1 HL）そう
3. 完了していなければならない
4. 完璧である。

ツリーisPerfect（場合3と4は、再帰的にチェックしなければならない段階）とisComplete（）

Answer 2

私は完全に確認するために最初の音符にアルゴリズムを試し、その後、コードに移ります

。

これをプリオーダートラバーサルアプローチで考えてみましょう。

• ノードがnullである場合にノードインデックスがより大きい（または、ある場合にノードインデックス0
• として根を処理すること、ツリーは
• 完了し、ルートからツリー
• 再帰内のノードの数を必要としますツリー内のノード数に等しい）、それは完全ではない
• recurse left and right subtree;プリオーダートラバーサルアプローチを考えると、左ツリーはインデックス2*i + 1を取得し、右ツリーは2*i + 2を取得します。

これがなぜ機能するのか理解しているビット。

以下は完全なツリー[角括弧内のノードインデックス付き]です。 この完全なバイナリツリーの場合のノードインデックスは、完全なバイナリツリーのノードの数よりも厳密に少ないことに注意してください。

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

関数[ルートクラスフィールドであるので0パラメータで、]次にツリー

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

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

内のノードの総数は、ラッパーisComplete（）関数を返す ...

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