preordertraverse.cpp

文件夹中包括常用的数据结构的算法

#include<malloc.h>
#include <stdio.h>
#define m0 100   //定义字符串结构中的最大长度
#define m2 20
#define null 0
#define Len  sizeof (BinNode)

enum tag{zero,one};

typedef struct BinNode             // 结点结构
{ 
	char data;
    struct BinNode *lch,*rch;
    enum tag ltag,rtag;
}BinNode,*Bintree;


struct chtp{ int len;      char ch[m0];    };  //定义字符串结构
struct BinNode *bt;   //定义2叉树的根节点指针
struct BinNode *stack[m2];       //定义堆栈，中序遍历二叉树的非递归算法要用
struct chtp s;
int top=0,ii=0;          //两个全局变量

void  crt_pre(Bintree *t) 
{ 
	char c;
    c=s.ch[ii];  
	ii=ii+1;

    if (c=='.')  *t=null;
    else 
	{ 
		*t=(BinNode *)malloc(Len);
		(*t)->data=c;
		crt_pre(&(*t)->lch);
		crt_pre(&(*t)->rch);
    };
}

void PreOrderTraverse( BinNode *t)      /*第一种前序遍历二叉树的非递归算法*/
{
	BinNode *p;
    top=0;
	
	p=t;

	if(t = NULL ) printf("error\n");
	else
	{
        while (top!=-1)
		{ 
	    	for(;p;)
			{ 
				printf("%c\t",(*p).data); 
				if(p->rch != NULL)              //若当前节点的右孩子不空，将根节点右孩子压入栈
				{
		            stack[top]=p->rch;             //将当前节点右孩子压入栈
		        	top=top+1;
				};
				p = p->lch;                
			}; 
            top=top-1;   //准备从栈中弹出前一个有右孩子节点的右孩子
            if(top!=-1) 
			{
		    	p=stack[top];  ////从栈中弹出前一个有右孩子节点的右孩子，作为下次遍历的起点
			};
		}
    	printf("\n");
	};
}

void preorder( BinNode  *b)        /*第二种前序遍历二叉树的非递归算法*/
{ 
	//BiTree *stack[m0];
    // int top;  
	BinNode *p;
     if (b!=NULL)
     { 
		 top=1;                   //根结点入栈
         stack[top]=b;
         while (top>0)       //栈不为空时循环
         {
			 p=stack[top];  //退栈并访问该结点
             top--;
             printf("%c\t",p->data);
             if (p->rch!=NULL)     //右孩子入栈
             { 
				 top++;
                 stack[top]=p->rch;
			 };
             if (p->lch!=NULL)    //左孩子入栈 
             {
				 top++;
                 stack[top]=p->lch;
             }
         }
     }
	 printf("\n");
}



void main()
{
//	char /*c[]={'a','b','d','.','.','.','c','e','.','.','f','.','.','!'};*/
    char    c[]={'a','b','c','.','.','d','e','.','g','.','.','f','.','.','.','!'};
    int i=0;
    for(i=0,s.len=0;c[i]!='!';i++,s.len++) s.ch[i]=c[i];
    
	crt_pre(&bt);
	
	PreOrderTraverse(bt);      /*第一种前序遍历二叉树的非递归算法*/
  
	preorder(bt);            /*第二种前序遍历二叉树的非递归算法*/
}