5

事前注文パス情報を含むツリーの複数行表現を返すバイナリ検索ツリーの再帰文字列メソッドを作成しようとしています。

各ノードの前には、ルートからそのノードに至るパスを示す一連の<および>文字を付ける必要があります。連続して呼び出すたびに1文字ずつ拡張される文字列プレフィックスパラメータを使用する方法がわかりません。

メソッドは、この例を再現できる必要があります。

木:

     15
    /  \
   12  18
  /   /  \
 10  16  20
   \   \
   11  17

期待される印刷出力:

15
<12
<<10
<<>11
>18
><16
><>17
>>20

私は再帰に不慣れで、これまでのところ、コードを何時間もいじった後、実際の印刷出力は十分に閉じていません。

18
<17
<10
>15
<11
>12
16
20

正しく機能するツリーノードクラスは次のとおりです。

/**
 * A single binary tree node.
 * <p>
 * Each node has both a left or right child, which can be null.
 */
public class TreeNode<E> {

  private E data;
  private TreeNode<E> left;
  private TreeNode<E> right;

  /**
   * Constructs a new node with the given data and references to the
   * given left and right nodes.
   */
  public TreeNode(E data, TreeNode<E> left, TreeNode<E> right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  /**
   * Constructs a new node containing the given data.
   * Its left and right references will be set to null.
   */
  public TreeNode(E data) {
    this(data, null, null);
  }

  /** Returns the item currently stored in this node. */
  public E getData() {
    return data;
  }

  /** Overwrites the item stored in this Node with the given data item. */
  public void setData(E data) {
    this.data = data;
  }

  /**
   * Returns this Node's left child.
   * If there is no left left, returns null.
   */
  public TreeNode<E> getLeft() {
    return left;
  }

  /** Causes this Node to point to the given left child Node. */
  public void setLeft(TreeNode<E> left) {
    this.left = left;
  }

  /**
   * Returns this nodes right child.
   * If there is no right child, returns null.
   */
  public TreeNode<E> getRight() {
    return right;
  }

  /** Causes this Node to point to the given right child Node. */
  public void setRight(TreeNode<E> right) {
    this.right = right;
  }
}

下部にtoFullString()メソッドを使用したバイナリ検索ツリークラスは次のとおりです。

import java.util.*;

/**
 * A binary search tree (BST) is a sorted ADT that uses a binary
 * tree to keep all elements in sorted order.  If the tree is
 * balanced, performance is very good: O(n lg n) for most operations.
 * If unbalanced, it performs more like a linked list: O(n).
 */
public class BinarySearchTree<E extends Comparable<E>> {

  private TreeNode<E> root = null;
  private int size = 0;

  /** Creates an empty tree. */
  public BinarySearchTree() {
  }


    public BinarySearchTree(Collection<E> col) {
        List<E> list = new ArrayList<E>(col);
        Collections.shuffle(list);
        for (int i = 0; i < list.size() ; i++) {
            add(list.get(i));
        }
    }


  /** Adds the given item to this BST. */
  public void add(E item) {
    this.size++;
    if (this.root == null) {
      //tree is empty, so just add item
      this.root = new TreeNode<E>(item);
    }else {
      //find where to insert, with pointer to parent node
      TreeNode<E> parent = null;
      TreeNode<E> curr = this.root;
      boolean wentLeft = true;
      while (curr != null) {  //will execute at least once
        parent = curr;
        if (item.compareTo(curr.getData()) <= 0) {
          curr = curr.getLeft();
          wentLeft = true;
        }else {
          curr = curr.getRight();
          wentLeft = false;
        }
      }

      //now add new node on appropriate side of parent
      curr = new TreeNode<E>(item);
      if (wentLeft) {
        parent.setLeft(curr);
      }else {
        parent.setRight(curr);
      }
    }
  }

  /** Returns the greatest (earliest right-most node) of the given tree. */
  private E findMax(TreeNode<E> n) {
    if (n == null) {
      return null;
    }else if (n.getRight() == null) {
      //can't go right any more, so this is max value
      return n.getData();
    }else {
      return findMax(n.getRight());
    }
  }

  /**
   * Returns item from tree that is equivalent (according to compareTo)
   * to the given item.  If item is not in tree, returns null.
   */
  public E get(E item) {
    return get(item, this.root);
  }

  /** Finds it in the subtree rooted at the given node. */
  private E get(E item, TreeNode<E> node) {
    if (node == null) {
      return null;
    }else if (item.compareTo(node.getData()) < 0) {
      return get(item, node.getLeft());
    }else if (item.compareTo(node.getData()) > 0) {
      return get(item, node.getRight());
    }else {
      //found it!
      return node.getData();
    }
  }

  /**
   * Removes the first equivalent item found in the tree.
   * If item does not exist to be removed, throws IllegalArgumentException().
   */
  public void remove(E item) {
    this.root = remove(item, this.root);
  }

