请分别用递归和非递归方法实现查找二叉树中的最大元素的算法。

答案

查看答案

发布时间：2022-06-28

更多“请分别用递归和非递归方法实现查找二叉树中的最大元素的算法。”相关的问题

第1题

设二叉树共含n个节点，且各节点数据项的类型支持大小比较（类似于整数或浮点数)。试设计并实现一个递归算法，在o（n)时间内将每个节点的数值替换为其后代中的最大数值。

点击查看答案

第2题

将折半查找的算法改写为递归算法。

点击查看答案

第3题

关于kd-树查找算法kdSearch（)（教244页算法8.2)，试证明以下结论：a)在树中某一节点发生递归，当且

关于kd-树查找算法kdSearch()(教244页算法8.2)，试证明以下结论：

a)在树中某一节点发生递归，当且仅当与该节点对应的子区域，与查询区域的边界相交;

b)若令Q(n)=规模为n的子树中与查询区域边界相交的子区域(节点)总数，则有：Q(n)=2+2Q(n/4)=o(√n)。

c)kdSearch()的运行时间为：o(r+√n)，其中r为实际命中并被报告的点数。

d)进一步地，试举例说明，单次查询中的确可能有多达Ω(√n)个节点发生递归，故以上估计是紧的。

e)若矩形区域不保证与坐标轴平行，甚至不是矩形(比如圆)，则上述结论是否依然成立？

点击查看答案

第4题

设文法G]S]: S→^ | a | （T) T→T,S | S ⑴ 消除左递归；（3分） ⑵ 构造相应的FIRST和FOLLOW集合；（3+3分） ⑶ 判断其改写后的文法是否是LL（1）的（说明理由); （3分）（4) 若是LL（1)的，对每个非终结符，写出不带回溯的递归子程序（伪代码)。若不是LL（1)的，给出自上而下分析过程。（3分）

点击查看答案

第5题

考查教材5.4.2、5.4.3、5.4.4和5.4.5节所介绍的各种迭代式二叉树遍历算法。a)试证明，这些算法都是正确的——亦即，的确会访问每个节点一次且仅一次；b)试证明，无论递归式或迭代式，这些算法都具有线性时间复杂度；c)这些算法的空间复杂度呢？

点击查看答案

第6题

试将下列递归过程改写为非递归过程。