-1

假设我有一个 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();
}

问题当然是首先调用带有 NULL 的 printBinary 来调用未定义的行为！所以我想避免这种情况，据我所知，我至少有三种方法：

1) 使用静态成员函数，它得到一个可以安全检查的显式 this-type 参数。这实际上是我到目前为止所做的，但是因为它是一个非常递归的实现，几乎所有的成员函数都被编码为静态的。这不是很好，对吧？

2)在使用可能为“this”的 NULL 指针进行另一个递归调用之前检查下一个节点的停止条件。这是一种不太自然的写作形式，实际上会检查除此之外的其他项目。我想避免它。

3) 使用默认虚拟值。试过了，感觉它并没有真正为我节省任何特殊情况的处理，但这可能只是因为我的树的通用性。

我真的在这件事上大惊小怪了一段时间，所以如果有任何好的建议，我将不胜感激。

4

3 回答 3

2

你的代码是错误的。

this您可以检查NULL in ，而不是检查 NULL in ，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();
}

顺便提一句。这是一个链表。

于 2013-05-04T11:34:14.820 回答
1

如果您想从节点结构中导航，第二个解决方案是唯一的解决方案。然而，通常的解决方案是区分节点和树，导航代码是树对象的成员，而不是节点。该节点最多具有返回下一个指针的功能。这意味着导航函数将采用指向节点的指针；你printBinaryTree可能是这样的：

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

或者您可以使用访问者模式，它将树行走代码与每个节点的操作分开。

于 2013-05-04T11:39:53.743 回答
0

让我们试试你的实现：

#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
于 2013-05-04T12:01:43.690 回答