所以我不确定这个问题是属于这里还是属于软件工程,但由于我对 C++ 实现特别感兴趣,所以我在这里问。
现在,除此之外,我已经实现了一个基本的二叉树,其中包含一个通用遍历函数,用于处理前序、中序和后序。
void BiTree::_trav(BiNode* root, int offset, function<void (int&,int&)> lambda) {
if (root == NULL) {return;}
auto call = [&] () {lambda(root->data, root->sc);};
if (offset == 0) { call();}
_trav(root->child[0], offset, lambda);
if (offset == 1) { call();}
_trav(root->child[1], offset, lambda);
if (offset == 2) { call();}
}
可以看到,这个函数是递归调用自己的,而且有很多分支。由于不是每个人都知道 C++ 或 C++ 中的 lambda(我昨天还不知道),所以这里将相同的想法归结为问题。
void BiTree::_trav(BiNode* root, int offset) {
if (root == NULL) {return;}
if (offset == 0) { do_thing();}
_trav(root->child[0], offset, lambda);
if (offset == 1) { do_thing();}
_trav(root->child[1], offset, lambda);
if (offset == 2) { do_thing();}
}
我的编程直觉告诉我有更好的方法可以做到这一点,分支更少,但我不知道如何做。 switch 语句不起作用,因为 do-thing()
被调用不止一次,或者有更多的分支。所以我对如何使用最少的分支进行通用树遍历很感兴趣。
最佳答案
因此,我使用一组虚拟函数来回答我自己的问题,并将该函数与我实际想要运行的代码一起插入到我想要运行它的地方。我不确定这是否会提高性能,但它似乎减少了分支。
void BiTree::_trav(BiNode* root, int offset, function<void (int&,int&)> lambda) {
if (root == NULL) {return;}
function<void (void)> branches[3];
for(int i = 0; i < 3; i++) {
branches[i] = [&] () {};
}
function<void (void)> call = [&] () {lambda(root->data, root->sc);};
branches[offset] = call;
branches[0]();
_trav(root->child[0], offset, lambda);
branches[1]();
_trav(root->child[1], offset, lambda);
branches[2]();
}
关于c++ - 减少通用树遍历中的分支,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40316405/