  private TreeNode<E> remove(E item, TreeNode<E> node) {
    if (node == null) {
      //didn't find item
      throw new IllegalArgumentException(item + " not found in tree.");
    }else if (item.compareTo(node.getData()) < 0) {
      //go to left, saving resulting changes made to left tree
      node.setLeft(remove(item, node.getLeft()));
      return node;
    }else if (item.compareTo(node.getData()) > 0) {
      //go to right, saving any resulting changes
      node.setRight(remove(item, node.getRight()));
      return node;
    }else {
      //found node to be removed!
      if (node.getLeft() == null && node.getRight() == null) {
        //leaf node
        return null;
      }else if (node.getRight() == null) {
        //has only a left child
        return node.getLeft();
      }else if (node.getLeft() == null) {
        //has only a right child
        return node.getRight();
      }else {
        //two children, so replace the contents of this node with max of left tree
        E max = findMax(node.getLeft());  //get max value
        node.setLeft(remove(max, node.getLeft())); //and remove its node from tree
        node.setData(max);
        return node;
      }
    }
  }

  /** Returns the number of elements currently in this BST. */
  public int size() {
    return this.size;
  }

  /**
   * Returns a single-line representation of this BST's contents.
   * Specifically, this is a comma-separated list of all elements in their
   * natural Comparable ordering.  The list is surrounded by [] characters.
   */
  @Override
  public String toString() {
    return "[" + toString(this.root) + "]";
  }

  private String toString(TreeNode<E> n) {
    //would have been simpler to use Iterator... but not implemented yet.
    if (n == null) {
      return "";
    }else {
      String str = "";
      str += toString(n.getLeft());
      if (!str.isEmpty()) {
        str += ", ";
      }
      str += n.getData();
      if (n.getRight() != null) {
        str += ", ";
        str += toString(n.getRight());
      }
      return str;
    }
  }

    public String toFullString() {
        StringBuilder sb = new StringBuilder();
        toFullString(root, sb);
        return sb.toString();
    }

  /**
   * Preorder traversal of the tree that builds a string representation
   * in the given StringBuilder.
   * @param n root of subtree to be traversed
   * @param sb StringBuilder in which to create a string representation
   */
  private void toFullString(TreeNode<E> n, StringBuilder sb)
  {

    if (n == null)
    {
      return;
    }



sb.append(n.getData().toString());
    sb.append("\n");


        if (n.getLeft() != null) {
        sb.append("<");
    } else if (n.getRight() != null) {
        sb.append(">");
    }

    if (n.getLeft() != null || n.getRight() != null)
    {
      toFullString(n.getLeft(), sb);   
      toFullString(n.getRight(), sb);
    }
  }


  /**
   * Tests the BST.
   */  
    public static void main(String[] args) {
    Collection collection = new ArrayList();
    collection.add(15);
    collection.add(12);
    collection.add(18);
    collection.add(10);
    collection.add(16);
    collection.add(20);
    collection.add(11);
    collection.add(17);
    BinarySearchTree bst = new BinarySearchTree(collection);
    //System.out.println(bst);      
    String temp = bst.toFullString();
    System.out.println(temp);
    }
}

再帰的なtoFullStringメソッドに関するヘルプは大歓迎です。

4

1 に答える 1

3

再帰的ソリューションを設計するときに考慮する必要がある2つのレベルがあります。

  1. 再帰内の現在のアイテムをどのように処理しますか?
  2. このアイテムから次のアイテムに移動するにはどうすればよいですか?また、どのような情報が渡されますか?

ツリー内の各アイテムを印刷しているので、各再帰呼び出し内に1つのprintステートメントがあります。ただし、各行に出力される文字列には、現在のノードに到達するためにトラバースされた前のステップに関する情報が含まれています。この情報をどのように処理しますか?前の再帰呼び出しから次の呼び出しに渡す必要があります。

可能なルールのセットは次のとおりです。

  1. 現在のアイテムがリーフの場合は、現在の結果を印刷します。
  2. 現在のアイテムに左側のノードがある場合は、を追加<し、左側のノードに再帰的に作用します。
  3. 現在のアイテムに適切なノードがある場合は、を追加>し、適切なノードに対して再帰的に動作します。

何を追加<>ますか?再帰呼び出しから呼び出しへの再帰で発生した現在の前のステップを実行するためのパラメーターが必要です。すべての単一ノードにプレフィックスを印刷するための現在の一連の手順を覚えておく必要があるため、単純に印刷し<てツリーをトラバースする必要はありません。>元のパラメーターと同じパラメーターを使用する2番目のヘルパーメソッドがありますがtoFullString()、前のステップの現在のセットを実行するためのカスタムの3番目のパラメーターがあります。

したがって、ロジックは次のようになります。

  • ""現在のプレフィックスがない場合は、ルートに到達するためのステップが最初はないため、プレフィックスをに初期化します。
  • 現在のノードがリーフの場合は、現在のプレフィックス+リーフ値を使用して出力行を追加します。
  • 現在のノードに左側のノードがある場合は、左側のノードを再帰的に呼び出し、現在のプレフィックス文字列にtoFullString()追加<します。これは受け継がれます。
  • 現在のノードに右側のノードがある場合は、右側のノードを再帰的に呼び出し、現在のプレフィックス文字列にtoFullString()追加>します。これは受け継がれます。
于 2012-11-17T22:49:15.867 に答える