tree.c

数据结构中关于二叉树的建造

#include "Conio.h" 
#include "time.h" 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>                                                 /**/
#define SIZE 100
#define nothing 0                                                 /*表示空号*/
#define ElemType int
typedef struct {
        int num;	
        int data;
        int parent;
	    int lchild;
	    int rchild;
}BTree;
int xuhao,list[SIZE+1],zhuan,cishu,suijizhi;
int rp,lp,t,j,l,s,u,i,k=1,x;
int checked[SIZE+1],PrintAlready[SIZE+1];
BTree Member[SIZE+1];
main()
{  
	    i=face();
        i=disorder();
		for(i=1;i<=100;i++)  printf("NO.%d = %d\t",i,Member[i].data);
        i=build();                           		
        preorder(1);
	   //inorder(1); 
	 //postorder(1);

}
int face()
{
printf("                                                                    ");
printf("         *    *                            *   *         \n          ");                                                
     printf("        *          *                  *          *            \n ");
            printf("        *                *       *                *     \n");
     printf("        * What do you want to do? Input the number*           \n ");   
     printf("         *                                        *           \n ");
     printf("          *                                      *            v ");
     printf("           *   1.Build a tree in good order     *             \n ");
     printf("            *                                  *               \n");
    printf("             *                                *                  \n");
 printf("              *                              *                    \n ");
   printf("               *  2.A tree without order   *                      \n");
               printf("                *                         *           \n ");
 printf("                 *                       *                          \n");
printf("                  *   3.Scan the tree  *                             \n");
            printf("                   *                  *                 \n ");
printf("                    *               *                                \n");
 printf("                     *   4.exit    *                                  \n");
printf("                       *         *                                   \n");
 printf("                          *  *                                      \n ");
printf("                Please enter your choice:                              ");
                                                return (2);
}
int build()
{
		for(i=1;i<=100;i++)  printf("NO.%d = %d\t",i,Member[i].data);                                    		
		for(i=1;i<=100;i++)		Member[i].num=i;                   /* 建立联系,组成树  */ 			
		for(i=1;i<=SIZE/2;i++)                                                                          
	{
	     if(i*2>SIZE) 
	     Member[i].lchild=nothing;
         else
		 {
		     Member[i*2].parent=Member[i].num;                    /*//建立“双亲-左孩子”联系*/
             Member[i].lchild= Member[i*2].num;
		 }
	     if(i*2+1>SIZE) 
	     Member[i].rchild =nothing;
         else
		 {
		     Member[i*2+1].parent=Member[i].num;                  /*//建立“双亲-右孩子”联系*/
             Member[i].rchild=Member[i*2+1].num;
		 }
	}
	Member[1].parent=0;
}
int disorder()                                                      /*随机排列结点的值*/
{ 
	int x,i; 
		for(cishu=1;cishu<=SIZE;cishu++)
	{
		Member[cishu].data=cishu;
	}
	for(cishu=1;cishu<=SIZE;cishu++)
	{
		srand(time(0));
        suijizhi=rand()%SIZE+1;
		zhuan=Member[cishu].data;
        Member[cishu].data=Member[suijizhi].data;
		Member[suijizhi].data=zhuan;
	}
       return(1);
} 

                                                                  /*//以下是先序遍历方法组：*/


preorder(int o)                                                   /*//代入先序法，逐个儿按遍历顺序查看结点。*/
{
    s=o;
	for(;s!=0;)
	{
		s=PrintFist(s);
	}
}
int PrintFist(int b)
{                                                              
	t=0;
	if(b!=0)
	{                                                      
		if(belong(Member[b].num,checked)==0)                        /*//没有访问过该结点。*/
		{
		     printf("%d\n",Member[b].data);                         /*//第一件事：打印数据*/
	            for( k=1;k<=SIZE;k++)                               /*//第二件事：把结点号放进“已读记录”*/
				{
		             if (checked[k]==0)
					 {
	                     checked[k]=Member[b].num;
		                 break;
					 }
				} 	
		}
		
			i=Member[b].lchild;   j=Member[b].rchild;              /*//定义新变量，简化运算。(i.j分别表示左右孩子的序号)*/
			if(belong(Member[i].num,checked)==1)                   /*//“已读记录”中有左孩子号：已查过左孩子，应查右孩子了。*/
			                                                       /*//用了点小技巧，对比从checked[0]（值为0）开始，*/
			                                                       /*//把没有左孩子当成孩子已访问处理，简化了。*/
			{
				if(belong(Member[j].num,checked)==1)
				                                                   /*//查右孩子不成功，返回去查双亲（技巧同上）*/
			    t=Member[b].parent;
			    else
				t=Member[b].rchild;                                /*//查右孩子*/
			}
		    else t=Member[b].lchild;                               /*//查左孩子*/
		                                       
		return (t);
	}
	else exit(0);
}

                                                                    /*//以下是中叙遍历方法组和先序方法组差不多*/
                                                                    /*//不详细叙：*/

