m0_60928107 2022-04-24 21:30 采纳率: 0%
浏览 361

设计递归和非递归算法,在给定二叉树的结点总数N的情况下,输出二叉树可能拥有的形状

一、 设计一个递归算法,求在给定二叉树的结点总数N的情况下,二叉树可能拥有的形状数M。请看如下说明和要求:
(1) 满足要求的任何一棵二叉树都是高度为N的满二叉树从根结点开始的子树。将这棵满二叉树的结点按照从上至下、从左至右的顺序进行编号,根结点的编号为1,则可以按层次输出任何结点总数为N的二叉树的所有结点编号。例如当N=3时,输出结果为:
1: 1, 2, 3
2: 1, 2, 4
3: 1, 2, 5
4: 1, 3, 6
5: 1, 3, 7
tree_count is 5 when N is 3
(2) 递归函数的原型是:void arrange(int arr[],int idx,int N,int &tree_count);其中arr是存放编号序列的数组,idx是当前需要计算的数组元素的下标,N是结点总数也是数组长度,tree_count记录二叉树的数目。
(3) 并不需要实际构造出一棵二叉树,只需要把各种可能的合法编号序列计算出来就能统计二叉树的数目,因此重点是编写算法arrange(),要求输出每一个合法的序列;
二、用非递归(迭代)算法解决问题一。函数原型为:void buildtree(int N,int &tree_count);即送入结点总数N,得到二叉树总数目tree_count。整个算法的总体结构如:

while(idx>0){

if(…)
idx++;
else
idx--;

}
同问题一,需要设定一个长度为N的数组int arr[],idx为数组下标,当可以顺利确定当前下标上的结点编号之后,idx会自增以完成下一个位置上的计算。当idx到达N时,说明找到问题的一个解(即发现一棵新的二叉树),打印输出数组的内容。
语句idx--;是在当前位置上的所有合法取值都已经试验完毕,或者是刚刚输出了一个可行解之后执行的。


请问解题思路是什么呀?

  • 写回答

1条回答

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 创建了问题 4月24日

      悬赏问题

      • ¥15 ue如何做自然的物体边缘磨损效果材质
      • ¥15 求解答,急,本人真的是没有办法了
      • ¥15 我是在windows环境下通过IIS部署django项目,但是是这样怎么处理呢
      • ¥15 python 循环语句问题
      • ¥30 51单片机测量脉冲周期/频率并加以计算、显示
      • ¥50 图书期刊管理系统c++
      • ¥20 c语言基础,设计带界面的小应用
      • ¥15 Erplab无法创建事件清单
      • ¥15 fdisk输入n后不提示选择分区类型
      • ¥15 关于#java#snaker 工作流的问题,如何解决?