VPF::Двоичное дерево поиска в Яве - Форум программистов

Widunder

Дата 31.8.2008, 06:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 31.8.2008

Репутация: нет
Всего: нет

Помогите пожалуйста. Я по Интернету поискала как работать с двоичным деревом поиска в Яве и просто так, поняла чего это такое, но свою задачу так и не смогла решить.
Задача заключается в том, что надо создать узел с ключём K и значением V (инпут параметры) и этот узел добавить в двоичное дерево поиска.
А ещё пытаюсь написать, чтобы находила программа узел с минимальным значением, но похоже та версия программы, на которой я умела это делать совсем другая от той, которой пользуюсь сейчас и уже не знаю как так сделать, чтобы находила меньшее значение ключа. Потому что как я делала это раньше в этой версии не работает. Версия, которой пользуюсь самый последний toolkit 6-ой.
Пожалуйста подскажите как быть.
Заранее благодарю.

Dwyane

Дата 31.8.2008, 08:22 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 8.5.2007

Репутация: нет
Всего: 1

Код


public class BinaryTree {
  // Root node pointer. Will be null for an empty tree.
  private Node root;
 

  /*
   --Node--
   The binary tree is built using this nested node class.
   Each node stores one data element, and has left and right
   sub-tree pointer which may be null.
   The node is a "dumb" nested class -- we just use it for
   storage; it does not have any methods.
  */
  private static class Node {
    Node left;
    Node right;
    int data;

    Node(int newData) {
      left = null;
      right = null;
      data = newData;
    }
  }

  /**
   Creates an empty binary tree -- a null root pointer.
  */
  public void BinaryTree() {
    root = null;
  }
 

  /**
   Returns true if the given target is in the binary tree.
   Uses a recursive helper.
  */
  public boolean lookup(int data) {
    return(lookup(root, data));
  }
 

  /**
   Recursive lookup  -- given a node, recur
   down searching for the given data.
  */
  private boolean lookup(Node node, int data) {
    if (node==null) {
      return(false);
    }

    if (data==node.data) {
      return(true);
    }
    else if (data<node.data) {
      return(lookup(node.left, data));
    }
    else {
      return(lookup(node.right, data));
    }
  }
 

  /**
   Inserts the given data into the binary tree.
   Uses a recursive helper.
  */
  public void insert(int data) {
    root = insert(root, data);
  }
 

  /**
   Recursive insert -- given a node pointer, recur down and
   insert the given data into the tree. Returns the new
   node pointer (the standard way to communicate
   a changed pointer back to the caller).
  */
  private Node insert(Node node, int data) {
    if (node==null) {
      node = new Node(data);
    }
    else {
      if (data <= node.data) {
        node.left = insert(node.left, data);
      }
      else {
        node.right = insert(node.right, data);
      }
    }

    return(node); // in any case, return the new pointer to the caller
  }

Это сообщение отредактировал(а) powerOn - 1.9.2008, 10:47

Widunder

Дата 1.9.2008, 02:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 31.8.2008

Репутация: нет
Всего: нет

благодарю за ответ, но вот так и непонимаю как же сделать K и V инпут параметрами smile

SoulKeeper

Дата 1.9.2008, 08:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 375
Регистрация: 14.1.2007
Где: Ukraine, Lviv.

Репутация: 11
Всего: 15

Код


public class Something<K,V>{

public void put(K key, V value){
...
}
...
}

Joss

Дата 1.9.2008, 08:49 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 19.3.2006

Репутация: нет
Всего: 1

Имеется ввиду, что тип ключа должен быть К, а тип значения - V?

Widunder

Дата 1.9.2008, 11:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 31.8.2008

Репутация: нет
Всего: нет

да, это и имеется ввиду

fixxer

Дата 1.9.2008, 13:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 672
Регистрация: 14.9.2006
Где: Саратов, Россия

Репутация: 6
Всего: 27

посмотрите java.util.TreeMap. Сделан на основе красно-черных деревьев.

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »