a BohYoh.com【著書】Javaによるアルゴリズムとデータ構造《演習問題10-2の解答》

Javaによるアルゴリズムとデータ構造

演習10-2の解答

　最小のキー値を返すメソッド、最小のキー値をもつノードのデータを返すメソッド、最大のキー値を返すメソッド、最大のキー値をもつノードのデータを返すメソッドを作成せよ。木が空である場合はnullを返すこと。

K getMinKey ()	// 最小のキー値を返す
V getDataWithMinKey ()	// 最小のキー値をもつノードのデータを返す
K getMaxKey ()	// 最大のキー値を返す
V getDataWithMaxKey ()	// 最大のキー値をもつノードのデータを返す

  // 最小のキー値をもつノードを返す
  private Node<K,V> getMinNode() {
    if (root == null)
      return null;
    else {
      Node<K,V> p = root;            // 根に着目

      while (p.left != null)
        p = p.left;
      return p;
    }
  }

  // 最大のキー値をもつノードを返す
  private Node<K,V> getMaxNode() {
    if (root == null)
      return null;
    else {
      Node<K,V> p = root;            // 根に着目

      while (p.right != null)
        p = p.right;
      return p;
    }
  }

  // 最小のキー値を返す
  K getMinKey() {
    Node<K,V> minNode = getMinNode();
    return (minNode == null ? null : minNode.getKey());
  }

  // 最小のキー値をもつノードのデータを返す
  V getDataWithMinKey() {
    Node<K,V> minNode = getMinNode();
    return (minNode == null ? null : minNode.getValue());
  }

  // 最大のキー値を返す
  K getMaxKey() {
    Node<K,V> maxNode = getMaxNode();
    return (maxNode == null ? null : maxNode.getKey());
  }

  // 最大のキー値をもつノードのデータを返す
  V getDataWithMaxKey() {
    Node<K,V> maxNode = getMinNode();
    return (maxNode == null ? null : maxNode.getValue());
  }

戻る