差分键的二叉搜索树和

Question

我正在尝试将名为 sigma() 的方法实现到二叉搜索树 class 中。该方法的工作是return BST 中差分键的总和。我得到的定义如下：

Definition 1. The differential key of a node in a binary tree whose elements are integers is the element in the node if the node is the root or is the difference between the element in the node and its parent. The differential of a null node is 0. See figure 1 for an illustration of a differential binary tree. The sum of the differential keys of T is 9, ∑_i=1ⁿ ∆(i), where ∆(i) denotes the differential key of node i and n, the size of the tree.

该方法应该return 树 sigma(T) 值的总和。所以在这种情况下，sigma(T) 会 return 10-4-2+3+5-3 = 9。我理解所有这一切背后的概念并且可以轻松地在纸上完成，但将其实施到我的代码是我遇到的麻烦。我需要编写一个包装器方法和一个递归的辅助方法来定义 sigma().

这是我的 BSTree class 目前为止我写的（sigma() 接近底部）：

package bstreedemo;

import java.util.function.Function;

/**
 * A binary search tree <br>
 * Requires JDK 1.8 for Function
 * @param <E> the tree data type
 * @since 12/09/2016
 * @see BSTreeAPI
 */
public class BSTree<E extends Comparable<E>> implements BSTreeAPI<E>
{
   /**
    * the root of this tree
    */
   private Node root;
   /**
    * the number of nodes in this tree
    */
   private int size;
   /**
    * A node of a tree stores a data item and references
    * to the child nodes to the left and to the right.
    */    
   private class Node
   {
      /**
       * the data in this node
       */
      public E data;
      /**
       * A reference to the left subtree rooted at this node.
       */
      public Node left;
      /**
       * A reference to the right subtree rooted at this node
       */
      public Node right;
   } 
   /**
    *   Constructs an empty tree
    */      
   public BSTree()
   {
      root = null;
      size = 0;
   }
   @Override
   public boolean isEmpty()
   {
      return size == 0;
   }

   @Override
   public void insert(E item)
   {
      Node newNode = new Node();
      newNode.data = item;
      if (size == 0)
      {
         root = newNode;
         size++;
      }
      else
      {
         Node tmp = root;
         while (true)
         {
            int d = tmp.data.compareTo(item);
            if (d == 0)
            { /* Key already exists. (update) */
               tmp.data = item;
               return;
            }
            else if (d>0)
            {
               if (tmp.left == null)
               { /* If the key is less than tmp */
                  tmp.left = newNode;
                  size++;
                  return;
               }
               else
               { /* continue searching for insertion pt. */
                  tmp = tmp.left;
               }
            }
            else
            {
               if (tmp.right == null)
               {/* If the key is greater than tmp */
                  tmp.right = newNode;
                  size++;
                  return;
               }
               else
               { /* continue searching for insertion point*/
                  tmp = tmp.right;
               }
            }
         }
      }
   }

   @Override
   public boolean inTree(E item)
   {
      return search(item) != null;
   }

   @Override
   public void remove(E item)
   {      
      Node nodeptr = search(item);
      if (nodeptr != null)
      {
         remove(nodeptr);
         size--;
      }
   }

   @Override
   public void inorderTraverse(Function func)
   {
      inorderTraverse(root,func);
   }

   @Override
   public E retrieve(E key) throws BSTreeException
   {      
      if (size == 0)
         throw new BSTreeException("Non-empty tree expected on retrieve().");
      Node nodeptr = search(key);
      if (nodeptr == null)
         throw new BSTreeException("Existent key expected on retrieve().");
      return nodeptr.data;
   }

   @Override
   public int size()
   {
       return size;
   }   

   /**
    * A recursive auxiliary method for the inorderTraver method that
    * @param node a reference to a Node object
    * @param func a function that is applied to the data in each
    * node as the tree is traversed in order.
    */
   private void inorderTraverse(Node node, Function func)
   {
      if (node != null)
      {
         inorderTraverse(node.left,func); 
         func.apply(node.data);         
         inorderTraverse(node.right,func);
      }
   }

   /**
    * An auxiliary method that support the remove method
    * @param node a reference to a Node object in this tree
    */
   private void remove(Node node)
   {
      E theData;
      Node parent, replacement;
      parent = findParent(node);
      if (node.left != null)
      {
         if (node.right != null)
         {
            replacement = node.right;
            while (replacement.left != null)
               replacement = replacement.left;
            theData = replacement.data;
            remove(replacement);
            node.data = theData;
            return;
         }
         else
            replacement = node.left;            
      }
      else
      {       
         if (node.right != null)
            replacement = node.right;         
         else
            replacement = null;
      }
      if (parent==null)
         root = replacement;
      else if (parent.left == node)
         parent.left = replacement;
      else
         parent.right = replacement;      
   }  

   /**
    * An auxiliary method that supports the search method
    * @param key a data key
    * @return a reference to the Node object whose data has the specified key.
    */
   private Node search(E key)
   {
      Node current = root;
      while (current != null)
      {
         int d = current.data.compareTo(key);
         if (d == 0)
            return current;
         else if (d > 0)
            current = current.left;
         else
            current = current.right;
      }
      return null;
   }