inorder(int o)                                                     
{
    s=o;
	for(;s!=0;)
	{
		s=PrintSecond(s);
	}
}
int PrintSecond(int b)
{                                                              
	t=0;
	if(b!=0)
	{                                                      
		if(belong(Member[b].num,checked)==0)                       
		{
	            for( k=1;k<=SIZE;k++)                              
				{
		             if (checked[k]==0)
					 {
	                     checked[k]=Member[b].num;
		                 break;
					 }
				} 	
		}
       i=Member[b].lchild;       j=Member[b].rchild;
                                                                /*//和先叙遍历不同，中序法查完左孩子，再打印数据。*/
	   if(belong(Member[i].num,checked)==1)                     /*//“打印记录”中有左孩子号：已查过左孩子，应查右孩子了。*/
	   {
		   if(belong(Member[b].num,PrintAlready)==0)             /*//检查有没有打印过该结点，防止重复打印。*/
		   {
		        printf("%d\n",Member[b].data);                  /*//打印数据*/
	            for(l=1;l<=SIZE;l++)                            /*//把结点号放进“已打印记录”，防止重复打印*/
				{
		             if (PrintAlready[l]==0)
					 {
	                     PrintAlready[l]=Member[b].num;//
		                 break;
					 }
				} 	
		   }
			if(belong(Member[j].num,checked)==1)
			                                                  
			t=Member[b].parent;
	        else
			t=Member[b].rchild;
		}
	    else t=Member[b].lchild;     
        return(t);
	}
	else exit(0);
}
                                                                 /*//以下是后序遍历方法组：*/
postorder(int o)                                                     
{
    u=o;
	for(;u!=0;)
	{
		u=PrintThird(u);
	}
}
int PrintThird(int b)
{                                                              
	t=0;
	if(b!=0)
	{                                                      
		if(belong(Member[b].num,checked)==0)                       
		{
	            for( k=1;k<=SIZE;k++)                              
				{
		             if (checked[k]==0)
					 {
	                     checked[k]=Member[b].num;
		                 break;
					 }
				} 	
		}
       i=Member[b].lchild;       j=Member[b].rchild;
                                                                
	   if(belong(Member[i].num,checked)==1)                     
	   {
		   
			if(belong(Member[j].num,checked)==1)
			{
				                                                          /*//与先叙和中序遍历都步不同，后序法在访问双亲前打印数据。*/
				if(belong(Member[b].num,PrintAlready)==0)                 /*//和中序法一样，要检查有没有打印过该结点，防止重复打印。*/
				{
		               printf("%d\n",Member[b].data);                     /*//打印数据*/
	                   for(l=1;l<=SIZE;l++)                               /* //把结点号放进“已打印记录”，防止重复打印*/
					   {
		                    if (PrintAlready[l]==0)
							{
	                             PrintAlready[l]=Member[b].num;
		                         break;
							}
					   } 	
				} 
				t=Member[b].parent;
			}
	        else
			t=Member[b].rchild;
		}
	    else t=Member[b].lchild;     
        return(t);
	}
	else exit(0);
}

                                                                           /*//检验数据是否已被查过*/
int belong(int i,int j[SIZE+1])
{
	int count; int TrueOrNot=0;
	for(count=0;count<=SIZE && TrueOrNot==0; count++)
	{
		if(i==j[count])
		TrueOrNot=1;
	}
	return TrueOrNot;
}