c.cpp

用C＋＋编的关于二叉树的一些内容

#include<stdio.h>
#include<malloc.h>
#define maxsize 100
typedef char elemtype;
typedef struct node
{ elemtype data;
  struct node *lchild;
  struct node *rchild;
} binode;
void init_binode(binode *&b)//初始化二叉树
{
	b=(binode *)malloc(sizeof(binode));
	b->lchild=NULL;
	b->rchild=NULL;
}
void destroy_binode(binode *&b)//销毁二叉树
{
    if (b!=NULL)

	{
		destroy_binode(b->lchild);
	    destroy_binode(b->rchild);
	    free (b);
	}
	b=NULL;


	
	
}
 void create_binode(binode *&b,char *str)//用形式法输入树的各个结点
{
	binode *st[maxsize],*p=NULL;
	int top=-1,k,j=0;
	char ch;
	b=NULL;
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case'(':top++;st[top]=p;k=1;break;
		case')':top--;break;
		case',':k=2;break;
		default:p=(binode *)malloc(sizeof(binode));
		p->data=ch;p->lchild=p->rchild=NULL;
		if (b==NULL)
			b=p;
		else
		{ switch(k)
		{
           case 1:st[top]->lchild=p;break;
           case 2:st[top]->rchild=p;break;
		
		}
		
	}
		
}
		j++;
		ch=str[j];
	}
	}
void bitree_empty(binode *&b)//判断二叉树是否为空
 {
	 if (b!=NULL)
		 printf("二叉树不为空\n");

	 else
         printf("二叉树为空\n");
 }
