二叉树的基本运算btree.cpp

数据结构经典课件(附带各章的经典算法) 具体代码是使用C语言编写的

#include <stdio.h>
#include <malloc.h>
#define MaxSize 30
typedef char ElemType;
typedef struct node 
{	
	ElemType data;		
	struct node *lchild;
	struct node *rchild;	
} BTNode;
void CreateBTNode(BTNode * &b,char *str)
{
	BTNode *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=(BTNode *)malloc(sizeof(BTNode));
				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];
	}
}
char disp[10];
int k;

void preorder(BTNode *b)
{
  if(b!=NULL)
  { disp[k]=b->data ;k++;
    preorder(b->lchild);
	preorder(b->rchild);
  }
}

void inorder(BTNode *b)
{
  if(b!=NULL)
  { 
    inorder(b->lchild);
	disp[k]=b->data ;k++;
	inorder(b->rchild);
  }
}

void postorder(BTNode *b)
{
  if(b!=NULL)
  { 
    postorder(b->lchild);
	postorder(b->rchild);
	disp[k]=b->data ;k++;

  }
}
char pre0[]="abdcegf";
char ind0[]="dbaegcf";
char pre[]="abcdefghi";
char ind[]="cbdafhgie";

BTNode *creat(int l1,int h1,int l2,int h2)
{
    int k;
    BTNode *p;
    if(l1>h1) return(NULL);
    k=l2;
    while(ind[k]!=pre[l1])
       k++;
    p=(BTNode *)malloc(sizeof(BTNode));
    p->data=pre[l1];
    p->lchild=creat(l1+1,l1+k-l2,l2,k-1);
    p->rchild=creat(l1+k-l2+1,h1,k+1,h2);
    return(p);
}

int level(BTNode *b,ElemType x,int h)
{
  if(b==NULL)
	  return(0);
  if(b->data==x)
	  return(h);
  int L=level(b->lchild,x,h+1);
  if(L==0)
	  L=level(b->rchild,x,h+1);
  return(L);
}
void layer(BTNode *t)
{  BTNode *q[10];
   int front,rear;
   BTNode *p;
   p=t;k=0;
   front=-1;rear=0;
   q[rear]=p;
   while(front<rear)
     { front++;
       p=q[front];
	   disp[k]=p->data ;k++;
       if(p->lchild!=NULL)
	 { 
	   rear++;q[rear]=p->lchild;
	 }
       if(p->rchild!=NULL)
	 { 
	    rear++;q[rear]=p->rchild;
	 }
       }
}
void postorder1(BTNode *b)
{ BTNode *p;
  struct 
  { 
     BTNode *pt;
	 int tag;
  }stack[20];
  int top;
  k=0;
  top=-1;
  p=b;
  while(1)
   {  while(p!=NULL)
	{  top++;
	   stack[top].pt=p;
	   stack[top].tag=0;
	   p=p->lchild;
	}
      if(top==-1)
	    return;
      p=stack[top].pt;
	  if(stack[top].tag==0)
	  {stack[top].tag=1;
	   p=p->rchild;
	  }
	  else
	  {top--;
       disp[k]=p->data;  k++;
	   p=NULL;
	  }
   }
}
void inorder1(BTNode *b)
{ BTNode *p;
  BTNode *stack[20];
  int top;
  k=0;
  top=-1;
  p=b;
  while(1)
   {  while(p!=NULL)
	{  top++;
	   stack[top]=p;
	   p=p->lchild;
	}
      if(top==-1)
	    return;
      p=stack[top];
      top--;
      disp[k]=p->data;  k++;
      p=p->rchild;
   }
}
bool ancestor(BTNode *b,ElemType x)
{
	if(b==NULL)
		return false;
	if(b->data == x)
		return true;
	if(ancestor(b->lchild ,x)==true )
	{disp[k]=b->data;k++;
	 return true;
	}
	else if(ancestor(b->rchild,x)==true)
	{disp[k]=b->data;k++;
	 return true;
	}

}
BTNode *find(BTNode *b,ElemType x)
{  BTNode *p;
   if(b==NULL) 
	   return(NULL);
   if(b->data==x) 
	   return(b);
   p=find(b->lchild,x);
   if(p==NULL)
      p=find(b->rchild,x);
   return(p);
}

int leaf(BTNode *b)
{  int nl,nr;
   if(b==NULL) 
	   return(0);
   if(b->lchild ==NULL && b->rchild ==NULL)
      return(1);
   nl=leaf(b->lchild);
   nr=leaf(b->rchild);
   return(nl+nr);
}

void main()
{
	BTNode *b,*p;
	char s[]="a(b(d(,e)),c(f(,g(h,i))))";//"a(b(d,e),c(,f(g)))";
	CreateBTNode(b,s);
	int L=level(b,'d',1);
	b=creat(0,8,0,8);
	k=0;
	layer(b);
	k=0;disp[0]='\0';
	inorder1(b);

	bool bl=ancestor(b,'g');
	k=0;disp[0]='\0';
	preorder(b);
	k=0;disp[0]='\0';
	postorder1(b);
    p=find(b,'e');
}