Блог

Главная - Вопросы по программированию - Обход в древовидной структуре данных (по порядку) не работает в Java

Обход в древовидной структуре данных (по порядку) не работает в Java

#java #algorithm #data-structures #tree #binary-search-tree

#java #алгоритм #структуры данных #дерево #двоичное дерево поиска

Вопрос:

Я новичок в структуре данных, и в настоящее время я пишу метод обхода древовидной структуры данных. Прямо сейчас, когда я выполняю обход по порядку, он должен переходить от меньшего к наибольшему значению. Но, похоже, мой метод не соответствует последовательности. Могу ли я узнать, в чем здесь проблема? Вот фрагмент кода:

     int[] intArr = { 100, 20 ,140, 55, 19, 22, 89, 200, 120 };

    for( int i = 0; i < intArr.length; i   )
    {
        key  = intArr[i];
        tree.insert(key, intArr[i]); // Key is the same as data in this case
        key = "";
    }

    String str = tree.inOrderTraverse();
    System.out.println(str);

Вывод должен выглядеть следующим образом: 19 20 22 55 89 100 120 140 200
Но это фактический результат: 100 120 140 19 20 200 22 55 89

Вот мой рекурсивный метод и метод оболочки:

 // SUBMODULE: inOrderTraverse (Wrapper Method)
// IMPORT: none
// EXPORT: (String)
public String inOrderTraverse()
{
    return inOrderRec( root, "" );
}

// SUBMODULE: inOrderRec
// IMPORT: currNd (DSATreeNode), str (String)
// EXPORT: str (String)
private String inOrderRec( DSATreeNode currNd, String str )
{
    if( currNd != null )
    {
        str = inOrderRec( currNd.left, str );
        str  = currNd.data   " ";
        str = inOrderRec( currNd.right, str );
    }
    return str;
}

Это моя вставка и ее оболочки

 // SUBMODULE: insert (Wrapper)
// IMPORT: key (String), data (Object)
// EXPORT: none
public void insert( String key, Object data )
{
    try { root = insertRec( root, key, data ); } // Now root has the address of all the trees 
    catch(IllegalArgumentException e) { System.out.println(e.getMessage()); }
} 

// SUBMODULE: insertRec
// IMPORT: currNd (DSATreeNode), key (String), data (Object)
// EXPORT: updateNd (DSATreeNode)
// ASSERTION: Create the new tree node 
private DSATreeNode insertRec( DSATreeNode currNd, String key, Object data )
{
    DSATreeNode updateNd;
    updateNd = currNd;
    if( currNd == null )
    {
        currNd = new DSATreeNode( key, data );
        updateNd = currNd;
    }
    else if( key.equals(currNd.key) )
        throw new IllegalArgumentException( "Existing key provided" );      // Key must be unique

    else if( key.compareTo(currNd.key) < 0 )
        currNd.left = insertRec( currNd.left, key, data );                  // Recursive to left

    else
        currNd.right = insertRec( currNd.right, key, data );                // Recursive to right

    return updateNd;
}

Комментарии:

1. Не видя вашей insert функции, я не могу быть уверен, что ваше дерево строится правильно, для начала. В качестве первого шага я бы проверил, соответствует ли структура вашего дерева тому, что вы ожидаете. Это должно быть binary tree или binary *search* tree ?

2. ПРИВЕТ, я добавил функцию вставки, и я делаю для двоичного дерева поиска

Ответ №1:

Ваши ключи на самом деле являются строками. Поэтому вы получите лексикографический порядок вставленных вами ключей. Вот почему результат — это то, что вы видите. 100 120 140 19 20 200 22 55 89 — это правильный лексикографический порядок!

Не используйте string в качестве типов данных для ключей. Используйте integer, если ваши элементы являются целыми числами.

Или попробуйте преобразовать ключи в целые числа из строк перед сравнением, например: Integer.valueOf(key).compareTo(Integer.valueOf(currNd.key)) в вашем методе insert.

Но это дополнительная работа и подвержена исключениям, если вы не уверены, что ключи всегда представляют целые числа.