lsy_xie
2022-04-28 20:42
采纳率: 66.7%
浏览 56

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

问题遇到的现象和发生背景

递归的代码我已经写好,使用的是DFS算法,我想用非递归的方法实现程序,建立好栈之后没有头绪了。

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

#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);
}
上面的代码是我写好的递归。

运行结果及报错内容

暂无

我的解答思路和尝试过的方法

我的想法是自己建立栈来替代系统给的栈

我想要达到的结果

能够使用非递归的方法完成程序。

3条回答 默认 最新

相关推荐 更多相似问题