设计一个非递归（迭代）算法，求在给定二叉树的结点总数N的情况下，二叉树可能拥有的形状数M。

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

一、 设计一个非递归算法，求在给定二叉树的结点总数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
用非递归（迭代）算法解决问题一。函数原型为：void buildtree(int N,int &tree_count);即送入结点总数N，得到二叉树总数目tree_count。整个算法的总体结构如：
…
while(idx>0){
…
if(…)
idx++;
else
idx--;
…
}
同问题一，需要设定一个长度为N的数组int arr[],idx为数组下标，当可以顺利确定当前下标上的结点编号之后，idx会自增以完成下一个位置上的计算。当idx到达N时，说明找到问题的一个解（即发现一棵新的二叉树），打印输出数组的内容。

运行结果及报错内容

无

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

递归方式完成，迭代算法转换不会

我想要达到的结果

迭代算法完成设计

二叉树有五种基本形态，分别是：1、空二叉树；2、只有一个根结点的二叉树；3、只有左子树；4、只有右子树；5、完全二叉树。

如下是非递归实现的，如有帮助，请采纳！


#include <stdio.h>
#include <stdlib.h>
#define N 20
 
//二叉树结点的结构体表示形式
typedef struct tree
{
    char ch;
    struct tree *lchild;
    struct tree *rchild;
}BitTree;
 
//创建二叉树，利用递归的方法
//按前序次序输入。 如 A # #(#表示空树)
BitTree *CreateTree()
{
    BitTree *bt;
    char str; 
    scanf("%c",&str);
    if (str=='#')
        return NULL;
    else
    {
        bt=(BitTree *)malloc(sizeof(BitTree));
        bt->ch=str;
        bt->lchild=CreateTree();
        bt->rchild=CreateTree();
        return bt;
    }
}
 
//前序遍历的非递归实现
/*
 思想：利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，
 之后，左节点进栈；接着，弹出栈顶元素（输出）,
 此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）...一直这样下去，
 直到栈为空。
 */
void PreOrder(BitTree *bt)
{
    BitTree **s;
    BitTree *p;
    int top=-1;
    //创建栈；
    s=(BitTree **)malloc((N+1)*sizeof(BitTree *));
    //初始化栈；
    s[++top]=bt;
    //非递归前序遍历；
    while(top!=-1)
    {
        p=s[top--];
        printf("%c ",p->ch);    //栈的特点，先进后出；
        if(p->rchild)
            s[++top]=p->rchild;
        if(p->lchild)
            s[++top]=p->lchild;
    }
    free(s);
}
 
 
//中序遍历，非递归实现
/*
 思想：利用栈。从根节点开始循环，只要有左子节点则进栈，直到左子节点为空。
 接着弹出栈顶输出，判断该结点是否有右子节点，
 若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，
 有则进栈，直到左子节点为空；若该右子节点没有
 左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；
 接着又要判断刚进栈的这个节点，是否有左子节点，
 有则进栈，没有则继续弹栈。重复下去....
 栈空，是判定条件。
 */
void InOrder(BitTree *bt)
{
    BitTree **s;
    BitTree *p,*q;
    int top=-1;
    //创建栈；
    s=(BitTree **)malloc((N+1)*sizeof(BitTree *));
    //非递归中序遍历；
    if(bt)
    {
        while(bt)   //一直遍历左子树直到该结点的左孩子空为止；
        {
            s[++top]=bt;   //将所有左孩子存入栈中；
            bt=bt->lchild;     //指向下一个左子树；
        }
        while(top!=-1)  //栈空时结束循环；
        {
            p=s[top--];//刚开始将最p指向左下角的左孩子，并且移向该结点的父结点；
            printf("%c ",p->ch);  //输出左下角的结点；
            while(p->rchild)  //遍历移动后结点有没有右结点；
            {
                s[++top]=p->rchild;   //将这个结点的右子树入栈；
                q=p->rchild;          //这个右子树结点赋给q；
                while(q->lchild)      //判断结点q有没有左子树；
                {
                    s[++top]=q->lchild;  //有左子树，将与这个结点相连的所有左子树都入栈；
                    q=q->lchild;
                }
                break;   //结束当前循环，回到第二个while循环继续刚才的步骤；
            }
        }
    }
}
 
//后序遍历，非递归实现
/*
 算法思想:利用栈来实现。从根结点开始,只要左子节点非空,则进栈,直到左子节点
 为空为止。取出栈顶元素(只是取,并非弹栈),判断:
 1:取出的栈顶元素是否有右子节点,或者右子节点是否被访问过,若满足条件(无右子
 节点,或者右子节点被访问过),则输出该结点，同时弹栈,并且记录下该访问的节点。
 2:取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，
 重复一开始是否又左子节点的判断。
*/
void PostOrder(BitTree *bt)
{    
    BitTree **s;
    BitTree *p;
    int top=-1;
    //创建栈；
    s=(BitTree **)malloc((N+1)*sizeof(BitTree *));
    //非递归后序遍历；
    do
    {
        while(bt)     //一直遍历左子树直到该左子树的左孩子空为止；
        {
            s[++top]=bt;     //将所有左孩子存入栈中；
            bt=bt->lchild;   //指向下一个左子树；
        }
        p=NULL;
        while(top!=-1)
        {
            bt=s[top];
            if(bt->rchild==p)  //p:表示为null，或者右子节点被访问过了;
            {
                printf("%c ",bt->ch);   //输出结点数据域；
                top--;           //输出以后，top--；
                p=bt;  //p记录下刚刚访问的节点;
            }
            else
            {
                bt=bt->rchild;   //访问右子树结点；
                break;
            }
        }
    }while(top!=-1);
}
 
int main()
{
    printf("请以顺序输入二叉树(#表示该结点的子结点为空):\n");
    BitTree *btr=CreateTree();
    printf("前序遍历非递归实现：\n");
    PreOrder(btr);
    printf("\n");
    printf("中序遍历非递归实现：\n");
    InOrder(btr);
    printf("\n");
    printf("后序遍历非递归实现：\n");
    PostOrder(btr);
    printf("\n");
    return 0;
}

img