   /**
    * An auxiliary method that gives a Node reference to the parent node of
    * the specified node
    * @param node a reference to a Node object
    * @return a reference to the parent node of the specified node
    */
   private Node findParent(Node node)
   {
      Node tmp = root;
      if (tmp == node)
         return null;
      while(true)
      {
         assert tmp.data.compareTo(node.data) != 0;
         if (tmp.data.compareTo(node.data)>0)
         {
            /* this assert is not needed but just
               in case there is a bug         */
            assert tmp.left != null;
            if (tmp.left == node)
               return tmp;
            tmp = tmp.left;
         }
         else
         {
            assert tmp.right != null;
            if (tmp.right == node)
               return tmp;
            tmp = tmp.right;
         }
      }
   }

   /********************* Method Begins Here **********************/

   /**
    * 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)
   {
       if(subtreeRoot == null) 
           return 0;
       if(subtreeRoot.left != null) 
       {
           if(subtreeRoot.right != null) 
           {
               return (Integer)subtreeRoot.data + sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
           }
           else
               return (Integer)subtreeRoot.data + sigma(subtreeRoot.left);
       }
       if(subtreeRoot.right != null)
           return sigma(subtreeRoot.right) - (Integer)subtreeRoot.data;

       return (Integer)subtreeRoot.data;
   }

   /********************* Method Ends Here **********************/

   /**
    * Determines whether this binary tree is perfect
    * @return true if the binary tree is perfect, otherwise false
    */
   @Override
   public boolean isPerfect()
   {

   }

   /**
    * A wrapper method that computes the height of this tree
    * @return the height of this tree
    */
   @Override
   public int height()
   {
       return height(root);
   }

   /**
    * An auxiliary method that recursively computes 
    * the height of the subtree rooted at the specified node.
    * @param node a root of a subtree
    * @return the height of this tree
    */
   private int height(Node node)
   {
       if(node == null)
           return 0;
       return 1 + Math.max(height(node.left), height(node.right));
   }   

   /**
    * Determines whether this binary tree is complete.
    * @return true if this binary tree is complete, otherwise false
    */
   @Override
   public boolean isComplete()
   {

   }

   /**
    * An auxiliary method that recursively determines whether 
    * the index of the subtree rooted at the specified node is
    * less than the size of this tree.
    * @param node a root of a subtree
    * @param index the index of this node
    * @return 
    */
   private boolean isComplete(Node node, int index)
   {

   }
}

包装器方法 return 将根节点的数据转换为 Integer，添加到由对根节点执行的辅助方法编辑的值 return。

我认为有三种情况需要说明：

if(subtreeRoot == null)
if(subtreeRoot.left != null && subtreeRoot.right != null) // Parent node has left and right child nodes
if(subtreeRoot.left != null || subtreeRoot.right != null) // Parent node has only left or right child node

这是我卡住的地方，情况 2 和 3。我知道目标是从 [= 的值中减去左 and/or 右 child 的值52=] 节点找到该子树的差分键的值，然后向下递归左 and/or 右剩余子树执行相同的操作并将结果相加。但我不知道从这里去哪里。我们不允许将 parameters/arguments 添加到项目的方法中，因此 (Node subtreeRoot) 是辅助方法唯一允许的参数，包装方法不带参数。创建一个 Function<> 来简化问题是否有用，我的逻辑是否有缺陷等等？感谢任何帮助或进一步的解释，因为此时我有点迷茫，我的教授也没有帮助。

Answer 1

正如 MrMcGreg 已经指出的那样，您正在使主要逻辑变得复杂。

Base case：如果传入的树为NULL，return 0
递归：return求和
- 节点值减parent节点值
- 西格玛（左child）
- 西格玛（右child）

由于节点没有 link 到其 parent，您的递归函数需要将 parent 的值传递到例程中。您将获得从此 pseudo-code:

派生的代码

int sigma_aux (node root, int parent_val) {
    if !node
        return 0
    else
        root_val = root->data
        return root_val - parent_val +
               sigma_aux(root->left , root_val) +
               sigma_aux(root->right, root_val)

就是它；只是一个基本案例和一个递归案例。用铅笔和纸描绘它，直到您理解它——然后在您的代码上下文中实现它。

OP 写道：

... something like
return (Integer) subtreeRoot.data - (Integer) root.data + 
    sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
? I don't understand how to get the value of the parent node. I thought the parent node was the subtreeRoot node passed into the auxiliary method and it's children were subtreeRoot.left and subtreeRoot.right

你控制传入辅助方法的内容；不要把你的第一个概念当作给定的。这就是你感到困惑的地方。简化一下：top-level sigma 的唯一真正目的是将树根的数据传递给 sigma_aux，并且对外界进行 top-most 计算 return。

int sigma（节点根）{ root_val = root->data;

在这之后，它看起来就像 sigma_aux。

Answer 2

你一定是我class中的某个人...无论如何，你必须使用findParent方法，因为你没有通过parent sigma 方法中的节点。

 private int sigma(Node subtreeRoot) {
    int tot = 0;
    if (subtreeRoot == null) {
        return 0;
    }
    if (findParent(subtreeRoot) == null) {
        tot = sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
    } else{
        tot = (Integer) subtreeRoot.data - (Integer) findParent(subtreeRoot).data
                + sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
    }
    return tot;
}

使用 findParent 方法的 if-statement 是因为该方法将 return null 由于 subtreeRoot 是树的根，因此，它没有 parent。然后，当您为左右 children 调用 sigma 方法时，它们将继续执行 else-statement。

我卡在了 isPerfect 方法上。如果我创建一个辅助方法并使用递归，我可以做到这一点，但我们不应该那样做...

差分键的二叉搜索树和

Binary Search Tree Sum of Differential Keys

java

recursion

binary-tree

binary-search-tree

data-structures