binode *findnode(binode *b,elemtype x)//寻找值为Ｘ的结点，并返回
{
	binode *p;
	if(b==NULL)
		return NULL;
	else if(b->data==x)
		return b;
	else
	{
		p=findnode(b->lchild,x);
		if(p!=NULL)
			return p;
		else
			return findnode(b->rchild,x);
	}
}
binode *lchildnode(binode *p)//寻找结点的左孩子
{
	return p->lchild;
}
binode *rchildnode(binode *p)//寻找结点的右孩子
{
	return p->rchild;
}
int binodedepth(binode *b)//计算二叉树的深度
{
	int lchilddep,rchilddep;
	if(b==NULL)
		return(0);
	else
	{ lchilddep=binodedepth(b->lchild);
	  rchilddep=binodedepth(b->rchild);
      return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);
	}
}
void disp(binode *b)//输出二叉树
{
	if(b!=NULL)
	{  printf("%c",b->data);
	if (b->lchild!=NULL||b->rchild!=NULL)
	{  printf("(");
	   disp(b->lchild);
	   if(b->rchild!=NULL) printf(",");
	   disp(b->rchild);
	   printf(")");
	   }
	}
	
}
binode *root(binode *b)
{
	if (b!=NULL)
		return b;
	else
		return NULL;
}
elemtype value(binode *b,elemtype e)//寻找结点值为e的结点并返回其data值
{    binode *p;
	p=findnode(b,e);
	return p->data;
}
void assign(binode *b,elemtype e,elemtype val)//给结点重新赋值
{
	binode *p;
	p=findnode(b,e);
	p->data=val;
}
binode *parent(binode *b,elemtype e)//找双亲
{
   binode *q,*p;
   p=findnode(b,e);
    
	if  (b==NULL)
         return NULL;

 if(b->lchild==p||b->rchild==p)
		return b;

	{q=parent(b->lchild,e);
	if (q!=NULL)
		return q;
	else
		return parent(b->rchild,e);
	}
}
binode *lsibling(binode *b,elemtype e)//寻找左兄弟
{
	binode *p,*q;
	p=findnode(b,e);
	q=parent(b,e);
	if(p==NULL||q->lchild==p)
	return NULL;
	if(q->lchild==NULL)
		return NULL;
	else
		return q->lchild;
}
binode *rsibling(binode *b,elemtype e)//寻找右兄弟
{
	binode *p,*q;
	p=findnode(b,e);
q=parent(b,e);
	
	if (p==NULL||q->rchild==p)
		return NULL;
	else
		return q->rchild;
}
int nodes(binode *b)//计算结点数
{
	int num1,num2;
	if (b==NULL)
		return 0;
	else if(b->lchild==NULL&&b->rchild==NULL)
		return 1;
	else
	{	
		num1=nodes(b->lchild);
        num2=nodes(b->rchild);
	    return (num1+num2+1);
	}
}
int leafnodes(binode *b)//计算树的叶子结点
{
	int num1,num2;
	if  (b==NULL)
		return 0;
	else if (b->lchild==NULL&&b->rchild==NULL)
	return 1;
	else
	{
		num1=leafnodes(b->lchild);
		num2=leafnodes(b->rchild);
		return (num1+num2);
	}
}
void insertchild(binode *b,binode *p,int i,binode *c)//插入子树，插入的子树的右子树必须为空
{binode *m;
	if (b==NULL||c==NULL)
	{
		printf("输入的母树或子树不能为空\n");
    }
    else if  (i!=0&&i!=1)
    {
		printf("您必须选择子树插入为左子树（0）或者右子树（1）\n");
	}

	else if (c->rchild!=NULL)
	{
		printf("您输入的子树不符合右子树为空的规则\n");
	}
	else if (i==0)
	{   
		m=b->lchild;
		b->lchild=c;
		c->rchild=m;
	}
	else if (i==1)
	{
		m=b->rchild;
		b->rchild=c;
		c->rchild=m;
	}
}
void deletechild(binode *b,binode *p,int i)//删除树的左或者右孩子
{
	 if  (i!=0&&i!=1)
    {
		printf("您必须选择删除左子树（0）或者右子树（1）\n");
	}
	 else if (i==0)
	 {
		 p->lchild=NULL;
	 }
	 else if  (i==1)
	 {
         p->rchild=NULL;
	 }
}
void perordtra(binode *b)//前序遍历二叉树
{
	if  (b!=NULL)
	{
		printf("%c",b->data);
		perordtra(b->lchild);
		perordtra(b->rchild);
	}
}
void inordtra(binode *b)//中序遍历二叉树
{
	if (b!=NULL)
	{
		
		inordtra(b->lchild);
        printf("%c",b->data);
		inordtra(b->rchild);
	}
}
void posordtra(binode *b)//后序遍历二叉树
{
	if (b!=NULL)
	{
	
		posordtra(b->lchild);
		posordtra(b->rchild);
	   printf("%c",b->data);
	}
}
void travlevel(binode *b)
{
	binode *Qu[maxsize];
	int front,rear;
	front=rear=0;
	if(b!=NULL)
		printf("%c",b->data);
	rear++;
	Qu[rear]=b;
	while(rear!=front)
	{
		front=(front+1)%maxsize;
		b=Qu[front];
		if(b->lchild!=NULL)
		{printf("%c",b->lchild->data);
		rear=(rear+1)%maxsize;
		Qu[rear]=b->lchild;
		}
		if(b->rchild!=NULL)
		{
			printf("%c",b->rchild->data);
			rear=(rear+1)%maxsize;
			Qu[rear]=b->rchild;
		}
	}
	printf("\n");
}
void main()
{
	binode *b,*p,*lp,*rp,*o,*ls,*rs,*par,*c,*m;


    init_binode(b);
	printf("(1)现在输入形式化后的二叉树A(B(D,E(G)),C(,F))\n");
	create_binode(b,"A(B(D,E(G)),C(,F))");
    printf("(2)现在输出二叉树\n");
	disp(b);
    printf("\n");
	printf("(3)");

    bitree_empty(b);
	p=findnode(b,'B');
    printf("(4)结点H");
	if(p!=NULL)
	{
		lp=lchildnode(p);
		if(lp!=NULL)
			printf("左孩子为%c",lp->data);
		else
			printf("无左孩子");
       rp=rchildnode(p);
		if(rp!=NULL)
			printf("右孩子为%c",rp->data);
		else
			printf("无右孩子");
	}

      printf("\n");
	  printf("(5)此二叉树的深度为%d\n",binodedepth(b));
      printf("(6)此二叉树的结点数为%d\n",nodes(b));

      printf("(7)此二叉树的叶子结点数为%d\n",leafnodes(b));
printf("(8)把A重新赋值成K");

assign(b,'A','K');
printf("\n则此时树为");
disp(b);
printf("\n");
assign(b,'K','A');
printf("(8)现在删除结点A的左子树\n");

o=findnode(b,'A');

deletechild(b,o,0);

printf("结果为");

disp(b);
printf("\n");
printf("(9)现在销毁树ACF\n");

destroy_binode(b);
printf("(10)现在");
bitree_empty(b);
printf("(11)现在把树复原\n");
	create_binode(b,"A(B(D,E(G)),C(,F))");

	par=parent(b,'D');
printf("(12)D的父母为%c\n",par->data);
  rs=rsibling(b,'D');
    if (rs==NULL)
    printf("(13)F的右兄弟为空\n");
	else
     printf("(13)D的右兄弟为%c\n",rs->data);
  ls=lsibling(b,'F');
	if (ls==NULL)
       printf("(14)F的左兄弟为空\n");
	   else 

     printf("(14)F的左兄弟为%c\n",ls->data);

create_binode(c,"H(I(J,K))");
printf("(15)现在插入子树c=H(I(J,K))为根结点的左子树，原来根结点的左子树为c的右子树\n");
m=findnode(b,'A');
 insertchild(b,p,0,c);
printf("(16)此时的树为");
 disp(b);
printf("\n");
printf("(17)前序遍历树");
perordtra(b);
printf("\n");
printf("(18)中序遍历树");
inordtra(b);
printf("\n");
printf("(19)后序遍历树");
posordtra(b);
printf("\n");
printf("(20)层次遍历二叉树");
travlevel(b);
printf("\n");
}