Проверка этого == NULL в качестве члена-функции, не прибегая к непредсказуемому поведению

Question

Предположим, что у меня есть класс C++, и я хотел бы иметь рекурсивный член-функцию, которая вызывается с экземплярами элементов класса, например

// the eplicit "this" is just for clarity in the following code: 
void recursivePrintTree(){ 
    (if this == NULL){ // We are "out" of the tree 
     return; 
    } 
    cout << this->val; 
    (this->leftSon)->printBinaryTree(); 
    (this->rightSon)->printBinaryTree(); 
} 

Проблема заключается, конечно, в вызове неопределенного поведения, вызвав printBinary с NULL в первую очередь! поэтому я хотел бы избежать этого, и насколько я знаю, у меня есть по крайней мере три способа сделать это:

1) Использование статических функций-членов, которые получают явный аргумент этого типа, который можно безопасно проверять. это на самом деле то, что я сделал до сих пор, но поскольку это очень рекурсивная реализация, почти все функции-члены кодируются как статические. Это не очень хорошо, не так ли?

2) проверка состояния останова для узла следующего перед другим рекурсивным вызовом с указателем NULL, возможно, как «это». Это гораздо менее естественная форма написания и на самом деле проверяет другие предметы, что это. и я хотел бы избежать этого.

3) Использование стандартных фиктивных значений. Пробовал это, почувствовав, что это не спасает меня каким-либо специальным случаем, но это, возможно, было только из-за родословности моего дерева.

Я действительно беспокоился об этом вопросе какое-то время, поэтому буду признателен за любые полезные советы.

Answer 1

Ваш код является неправильным.

Вместо проверки на NULL в this вы можете проверить NULL в this->next, чтобы избежать вызова метода для указателей NULL в первую очередь.

То есть, вместо того, чтобы:

void printBinaryTree() { 
    if(this == NULL){ 
     return; 
    } 
    cout << this->val; 
    this->next->printBinaryTree(); 
} 

ли это:

void printBinaryTree() { 
    cout << this->val; 
    if(this->next) 
     this->next->printBinaryTree(); 
} 

BTW. это связанный список.

Answer 2

Второе решение является единственным решением , если вы хотите, чтобы перемещаться изнутри структуры узла. Однако обычное решение, , состоит в том, чтобы различать узлы и дерево, а навигационный код является членом древовидного объекта, а не узла. В большинстве случаев узел имеет функцию для возврата следующего указателя. Это означает, что функции naviagtion будут иметь указатель на узлов; Ваш printBinaryTree может быть что-то вроде:

void 
BinaryTree::print(Node const* node) 
{ 
    if (node != NULL) { 
     node->print(); 
     print(node->next()); 
    } 
} 

Или вы можете использовать шаблон посетителя, который отделяет дерево пешеходную код из действий на каждом узле.

Answer 3

Давайте попробуем вашу реализацию:

#include <iostream> 

class BinaryTree { 
    public: 
     BinaryTree(int value, BinaryTree * left, BinaryTree * right) : value_(value), left_(left), right_(right) {} 

     void printBinaryTree(int depth = 0) { 

      for (int i = 0; i < depth; i++) std::cout << " "; 

      if (this == NULL) { 
       std::cout << "Null node, returning..." << std::endl; 
       return; 
      } 
      else { 
       std::cout << value_ << std::endl; 
      } 

      left_->printBinaryTree(depth+1); 
      right_->printBinaryTree(depth+1); 
     } 

    private: 
     int value_; 
     BinaryTree * left_; 
     BinaryTree * right_; 
}; 

int main() { 
    BinaryTree leaf(0,NULL,NULL); 
    BinaryTree top(1,&leaf, &leaf); 

    top.printBinaryTree(); 

    return 0; 
} 

Если мы делаем этот пробег, мы получаем вывод, который выглядит следующим образом:

1 
    0 
    Null node, returning... 
    Null node, returning... 
    0 
    Null node, returning... 
    Null node, returning... 

Причина, почему это работает, объясняется здесь: Accessing class members on a NULL pointer

Однако, согласно стандарту C++, это неопределенное поведение. Как и в, это работает только потому, что реализация вашего или, в данном случае, моего, компилятора способна выполнить эту работу. Это не гарантия, и это снижает вашу мобильность и может даже перестать работать, если вам когда-нибудь понадобится обновить свой компилятор!

Есть несколько вариантов этого. Вы уже перечисляете некоторые, хотя я должен сказать, что мне не нравится статическая реализация, потому что это не имеет особого смысла с точки зрения дизайна и делает весь ваш код беспорядочным. Дополнительным решением может быть сделать функцию printBinaryTree виртуальной и определить листовые узлы как дочерний класс дерева. Это пример:

#include <iostream> 

class BinaryTree { 
    public: 
     BinaryTree(int value, BinaryTree * left, BinaryTree * right) : value_(value), left_(left), right_(right) {} 

     virtual void printBinaryTree(int depth = 0) { 

      for (int i = 0; i < depth; i++) std::cout << " "; 

      std::cout << value_ << std::endl; 

      left_->printBinaryTree(depth+1); 
      right_->printBinaryTree(depth+1); 
     } 

     int getValue() { return value_; } 

    private: 
     int value_; 
     BinaryTree * left_; 
     BinaryTree * right_; 
}; 

class BinaryTreeLeaf : public BinaryTree { 
    public: 
     BinaryTreeLeaf(int value) : BinaryTree(value, NULL, NULL) {} 

     virtual void printBinaryTree(int depth=0) { 
      for (int i = 0; i < depth; i++) std::cout << " "; 

      std::cout << getValue() << std::endl; 
     } 

}; 

int main() { 
    BinaryTreeLeaf leaf(0); 
    BinaryTree top(1,&leaf, &leaf); 

    top.printBinaryTree(); 

    return 0; 
} 

Выход здесь, по желанию, является:

1 
    0 
    0