a.txt

按照前序非递归遍历二叉树

1.先序遍历非递归算法 
#define maxsize 100 
typedef struct 
{ 
Bitree Elem[maxsize]; 
int top; 
}SqStack; 

void PreOrderUnrec(Bitree t) 
{ 
SqStack s; 
StackInit(s); 
p=t; 

while (p!=null || !StackEmpty(s)) 
{ 
while (p!=null) //遍历左子树 
{ 
visite(p->data); 
push(s,p); 
p=p->lchild; 
}//endwhile 

if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 
{ 
p=pop(s); 
p=p->rchild; 
}//endif 

}//endwhile 

}//PreOrderUnrec 








#include "iostream.h" 
#include "stdlib.h" 
#include "stdio.h" 

typedef char ElemType;//定义二叉树结点值的类型为字符型 
const int MaxLength=10;//结点个数不超过10个 

typedef struct BTNode{ 
ElemType data; 
struct BTNode *lchild,*rchild; 
}BTNode,* BiTree; 


void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树 
// if(T) return; 
char ch; 
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。 
if(ch==' ') T=NULL; 
else{ 
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!"; 
T->data=ch; 
CreateBiTree(T->lchild); 
CreateBiTree(T->rchild); 
} 
} 
//非递归的先序遍历算法 
void NRPreOrder(BiTree bt) 
{ BiTree stack[MaxLength],p; 
int top; 
if (bt!=NULL){ 
top=0;p=bt; 
while(p!=NULL||top>0) 
{ while(p!=NULL) 
{ 
cout<<p->data; 
stack[top]=p; 
top++; 
p=p->lchild; 
} 
if (top>0) 
{ top--; p=stack[top]; p=p->rchild; } 
} 
} 
} 







typedef struct Binnode{

    char data;

    struct Binnode *lchild;

    struct Binnode *rchild;

  }Binnode;

   /*按照前序遍历建立二叉树*/

void Creat_Bintree(Binnode **t)

{

   char ch;

   scanf("\n%c",&ch);

   if(ch=='0') *t=NULL;

   else

     {

       *t=(Binnode*)malloc(sizeof(Binnode));

       if(!*t)exit(OVERFLOW);

       (*t)->data=ch;

       printf("%c: left",ch); Creat_Bintree(&(*t)->lchild);

       printf("%c: right",ch);Creat_Bintree(&(*t)->rchild);

     }

}

/*按照前序非递归遍历二叉树*/

void preorder2(Binnode *root)/*先序非递归遍历二叉树*/

{   Binnode  *p,*stack[100];

     int top ;

      p=root;

   if(root!=NULL)

        {top=1;

          stack[top]=p;

           while(top>0)

          {

           p=stack[top]  ;/*将右小孩放入栈*/

           top--;

           printf("%c",p->data);

             if(p->rchild!=NULL)

              {top++;

               stack[top]=p->rchild;

              }

             if(p->lchild!=NULL)

              {top++;

               stack[top]=p->lchild;

              }

          }

        }

}




/*递归法将二叉树的左右子树互换*/

void Exchange1(Binnode *t)

{

    Binnode *temp;

    if(t)

    {

        Exchange1(t->lchild);

        Exchange1(t->rchild);

        temp=t->lchild;

        t->lchild=t->rchild;

        t->rchild=temp;

    }

}