0

这是一个家庭作业问题，所以我真正想要的是一个基本的递归算法。我正在研究 AATree 的地板/天花板方法。我当前的树有这样的结构：

        40
  20        60
10  30    50    80
              70  90
                    100

（等级顺序）。我的 floor 方法有一个迭代解决方案：

 /**
   * Returns the greatest element in the set <= the_target.
   * Strings are compared by ASCII values.
   * 
   * @param the_target Element to compare set values with.
   * @return Greatest element <= the_target, null if no such element exists.
   */
  public E floor(final E the_target) {
    AANode<E> current_node = my_root;
    E result = null;
    int root_value = compare(current_node.my_element, the_target);
    while (true) {
      if (root_value == 0) {
        if (current_node.my_left.equals(my_null_node) 
            && current_node.my_right.equals(my_null_node)) {
          break;
        }
        result = current_node.my_element;
        break;
      }
      if (contains(the_target)) {
        result = the_target;
        break;
      } else if (root_value > 0) { 
        if (current_node.my_left.my_element == null) {
          break;
        }
        current_node = current_node.my_left;
        root_value = compare(current_node.my_element, the_target);
      } else {
        if (current_node.my_right.my_element == null) {
          result = current_node.my_element;
          break;
        }
        result = current_node.my_element; 
        current_node = current_node.my_right;  
        root_value = compare(current_node.my_element, the_target);
      }
    }
    return result;
  }

但我想让我的 ceiling() 方法递归。它必须具有此方法签名：

  /**
   * Returns the smallest element in the set >= the_target.
   * 
   * @param the_target Element to compare set values with.
   * @return Smallest element >= the_target, null if no such element exists.
   */
  public E ceiling(final E the_target);

我将使用返回 E 的辅助递归方法来实现这一点。我试图让我的逻辑正确，并希望得到一些算法建议。

感谢大家的帮助！我知道了。

 /**
   * Helper recursive method for ceiling().
   * 
   * @param the_root The current node.
   * @param the_smallest The previous smallest element.
   * @param the_target The target for ceiling.
   * @return The ceiling element of the tree.
   */
  private E findCeiling(final AANode<E> the_root, final AANode<E> the_smallest,
                        final E the_target) {
    AANode<E> small = the_smallest;
    if (compare(the_target, small.my_element) > 0) {
      small = the_root;
    }
    // base case
    if (the_root.my_left.my_element == null 
        && the_root.my_right.my_element == null) {
      return small.my_element;
    } else {
      if (compare(the_target, the_root.my_element) > 0) {
        if (compare(the_smallest.my_element, the_root.my_element) > 0) {
          small = the_root;
        }
        return findCeiling(the_root.my_right, small, the_target);
      } else {
        if (compare(the_smallest.my_element, the_root.my_element) > 0) {
          small = the_root;
        }
        return findCeiling(the_root.my_left, small, the_target);
      }
    }
  }
4

2 回答 2

1

您想遍历树并跟踪迄今为止看到的集合中小于目标的最小值。让我们调用这个值SGT

您的辅助例程需要接受正在检查的当前节点和当前SGT值。

这里有一个提示，让你开始......

 public E ceiling(final E target) { 
     return ceilingHelper(root, root.my_element, target);
 }

 private E ceilingHelper(final AANode<E> current_node, 
                         final E SGT, 
                         final E target) { 
    //now do you get the idea ?  your recursion will need a base case
    //and a recursive step.  you can traverse the tree using a depth first
    //search
 }
于 2013-03-01T19:34:42.520 回答
0

我认为提供确切的解决方案并不合适，但您应该查看http://en.wikipedia.org/wiki/Tree_traversal。您需要递归执行此操作的所有通用算法。

通常，递归解决方案涉及将问题定义为子问题。作为提示，两个相邻子树的 ceils 是如何相关的？还要考虑递归结束的基本情况。叶节点的ceil是什么？

树问题的递归解决方案可以非常简洁和简单。

于 2013-03-01T19:11:12.633 回答