2013-12-15 5 views
-2

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

Так, по существу, установить на этот вопрос будет (я думаю):

общественного узла искатель (корневой узел, Int макс, внутр мин) {};

+1

«вот код, который у меня есть до сих пор, и здесь я застреваю», как правило, это должно произойти. Прямо сейчас ваш ход мысли еще не покинул станцию ​​... – Floris

+0

Я думал, что просто выполнил бы оператор if, чтобы проверить, не осталось ли и левое, и правое дочернее устройство, если так возвращать null (по существу ничего не делая), то оттуда есть 2 заявления. 1-й оператор if: проверьте, находится ли левый дочерний элемент, если он посещает его, и рекурсивно вызывать программу снова с помощью левого дочернего элемента. 2-й оператор if: выполните то же самое, что и первое, за исключением использования правильного дочернего элемента. Кроме того, я знаю, что моя логика не завершена, и я пропустил шаги – user2251001

ответ

0

Создайте функцию «проверки», которая рекурсивно определяется как

check(Node x){ 
    if(x.right.elm()>min&&x.right.elm()<max){ 
     check(x.right); 
    } 
    else if(x.right.elm()>max){ 
     check(x.right.left);  
    else if(x.right.elm()<min){ 
     check(x.right.right); 
    } 
    if(x.left.elm()>min&&x.left.elm()<max){ 
     check(x.left); 
    } 
    else if(x.left.elm()>max){ 
     check(x.left.left);  
    else if(x.left.elm()<min){ 
     check(x.left.right); 
    } 
    } 

В качестве альтернативы для упрощения кода вы можете создать две функции check_right и check_left.

Смежные вопросы