返回递归三元怪胎

Question

假设以下功能:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        return 1 + max(findHeight(n->left), findHeight(n->right));
    }
}

treeHeight对于给定的二叉搜索树,相当标准的递归函数binaryTree.现在,我正在帮助一个朋友(他正在学习算法课程),我遇到了一个奇怪的问题,我无法100%向他解释这个功能.

将max定义为max(a,b) ((a)>(b)?(a):(b))(恰好是最大定义windef.h),递归函数变得怪异(它运行的n^n时间就像n树高一样).这显然使得检查具有3000个元素的树的高度非常非常长.

但是,如果max是通过模板定义的,就像std它一样,一切都很好.所以使用std::max修复他的问题.我只想知道原因.

另外,为什么countLeaves函数工作正常,使用相同的程序递归？

int binaryTree::countLeaves(node *n) {
    if (n == NULL) {
        return 0;
    } else if (n->left == NULL && n->right == NULL) {
        return 1;
    } else {
        return countLeaves(n->left) + countLeaves(n->right);
    }
}

是因为在返回三元函数时,值a => countLeaves(n->left)和b => countLeaves(n->right)递归双重调用只是因为它们是结果？

谢谢!

下面回答了这个问题

我只想链接一些有关该主题的文献以供将来参考:
http://www.boostpro.com/tmpbook/preprocessor.html
http://msdn.microsoft.com/en-us/library/z3f89ch8.aspx

这两种实现的主要区别在于:

#define max(i, j) (((i) > (j)) ? (i) : (j))

VS

template<class T> T max (T i, T j) { return ((i > j) ? i : j) }

谢谢你们!

Answer 1

在编译器查看代码之前,宏由预处理器进行扩展.这意味着,例如,宏参数可能会被多次评估.

使用你的宏,你最终会得到类似于:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        return 1 + (findHeight(n->left) > findHeight(n->right)) ? // call once...
                    findHeight(n->left) : findHeight(n->right); // and ouch
    }
}

正如您所看到的,它将评估两个函数,然后再评估一个额外的时间.这就是为什么宏可能是邪恶的.

您可以通过NOMINMAX在包含Windows标头之前定义来禁用宏.然后使用该函数<algorithm>.

如果他必须使用宏,他必须将计算存储在一个变量中:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        const int leftHeight = findHeight(n->left);
        const int rightHeight = findHeight(n->right);
        return 1 + max(leftHeight, rightHeight);
    }
}

使用函数,将在调用函数之前评估每个调用.也就是说,它有点像以前的代码块.它评估函数的参数,获取结果,然后将它们传递给std::max函数.没有重复的评估.