Обзор кода: Как я могу упростить этот простой метод?

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

bool Node::lookup(int d) 
{ 
    if (data==d) 
    { 
     return true; 
    } 
    else 
    { 
     if (left != NULL && right != NULL) 
     { 
      return left->lookup(d) && right->lookup(d); 
     } 
     else if (left != NULL) 
     { 
      return left->lookup(d); 
     } 
     else if (right != NULL) 
     { 
      return right->lookup(d); 
     } 
     else 
     { 
      return false; 
     } 
    } 
}

источник

2010-10-29 btree

Вы уверены, что хотите, чтобы значение находилось в * обоих * поддеревах? –

Хороший звонок ... Спасибо за это. – btree

bool Node::lookup(int d) 
{ 
    return (data==d) 
     || ((NULL != left) && left->lookup(d)) 
     || ((NULL != right) && right->lookup(d)); 
}

принимает преимущество поведения короткого замыкания и &&||.

Обратите внимание, что это не совсем эквивалентно вашему коду, но я полагаю, что это, вероятно, поведение, которое вы действительно хотите. (Ваш исходный код возвращает false, оба ребенка существуют, и d не находится в обоих из них.)

источник

2010-10-29 22:27:04

Это определенно то, о чем я думал. Благодаря! – btree

На самом деле, я не уверен, что это правильно. Держись ... –

Думаю, теперь это исправлено. –

-4

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

bool Node::lookup(int d){ 
    if (!this) // a little bit unorthodox, but much more elegant that testing before call 
     return false; 
    return (data == d) || left->lookup(d) || right->lookup(d); 
}

EDIT: Кажется, кому не нравится такой подход. Но почему? для случая виртуальных функций Кроме этого обеспечивает лучшую герметизацию, чем стандартный:

Node* tree; 
if (tree->lookup(i)) // we encapsulate in the Node class the information that an empty tree must return false 
    printf("found!\n"); 

Node* tree; 
if (tree && tree->lookup(i)) // we have to know in the outside that a NULL tree shall return false 
    printf("found!\n");

Единственный способ это может произвести UB, когда компилятор будет считать, что this не может быть NULL, и пропускает тест. Этого не произойдет, потому что в дикой природе достаточно кода, который использует этот тип проверки. Кроме того, в простой C это обычная практика.

источник

2010-10-29 22:30:32 ruslik

Это больше, чем неортодоксально; это в неопределенном поведении. Что делать, если это виртуальные функции? –

-1 не отличный шаблон для ссылки null на определенный тип и использовать его как объект. –

-1 Это полностью сломано. – meagar

Вы можете избавиться от вложенного МФСА и еще сослагательного наклонение

bool Node::lookup(int d) 
{ 
    if (data==d) 
     return true; 
    if (left != NULL && right != NULL) 
     return left->lookup(d) && right->lookup(d); 
    if (left != NULL) 
     return left->lookup(d); 
    if (right != NULL) 
     return right->lookup(d); 
    return false; 
}

источник

2010-10-29 22:49:26

Если вы хотите лаконичную версию кода в вопросе, вы можете сделать это:

bool Node::lookup(int d) 
{ 
    return 
     (data==d) || 
     (
      (right || left) && 
      (!left || left->lookup(d)) && 
      (!right || right->lookup(d)) 
     ); 
}

Но я подозреваю, вы хотите lookup вернуть true если таковые d матчи в либоleft или right, нет, если он соответствует в какleft и right

источник

2010-10-29 22:51:49 MSN

(! Left &&! Right) должен возвращать false в соответствии с оригиналом, не совсем правильно –

@Greg прямо сейчас! Исправлена. – MSN

троичный оператор укорачивает вещи красиво:

bool Node::lookup(int d) 
{ 
    if (data==d) 
    return true; 

    if (left == right) 
    return left == null ? false : left->lookup(d) && right->lookup(d); 
    return left == null ? right->lookup(d) : left->lookup(d); 
}

источник

2010-10-30 03:19:25 meagar

bool Node::lookup(int d) 
{ 
    return (data == d) 
     || (left && left->lookup(d)) 
     || (right && right->lookup(d));  
}

Я делаю предположение о том, что у вас есть логическая ошибка в вашем originial, так как она требует, чтобы, если левый и правый ребенка не равны нулю, что цель может быть найдена в и филиалов.

источник

2010-10-30 11:58:20 JohnMcG

Обзор кода: Как я могу упростить этот простой метод?

ответ

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