递归转化为非递归
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#define stackmaxsize 100
//__________________________________________
struct btreenode{
int data;
struct btreenode*left;
struct btreenode*right;
};
class cstack{
private:
struct btreenode stack[1000];
int cur;
public:
cstack(){cur=0;}
void push(struct btreenode *a);
struct btreenode pop();
int empty();
};
int cstack::empty()
{
return cur==0;
}
void cstack::push(struct btreenode *a)
{
stack[cur].data=a-> data;
stack[cur].left=a-> left;
stack[cur].right=a-> right;
cur++;
}
struct btreenode cstack::pop()
{
if(empty()) {printf( "栈已空! ");exit(1);}
else{
cur--;
return stack[cur];
}
}
struct btreenode *inttostruct(int x)//将整型数据转化成结构体（主要用于保存地址）
{
struct btreenode *p;
btreenode b;
b.data=x;
b.left=NULL;
b.right=NULL;
p=&b;
return p;
}
void preorder(struct btreenode* bt)
{
cstack st;
l0:
if (bt!=NULL){
printf( "%c ",bt-> data);
st.push(bt);
st.push(inttostruct(1));
bt=bt-> left;
goto l0;
//preorder(bt-> left);
l1:
st.push(bt);
st.push(inttostruct(2));
bt=bt-> right;
goto l1;
//preorder(bt-> right);
l2:;
}
while( !st.empty()){
int retaddr = st.pop().data;
bt-> right= st.pop().right;
bt-> left= st.pop().left;
bt-> data= st.pop().data;
if( retaddr == 1 ) goto l1;
else goto l2;
}
}
void createbtree(struct btreenode** bt,char *a )
{
struct btreenode*p;
struct btreenode * s[stackmaxsize];
int top=-1;
int k;
int i=0;
*bt=NULL;
while(a[i])
{
switch(a[i]){
case ' ':
break;
case '( ':
if(top==stackmaxsize-1){
printf( "栈空间太小,需增加staxkmaxsize!\n ");
exit(1);
}
top++;s[top]=p;k=1;
break;
case ') ':
if(top==-1){
printf( "二叉树广义表字符串错!\n ");
exit(1);
}
top--;break;
case ', ':
k=2;break;
default:
p=(struct btreenode*)malloc(sizeof(struct btreenode));
p-> data=a[i];p-> left=p-> right=NULL;
if(*bt==NULL)*bt=p;
else{
if(k==1) s[top]-> left=p;
else s[top]-> right=p;
}
}
i++;
}
}
void main ()
{
struct btreenode *bt;
char a[50];//广义字符串
printf( "输入二叉树广义表表示的字符串:\n ");
scanf( "%s ",&a);
createbtree(&bt,a);//据输入的广义表建立二叉树
printf( "前序遍历结果：\n ");
preorder(bt);//前序遍历
printf( "\n ");
}
该算法要求用非递归实现前序遍历.
问题:只能前序遍历二个结点,并会出现关闭程序的提示,应该是指针的使用出现的问题,
while( !st.empty()){
int retaddr = st.pop().data;
bt-> right= st.pop().right;
bt-> left= st.pop().left;
bt-> data= st.pop().data;
if( retaddr == 1 ) goto l1;
else goto l2;
这里可能没有循环起来,请高手帮忙看看,期待中.....
[解决办法]
算了，这个我也不会。递归很好呀，C++库里自己都大量使用递归的。
[解决办法]
【Ref】
遍历二叉树的非递归算法
作者： 来源： 发表时间：2006-06-05 浏览次数： 375 字号：大 中 小
编写的方法：根据树中结点的遍历规律及顺序直接写出其非递归算法。
先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T-> data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T-> data后，将T-> rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T-> rchild，出栈，遍历以该指针
为根的子树。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法一，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T-> data) ;
Push(S,T);
T = T-> lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T-> rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法二，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T-> data);
Push(S, T-> rchild);
T = T-> lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T-> data，再中序遍历T的右子树。
【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T-> lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T-> data);
T = T-> rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T-> lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T-> data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 设置栈顶标记
T = GetTopPointer(S); // 取栈顶保存的指针
T = T-> rchild;
}else break;
}
}
[解决办法]
MARK
