Поиск в режиме обхода предварительного заказа

У меня есть бинарное дерево поиска. Я знаю, как искать, используя свойство поиска. Но моя задача - искать дерево без использования свойства поиска (скажем, поиск в двоичном дереве). Вот как я должен искать.

1. Если вы найдете значение в текущем узле, верните его.

2. иначе ищите справа. Если не найдено справа, то ищите слева

3. Если не найдено во всем дереве, верните ноль.

Это то, что я пробовал.

public Node search(int val)
{
    Node target = this;
    if(target.getVal() == val)
        return this;
    else if(target.getRight() == null && target.getLeft() == null)
        return null;
    if(target.getRight() != null)
    {
        return target.getRight().search(id);
    }
    if(target.getLeft() != null)
    {
        return target.getLeft().search(id);
    }
    return null;
}

Проблема с моим кодом в том, что если правильный дочерний элемент существует, а val не найден, я получаю значение null. (Не ищет слева). Как это решить?


java search binary-tree tree-traversal preorder
person sanjay Kumar    schedule 02.12.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward 

public Node search(int val)
{
    Node target = this;
    if(target.getVal() == val)
        return this;
    else if(target.getRight() == null && target.getLeft() == null)
        return null;
    if(target.getRight() != null)
    {
        return target.getRight().search(id); //here lies the problem
    }
    if(target.getLeft() != null)
    {
        return target.getLeft().search(id);
   }
return null;

}

Проблема в вашем коде заключается в том, что вы возвращаете результат поиска в правом поддереве искомого узла.

Вот обновленный код

public Node search(int val)
{
    Node target = null;
    if(this.getVal() == val)
    {
        return this;
    }
    else if(this.getRight() == null && this.getLeft() == null)
        return target;
    if(this.getRight() != null)
    {
        target = this.getRight().search(id);
    }
    if(target==null && this.getLeft() != null)
    {
        target = this.getLeft().search(id);
   }
   return target;

}

person iotaSingh    schedule 02.12.2014

arrow_upward
0
arrow_downward

Это непроверенный код, но я бы немного изменил вашу логику:

public Node search(int val)
{
    if(this.getVal() == val)
        return this;

    if (this.getRight() != null) {
        Node right = this.getRight().search(id);
        if (right != null)
            return right;
    }

    if (this.getLeft() != null) {
        Node left = this.getLeft().search(id);
        if (left != null)
            return left;
    }

    return null;
}

В вашей версии вы возвращаете решение с единственным требованием, чтобы узел справа или слева не был нулевым. Вы должны вернуть решение, только если решение найдено.

person Olavi Mustanoja    schedule 02.12.2014