Найти узел N в дереве

Question

У меня проблемы с кодированием на Java следующим методом

int findNodeN (Узел узла, int n)

Например, если дерево двоичного поиска построено следующим образом:

        20
   10       30    
 1   14   25   35

Тогда узел 1 будет возвращен, если n = 0, узел 10 будет возвращен, если n = 1 и т. Д. (Т. Е. Обход inOrder)

Ценю любую помощь

Answer 1

Самая простая реализация - установить нулевую переменную счетчика.Прогулка по дереву в обычном порядке.Когда вы идете к правому ребенку - увеличьте счетчик, когда вы идете к родителю и у вас был левый ребенок - увеличьте счетчик.Когда счетчик станет равным N, верните текущую вершину.

Answer 2

Вот версия, которая у меня есть, она немного отличается от того, что вам нужно, но есть над чем поработать:

public E findElement(E element)
{
    TreeNode<E> current = root;

    while (current != null)
    {
        if ( element.compareTo(current.getElement() ) == 0)   //If found
        {
            return current.getElement();
        } 
        else if( element.compareTo(current.getElement() ) < 0)    //If element is less
        {
            current = current.getLeftChild();               //Try the left child
        } 
        else                                                //If element is greater
        {
            current = current.getRightChild();             //Try the right child
        }
    }

//not found
return null;

}

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

РЕДАКТИРОВАТЬ: ОК, попробуйте что-то вроде этого:

public int findNodeN(Node node, int n, int callNumber) //Call initially with findNodeN(tree.getRoot(), n, 0)
{
    if (node.hasLeft())
        findNodeN(node.getLeftChild(), n, callNumber);
    if (callNumber == n)                     
         return node.getElement();
    else
         callNumber++;
    if (node.hasRight())
        printTreeInOrder(node.getRightChild(), n, callNumber);

}

Это не проверено.Calum