简单的C++递归解释需要

我目前正试图围绕递归包裹我的头，所以我选择了C++教科书并开始阅读。关于递归一章的前几页很容易理解，但后来我找到了一个对我来说没有意义的项目。简单的C++递归解释需要

int height(node *p) 
{ 
    if(p==NULL) 
     return 0; 
    else{ 
    return 1 + max(height(p->llink),height(p->rlink)); 

    }

如果max给了我最大的两个值，max是如何从它返回的高度得到它的参数的。如果有人可以帮助我将不胜感激.....

来源

2012-11-01 codenamejupiterx

绘制的'node's树的那张照片上，凝视了一会儿，想着代码在'高度'。 –

专注于基本案例，绘制一棵树并向后工作。 –

千斤顶答案是一个很好的提示关于如何进步 - 0是递归的终止，并且节点从父母指向左边和右边的孩子 - 依此类推... – Caribou

要理解递归，你必须递归认为：

你能理解一个空的树有高度0
你能理解一棵普通的非空树具有高度1 +最长子树的高度（可以是从左边开始或从右边开始的高度）

从这开始，你可以平凡地理解代码。如果你绘制树，你会看到会发生什么。如果您有例如

 A 
    /\ 
    B C 
/\ 
D E

height(A)将返回1 + max(height(B), height(C))
height(B)将返回1 + max(height(D), height(E))
height(C)将返回1 + max(height(NULL), height(NULL)) = 1
height(D)将返回1 + max(height(NULL), height(NULL)) = 1
height(E)将返回1 + max(height(NULL), height(NULL)) = 1

所以

height(A) = 1 + max(height(B), height(C)) = 
= 1 + max(1 + max(height(D),height(E)), 1) = 
= 1 + max(1 + 1, 1) = 1 + max(2, 1) = 3

（我省略height(NULL)电话，因为他们是平凡0，否则它会一直过于冗长。）

来源

2012-11-01 18:50:05 Jack

到函数的参数之前的函数调用进行评估。

所以，你的示范性等效可能看起来像下面的（这也许会更有意义？）：

int height(node *p) 
{ 
    if(p==NULL) 
     return 0; 
    else{ 
     int heightLeftSubtree = height(p->llink); 
     int heightRightSubtree = height(p->rlink); 
     return 1 + max(heightLeftSubtree, heightRightSubtree); 
    } 
}

来源

2012-11-01 18:54:55 PiotrNycz

简单的C++递归解释需要

回答

相关问题