问题遇到的现象和发生背景
递归的代码我已经写好,使用的是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);
}
上面的代码是我写好的递归。
运行结果及报错内容
暂无
我的解答思路和尝试过的方法
我的想法是自己建立栈来替代系统给的栈
我想要达到的结果
能够使用非递归的方法完成程序。