1.cpp

先序遍历的非递归算法

#include<stdio.h>
#include<malloc.h>
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
bool CreateBiTree(BiTree &T){
	char ch;
	scanf("%c",&ch);
	if (ch=='0') T=NULL;
	else {
	       T=(BiTNode *)malloc(sizeof(BiTNode));
		   T->data=ch;
		   CreateBiTree(T->lchild);
		   CreateBiTree(T->rchild);
	}return 1;
} 
void preorder( BiTree  b)
  { BiTree stack[100],p;
     int top;  
     if (b!=NULL)
       { top=1;                   //根结点入栈
          stack[top]=b;
          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 main()
{   
	BiTree T=NULL;
	CreateBiTree(T);
	printf("先序序列为：");
	preorder(T);
	printf("\n");
}