如何给递归算法
问题描述:
给递归算法btProd它需要输入一个二叉树,并输出 包含在二叉树的数字产品的价值。如果输入是空树,那么算法应该返回null。如何给递归算法
算法btProd(P)
要求:输入是一个树P
1:btProd(空)←0
2:btProd(叶X)←X
3 :btProd(节点L x R)←btProd(L)+ x + btProd(R)
这就是我会这么做的方式,但我不确定这是否正确
答
正如评论中所述,该产品是可交换的。因此,您可以按照您喜欢的任何顺序遍历树(pre-,in-,post-order)。假设你写+ x +
的意思是btProd(L)乘以btProd(R),那么你作为伪代码激发的递归似乎是正确的。
到目前为止你做了什么? –
因为乘法是可交换的,所以你可以以任何你想要的方式遍历树并且乘以所有的节点。 – maraca
请尝试一些步骤,并发布你尝试过什么 – Billa