2022-04-28 20:42

# 从递归到非递归的转换，求详细解释

###### 问题相关代码，请勿粘贴截图

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define MaxSize 6000000
int visited[MaxSize] = { 0 }; //访问数组
void arrange(int arr[], int idx, int N, int& tree_count)
{
int i;
int lc, rc;
if (idx < 0) //函数调用错误
return;
if (idx == 0) //入口
{
arr[idx] = 1;
arrange(arr, idx + 1, N, tree_count);
}
if (idx >= N) //出口
{
printf("%d:", ++tree_count);
for (i=0; i<N-1; i++)
printf("%d,", arr[i]);
printf("%d\n", arr[i]);
return;
}
for (i=0; i<idx; i++)
{
lc = arr[i] * 2;//i节点左该子
rc = arr[i] * 2 + 1;//i节点右该子
if (lc > arr[idx - 1] && visited[lc] == 0) //左该子可插入且未被访问过
{
arr[idx] = lc;
visited[lc] = 1;
arrange(arr, idx + 1, N, tree_count);
visited[lc] = 0; //左该子退栈
}
if (rc > arr[idx - 1] && visited[rc] == 0)
{
arr[idx] = rc;
visited[rc] = 1;
arrange(arr, idx + 1, N, tree_count);
visited[rc] = 0; //右该子退栈
}
}
}//BFS

int main(void)
{
int N;
printf("输入二叉树结点总数:");
scanf("%d", &N);
int* arr = (int*)malloc(N * sizeof(int));
int tree_count = 0;
arrange(arr, 0, N, tree_count);
printf("tree_count is %d when N is %d", tree_count, N);
}