c - 以下代码如何工作？找到树的深度？

Question

请解释以下代码的工作原理？我无法得到递归。

int depth(struct tree *q)
{ 
    int h1,h2;
    if(q==NULL)
       return 0;
    else
    {
       h1=depth(q->left);
       h2=depth(q->right);
    }
    return (max(h1,h2) +1 );
}

递归在上述代码中是如何工作的？h1 和 h2 如何获得价值？

Answer 1

想象一棵只有 3 个节点、1 个根和 2 个子节点的简单树

      Node R
     /      \
    /        \
Node A      Node B

第一次调用 depth 将 Node R 作为它的参数。

呼叫 1)q不是NULL这样depth()被称为节点 R 左 == 节点 A

调用 2)q不是NULL这样depth()调用节点 A left ==NULL

调用 3)q所以NULL返回 0；

调用 2)h1 = 0; 现在调用节点 A right = NULL

调用 4)q所以NULL返回 0；

呼叫 2)h1 = 0; h2 = 0; return max(0, 0) + 1

调用 1)h1 = 1; 现在调用节点 R 右 = 节点 B

调用 5)q不是为节点 B left == NULL 调用NULL的depth()

调用 6)q就是NULL这样返回 0；

调用 5)h1 = 0; 现在调用节点 B right = NULL

调用 7)q就是NULL这样返回 0；

呼叫 5)h1 = 0; h2 = 0; return max(0, 0) + 1;

呼叫 1)h1 = 1; h2 = 1; return max(1, 1) + 1;

返回 2。