バイナリ検索ツリーの差分キー

Question

私は昨日この質問をしましたが、私はまだ完全に紛失し混乱しています。

/** 
    * A wrapper method for a method that computes the 
    * sum of the differential keys of this binary search tree. 
    * @return the sum of the differential keys of this tree. 
    */ 
    @Override 
    public int sigma() 
    { 
     if (size == 0) 
      return 0; 
     if (root.data.getClass() != Integer.class) 
      throw new IllegalArgumentException("Keys must be integers"); 
     return (Integer)root.data + sigma(root); 
    } 

    /** 
    * An auxiliary method that recursively computes the sum of 
    * differential keys in the subtrees of the tree rooted at 
    * the specified key. 
    * @param subtreeRoot the root of a subtree of this tree 
    * @return the sum of the differential keys of the left and 
    * right subtrees 
    */ 
    private int sigma(Node subtreeRoot) 
    { 
     // My attempt at implementing the auxiliary method 
     if(subtreeRoot == null) return 0; 
     return sigma(subtreeRoot.left) - (Integer)subtreeRoot.data + 
       sigma(subtreeRoot.right) - (Integer)subtreeRoot.data; 
    } 

注：我々は、いずれかのメソッドにパラメータを追加することはできませんか、コードを変更私は2つの方法で、ラッパー・メソッドと以下のように定義されたsigma()という名前の再帰的な補助方法を、記述しようとしていますラッパーメソッドの内部

---

キー微分の定義：ノードがある場合の要素整数であるバイナリツリー内のノードの

定義1.差分キーは、ノードの要素である ルートまたはノード内の要素と親の 親の間の違いです。 ヌルノードの差動Iは、基本ケース、if(subtreeRoot == null) return 0;をカバーしている0

ですが、その後、私は混乱しています。ここ メソッドが何をすべきかの例である：

補助方法はBSTに全ての差分キーの和の値を返すべきである（-1この例では）、次いで、ラッパー・メソッドはそれを追加します値をルートノードの値（この例では10）に設定します。したがって、差分キーとsigma（）によって返される値の合計は10 +（-1）= 9です。

私が抱えている主な問題は、補助的な方法で再帰的なソリューションを実装することです。私は紙に簡単に解決策をトレースすることができますが、私は私のプロジェクトにこれを実装するように見えることはできません。私はこれについてオンラインでリソースを見つけることができず、私の教授はほとんど役に立たない。補助的なメソッドを実装しようとする試みは上記のコードに含まれています。どんな助けもありがとうございます。

Answer 1

私は問題がどこにあるのか理解していると思います。

コードを使用した1つの例を見てみましょう。 4を有するノードで

、

sigma(subtreeRoot.left) - (Integer)subtreeRoot.data 

は-4と

sigma(subtreeRoot.right) - (Integer)subtreeRoot.data 

の値が間違っている-8の合計シグマを与え、-4の値を返すもたらします。

最終結果の一部として使用する前に、subtreeRoot.leftがnullであるかどうかを確認することをお勧めします。これはsubtreeRoot.rightでも同様に行う必要があります。

int tot = 0; 
if(subtreeRoot == null) return 0; 
if (subtreeRoot.left != null) 
    tot = sigma(subtreeRoot.left) - (Integer)subtreeRoot.data; 
if (subtreeRoot.right != null) 
    tot += sigma(subtreeRoot.right) - (Integer)subtreeRoot.data; 
return tot; 

私はこれが役に立てば幸い：

は、私はあなたのコードは次のようなものになってしまいます想像してみてください。

Answer 2

あなたが試すことができるのは差分ボトムアップを計算することです。子のすべてのノードを更新したら、親を更新します。各メソッド呼び出しは、ノードsubtreeRootなく差動