二叉搜索树差分键

昨天我问了这个，但我仍然完全迷茫和困惑。我想写两个方法，一个包装方法和递归的辅助方法，名为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

二叉搜索树差分键

回答

相关问题