translevel.cpp

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

/*按层次顺序（同一层次自左至右）遍历二叉树的算法。
  假设二叉树采用二叉链表结构，依题意，本算法要采用一个队列q，
  先将二叉树根结点入队列，然后出队列，输出该结点；若它有左子树，
  便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，
  如此直到队列空为止。因为队列的特点是先进先出，
  从而达到按层次顺序遍历二叉树的目的。
*/

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

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 translevel(BinNode *t)      //按层次顺序（同一层次自左至右）遍历二叉树
{  
	struct node               //队列
    { 
		BinNode *vec[MAXLEN];
        int f,r; 
    }q;
    q.f=0;
    q.r=0;                                  //置队列为空队列
	BinNode *b=t;
    if (b!=NULL) printf("%c\t",b->data);
    q.vec[q.r]=b;                        //结点指针进入队列
    q.r++;
    while (q.f<q.r)               //队列不为空
	{ 
		b=q.vec[q.f];             //队头出队列
        q.f++;
        if (b->lch!=NULL)       //输出左孩子，并入队列
        { 
			printf("%c\t",b->lch->data); 
            q.vec[q.r]=b->lch;
            q.r++;
        }
       if(b->rch!=NULL)      //输出右孩子，并入队列
       { 
		   printf("%c\t",b->rch->data);
           q.vec[q.r]=b->rch;
           q.r++;
       }
   }
	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);
	
	translevel(bt);
}