递归调用建模完美二叉树意味着什么？
我正在学习数据结构和算法。我参考的书（Sedgwick）用“寻找最大元素”来说明分而治之的策略。该算法将数组中途分成两部分，（递归地）找到两部分中的最大元素，并返回两者中较大的一个作为整个数组的最大元素。
下面是一道练习题
修改用于查找数组中最大元素的分而治之程序（程序 5.6），将大小为 N 的数组划分为大小为 k = 2^(lg N – 1) 的一部分和大小为 k = 2^(lg N – 1) 的另一部分， N – k（以便至少其中一个部分的大小为 2 的幂）。
绘制与程序在数组大小为 11 时进行的递归调用相对应的树，类似于程序 5.6 中所示的树。
我发现这样的二叉树的左子树是完美二叉树，因为第一个子集的大小是 2 的幂。作者希望我从中得到什么启示？
I'm learning data-structures and algorithms. The book I refer to(Sedgwick) uses 'finding the maximum element' to illustrate the divide-and-conquer strategy. This algorithm divides an array midway into two parts, finds the maximum elements in the two parts (recursively), and returns the larger of the two as the maximum element of the whole array.
The below is an exercise question asked
Modify the divide-and-conquer program for finding the maximum element in an array (Program 5.6) to divide an array of size N into one part of size k = 2^(lg N – 1) and another of size, N – k (so that the size of at least one of the parts is a power of 2).
Draw the tree corresponding to the recursive calls that your program makes when the array size is 11, similar to the one shown for Program 5.6.
I see that the left sub-tree of such a binary tree is a perfect binary tree because the size of the first subset is a power of two. What is the implication the author is hoping that I should get from this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为这个练习的要点在于k。它表明，如果您在二元递归中使用此公式表示 k，那么您的底层树是“漂亮的”，因为每个节点（不仅仅是根）的左子树是完美的二叉树。
当然，当N是2的幂时，它在“理想”情况下也表现良好；那么k就是N/2，并且每个子树（不仅是左边）都是完美二叉树。
I suppose that one nugget of this exercise lies in the k. It makes the point that if you use this formula for k in a binary recursion, then your underlying tree is "pretty", in the sense that the left subtree of every node (not just the root) is a perfect binary tree.
Of course it is also well-behaved in the "ideal" case when N is a power of 2; k is then simply N/2, and every subtree (not only the left) is a perfect binary tree.