将递归运算转化为非递归运算为什么使用栈?
#define struct_sizes 20#define adds 10typedef struct bitnode//二叉树的定义{int data;//二叉树元素数据类型struct bitnode *lchild,*rchild;//左右孩子}*bitree;typedef struct//顺序栈的定义{bitree *base;//栈底指针bitree *top;//栈顶指针int stacksize;}sqstack;int initstack(sqstack &S)//新建一个空栈{S。 base=(bitree *)malloc(struct_sizes*sizeof(...全部
#define struct_sizes 20#define adds 10typedef struct bitnode//二叉树的定义{int data;//二叉树元素数据类型struct bitnode *lchild,*rchild;//左右孩子}*bitree;typedef struct//顺序栈的定义{bitree *base;//栈底指针bitree *top;//栈顶指针int stacksize;}sqstack;int initstack(sqstack &S)//新建一个空栈{S。
base=(bitree *)malloc(struct_sizes*sizeof(bitree));if(!S。base)return 0;S。top = S。base;S。stacksize = struct_sizes;return 1;}//initstackint stackempty(sqstack S)//判断栈是否为空{if(S。
base==S。top)return 1;else return 0;}int push(sqstack &S,bitree e)//进栈{if(S。top - S。base >= S。stacksize)//栈满重新分配空间{S。
base = (bitree *)realloc(S。base,(S。stacksize adds) * sizeof (bitree));if(!S。base)return 0;S。top = S。
base S。stacksize;S。stacksize = adds;}*(S。top )=e;return 1;}//pushint pop(sqstack &S,bitree &e)//出栈{if(S。
top == S。base)return 0;e = * --S。top;return 1;}//popint gettop(sqstack S,bitree &e)//取栈顶元素{if(S。
top == S。base) return 0;e = *(S。
top - 1);return 1;}//gettopint mid_travel(bitree T)//递归二叉树中序遍历{if(!T)return 0;else{if(T->lchild)mid_travel(T->lchild);printf(" %d",T->data);if(T->rchild)mid_travel(T->rchild);}return 1;}int mid_norecursion(bitree T)//中序遍历二叉树T的非递归算法,打印每个数据{sqstack S;bitree p;if(!T)return 0;initstack(S);push(S,T);//根指针进栈while(!stackempty(S)){while(gettop(S,p)&&p)push(S,p->lchild);//向左走到尽头pop(S,p); //空指针退栈if(!stackempty(S))//访问结点,向右一步{pop(S,p);printf(" %d",p->data);push(S,p->rchild);}}return 1;}。收起