二叉搜索樹差分鍵

昨天我問了這個，但我仍然完全迷茫和困惑。我想寫兩個方法，一個包裝方法和遞歸的輔助方法，名爲sigma()，定義如下：二叉搜索樹差分鍵

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

注：我們不允許任何參數添加到任何一種方法或修改代碼包裝方法的內部。

的差分密鑰的定義：

定義1.一個節點的一二進制樹，其元素是整數的差分密鑰的節點的元素，如果該節點是根或者是該節點中的元素與其父親之間的差異。一個空節點的差是0

我已經覆蓋了基本情況，if(subtreeRoot == null) return 0;，但之後，我感到困惑。下面是該方法應當做什麼的一個示例：

輔助方法應返回的BST（-1在本例中）的所有差分密鑰的總和的值，則該包裝方法補充說值添加到根節點的值（在本例中爲10）。所以差分密鑰的總和與由Sigma（）的返回值是10 +（ - 1）= 9

我有正在執行在輔助方法遞歸溶液的主要問題。我可以很容易地在紙上找到解決方案，但似乎無法將其實施到我的項目中。我一直沒能在網上找到任何有關這方面的資源，而我的教授沒有什麼幫助。我在上面的代碼中包含了實現輔助方法的嘗試。任何幫助表示讚賞。

來源

2016-12-02 Mason Walton

主要做法是從根到下井到節點，在每一次迭代保持追蹤父節點。這樣，當你到達節點時，你會知道父節點是什麼。從那裏計算差異應該是直接的 –

根節點被傳遞到wrapper方法的return語句中的輔助方法，所以我想'subtreeRoot.left'和'subtreeRoot.right'是左邊/右邊的子節點根節點。我將如何跟蹤根節點之後的父節點？我在類中定義了一個方法'private Node findParent（Node node）'。我會將它分配給一個變量嗎？ @aimee –

好吧，我想我明白問題出在哪裏。

讓我們看一個使用你的代碼的例子。

在具有4節點，

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

將產生和-4值

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

將返回-4值，給人-8共西格瑪，這是不對的。

我建議你應該做的是檢查是否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;

我希望這有助於。

來源

2016-12-02 14:42:29 skw

起初，我有一些if語句，代表沒有孩子的父節點，一個孩子（左/右）或者左右孩子。但是，當我昨天在這裏發表了關於此問題的原始問題時，我被告知這太複雜了......不過，我會試試這個。 –

你可以嘗試的是計算自下而上的差分。一旦你更新了孩子的所有節點，你就更新了父母。

private int sigma(Node subtreeRoot) 
{ 
    // My attempt at implementing the auxiliary method 
    if(subtreeRoot == null) 
     return 0; 
    else { 
     if(subtreeRoot.left != null){    
     subtreeRoot.left.data = sigma(subtreeRoot.left) - subtreeRoot.data; 
     } 
     if(subtreeRoot.right != null){    
     subtreeRoot.right.data = sigma(subtreeRoot.right) - subtreeRoot.data; 
     } 


     return subtreeRoot.data; 
    }

}

注意，每個方法調用返回節點subtreeRoot的原始值，而不是差分

來源

2016-12-02 14:51:15

二叉搜索樹差分鍵

回答

相關問題