avl.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/*************************************************/
/*       平衡二叉树相关算法   文件名：AVL.C      */
/*  函数名：lchange()、rchange()、insertavltree()*/
/*************************************************/
#include<stdio.h>
#include<stdlib.h>
#include "AVL.H"
/*------------进行左改组-------------*/
void lchange(bstree *t)
{ bstree p1,p2;
  p1=(*t)->lchild;
  if (p1->bal==1)
      {        /*  LL改组  */
	  (*t)->lchild=p1->rchild;
	  p1->rchild=*t;
	  (*t)->bal=0;
	  (*t)=p1;
       }
    else
       {       /*  LR改组  */
         p2=p1->rchild;
         p1->rchild=p2->lchild;
         p2->lchild=p1;
	 (*t)->lchild=p2->rchild;
	 p2->rchild=*t;
	 if (p2->bal==1) {(*t)->bal=-1; p1->bal=0;} /*调整平衡度*/
		 else    {(*t)->bal=0;  p1->bal=1;}
	 (*t)=p2;
        }
     (*t)->bal=0;
}
/*------------进行右改组----------------*/
void rchange(bstree *t)
{ bstree p1,p2;
  p1=(*t)->rchild;
  if (p1->bal==-1)
        {     /*RR改组*/
	     (*t)->rchild=p1->lchild;
	     p1->lchild=*t;
	     (*t)->bal=0;
	     (*t)=p1;
         }
      else
         {   /*RL改组*/
            p2=p1->lchild;
            p1->lchild=p2->rchild;
            p2->rchild=p1;
	    (*t)->rchild=p2->lchild;
	    p2->lchild=(*t);
	    if (p2->bal==-1)  {(*t)->bal=1; p1->bal=0;} /*调整平衡度*/
		   else       {(*t)->bal=0; p1->bal=-1;}
	    (*t)=p2;
         }
      (*t)->bal=0;
 }

/*---------平衡二叉树的插入算法----------*/
void insertavltree(datatype x, bstree *t,int * h)
{
  if (*t==NULL)
	{ *t=(bstree)malloc(sizeof(bsnode));  /*生成根结点*/
	  (*t)->key=x;
	  (*t)->bal=0;
          *h=1;
	  (*t)->lchild=(*t)->rchild=NULL;
        }
     else
      if (x<(*t)->key)        /*在左子树中插入新结点*/
          {
	    insertavltree(x,&(*t)->lchild,h);
	    if (*h)   /*左子树中插入了新结点*/
	      switch( (*t)->bal)
		{ case -1: {(*t)->bal=0;*h=0;break;}
		  case 0:  {(*t)->bal=1;break;}
                  case 1:  {/*进行左改组*/
			    lchange(t);
			    *h=0;
                            break;
                           }
                 }
           }
        else
	   if (x>(*t)->key)   /*在右子树中插入新结点*/
	    { insertavltree(x,&(*t)->rchild,h);
	      if (*h)  /*右子树中插入了新结点*/
		 switch((*t)->bal)
		    { case 1:{ (*t)->bal=0;*h=0;break;}
		      case 0:{ (*t)->bal=-1;break;}
                      case -1:{/*进行右改组*/
			       rchange(t);
			       *h=0;
                               break;
                               }
                     }
            }
          else
	     *h=0;
 }
/*----前序遍历二叉树----*/
void preorder(bstree t)
{ if (t) {printf("%4d",t->key);
	  preorder(t->lchild);
	  preorder(t->rchild);
	  }
}

/*----中序遍历二叉树----*/
void inorder(bstree t)
  { if (t) {inorder(t->lchild);
	      printf("%4d",t->key);
              inorder(t->rchild);
             }

   }
/******************************/
 main()     /*主程序*/
  { bstree p,q;
    bstree t=NULL;
    int i,n,h=0;
    datatype x;
    printf("\nPlease input n:\n");
    scanf("%d",&n);
    printf("\nPlease input %d data:",n);/*输入n个关键字*/
    for  (i=0;i<n;i++)
         { scanf("%d",&x);
	   insertavltree(x,&t,&h);
          }
    printf("Preorder is:");
    preorder(t);
    printf("\nInorder is:");
    inorder(t);
 }