mayetree1.cpp

实现N叉树的建立、节点插入、删除、查找等。在devC环境下编译运行正常。

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node
{
	char name;
	int num;
};
struct node st[100];
int treein();
int size;
void show();
int deletenode();
int insertnode();
void searchnode();
int main()
{
	int f=6;
	while(f!=0)
	{printf("输入你的命令——1、输入树 2、删除结点 3、插入结点 4、查询结点 5、显示树 0、退出\n");
	fflush(stdin);
    scanf("%d",&f);
	if(f==1)
	{
    treein();f=6;}
	else if(f==5)
	{show();f=6;}
	else if(f==4)
	{searchnode();f=6;}
	else if(f==3)
	{insertnode();f=6;}
	else if(f==2)
	{deletenode();f=6;}
	else continue;
    }
	
	system("pause"); 
	return 0;
}
int treein()
{
    char s[50];
	int x=0;int k=1;
	int i=0;
	size=0;
	char ch;
	printf("请以括号的形式输入新树\n");
	fflush(stdin);
	gets(s);
	int j=0;
	ch=s[j];
	for(i=0;i<20;i++)
	{
        st[i].name='\0';
        st[i].num=0;
    }
	while(ch!='\0')
	{
		switch(ch)
		{
			case '(':x=x*10+1,k=1;break;
			case ')':x=x/10;break;
			case ',':x=x+1;break;
			default:if(x==0) {st[size].name=ch;st[size].num=1;x=1;size++;}
                    else {st[size].name=ch;st[size].num=x;size++;}break;
		}
		j=j+1;
		ch=s[j];
	}
	return size;
}
int deletenode()
{
	char c;
	int w,x,y,i;
	w=size;
	printf("你要删除哪个结点？\n");
	fflush(stdin);
	scanf("%c",&c);
	for(i=0;i<w;i++)
	{
		if (st[i].name==c)
		{
			break;
		}
	}
	if((i==w)&&(st[i].name!=c))
		printf("不存在你要删除的结点！\n");
	else
   {x=i;
	for (i=x;i<w;i++ )
	{
		if (st[i].num==st[x].num*10+1)
		{
			st[x].name=st[i].name;
			x=i;
		}
	}
	while(st[x+1].num>st[x].num)
	{
		st[x].name=st[x+1].name;
		x++;
	}
	for (i=x;i<w-1;i++ )
	{
		st[i].num=st[i+1].num;
		st[i].name=st[i+1].name;
	}
	size=w-1;
	return size;
   }
}

int insertnode()
{
    int i,w,j,k;
    w=size;
    char c,father;
	int x,y,fc;
	int count=0;
	int count1=0;
	struct node tmp;
    printf("你要将哪个结点插入到哪个结点下？输入提示：如输入a,b表示新建一个结点a将它插入到b下。\n");
    fflush(stdin);
	scanf("%c,%c",&c,&father);
	for(i=0;i<w;i++)
	{
		if (st[i].name==father)
		{
			x=i;break;
		}
		else continue;
	}
	y=st[x].num;
	for(i=x;i<w;i++)
	{
		if ((st[i].num>y*10)&&(st[i].num<(y+1)*10))
		{
			count1++;
		}
	}
	for(i=x+1;i<w;i++)
	{
		if (st[i].num>y*10)
		{
			count++;
		}
		else break;
	}
	k=x+count;
	fc=k+1;
	st[w].num=st[x].num*10+count1+1;
	st[w].name=c;
	tmp=st[w];
	for(i=w;i>fc;i--)
	{
		st[i]=st[i-1];
	}
	st[fc]=tmp;
    size=w+1;
    return size;
}

void searchnode()
{
     int i,n,max,a,b,j,pd;
     max=0;
     int w;
     w=size;
     int k=0;
     printf("输入你要查询的结点序号（你要查的是第几个结点？）：\n");
     scanf("%d",&n);
     if(n>w)
        {printf("你要找的结点不存在\n");}
     for(j=0;j<w;j++)
     {
        a=log10(st[j].num);           
        if(max<a)
        {max=a;}
     }
     for(i=0;i<=max;i++)
     {
        for(j=0;j<w;j++)                
        {
        pd=log10(st[j].num);                             
        if(pd==i)
           {k=k+1;
            if(k-n==0)
                  {printf("你要找的结点是");printf("%c\n",st[j].name);break;}
           }    
        }
     }    
}

void show()
{
	int i,a,b,qk,w,j,count;
	int left=0;
	int right=0;
	w=size;
	char ch;
	
	for(i=0;i<w;i++)
	{
		a=st[i].num;
		b=st[i+1].num;
		if(i==(w-1))
		{qk=4;}
		else if(a==b/10)
		{qk=1;}
		else if(a==(b-1))
		{qk=2;}
		else if(a>b)
		{qk=3;}
		switch(qk)
		{case 1:printf("%c",st[i].name);printf("(");break;
		 case 2:printf("%c",st[i].name);printf(",");break;
		 case 3:printf("%c",st[i].name);
				count=log10(a)-log10(b);
				for(j=count;j>=0;j--)
				{
					printf(")");
				}
				printf(",");break;
		 case 4:printf("%c",st[i].name);
				count=log10(st[i].num);
				for(j=count;j>0;j--)
				{printf(")");}
				break;
		}
	}
}