0

これは宿題の質問なので、基本的な再帰アルゴリズムが私が本当に求めているすべてです。私はAATreeの床/天井の方法に取り組んでいます。私の現在のツリーは次の構造になっています。

        40
  20        60
10  30    50    80
              70  90
                    100

（レベル順）。フロアメソッドの反復ソリューションがあります。

 /**
   * 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を参照してください。これを再帰的に実行するために必要なすべての一般的なアルゴリズムがあります。

一般に、再帰的な解決策には、問題をサブ問題として定義することが含まれます。ヒントとして、2つの隣接するサブツリーのセルはどのように関連していますか？また、再帰が終了するベースケースがどうなるかについても考えてください。リーフノードの天井とは何ですか？

ツリーの問題の再帰的な解決策は、非常に簡潔で単純な場合があります。

于 2013-03-01T19:11:12.633 に答える