Проверка узла дерева равным значению

Я пытаюсь написать рекурсивную функцию для произвольного двоичного дерева, которое принимает значение и листовой узел, и проверяет, имеет ли этот листовой узел это значение. Это примерно то, что у меня есть сейчас.Проверка узла дерева равным значению

bool tree_eq(value, N* node){ 
    if (node == nullptr){ 
    return false; 
    } 
    else{ 
    if node->value == value{ 
     return true; 
    } 
    else{ 
     return tree_eq(value, N->left); 
     return tree_eq(value, N->right); 
    }

Я знаю, что не могу вернуть две вещи, и это та часть, которую я пытаюсь решить. Как я рекурсивно проверяю правую и левую стороны, если задан корень, а не лист? Спасибо

источник

2015-02-03 Steven

Вы должны знать, если узел находится либо в левой или с правой стороны (на самом деле не имеет значения, в сторону), так что вы можете сказать:

... 
else { 
    return (tree_eq(value,N->left) || tree_eq(value,N->right)); 
}

Это приведет к поиск глубины, где всегда учитывается левая часть ветвей узлов.

источник

2015-02-03 22:31:37 MichaelCMS

Что делать, если данный узел является корнем, поэтому мне нужно идти влево и вправо? – Steven

Вы всегда будете идти влево и вправо, пока не найдете значение. Однако, если что-то возвращает true, все работает нормально. – MichaelCMS

Я не вижу, как || что обе стороны проверяются. Если я начинаю с корня, а его 2 листа не равен значению, он будет случайным образом проверять правильное или левое, но не то и другое. Это то, что я получаю от || – Steven

Когда дерево Unsorted, измените окончание еще пункт от

return tree_eq(value, N->left); 
return tree_eq(value, N->right);

и попытаться «или» эти два результата, как в

return (tree_eq(value, N->left) || 
     tree_eq(value, N->right));

Если дерево сортируется, вам нужно только dfs с одной стороны или другой, а не с обеих сторон.

Обратите внимание, что '||' не будет вызывать правильную ветвь, если она найдена в левой ветви.

источник

2015-02-03 22:33:45

Проверка узла дерева равным значению

ответ

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