平衡二叉搜索树/AVL二叉树 C实现

//AVTree.h

 #ifndef MY_AVLTREE_H

 #define MY_AVLTREE_H

 typedef int ElementType;

 struct TreeNode

 {

     ElementType data;

     struct TreeNode *left;

     struct TreeNode *right;

     int height;

 };

 typedef struct TreeNode TreeNode;

 typedef TreeNode *Tree;

 Tree Find(ElementType e,Tree t);

 Tree Insert(ElementType e,Tree t);

 Tree Create();

 //int Destroy();//这个没写。。。自己写下吧

 Tree LeftRotate(Tree t);

 Tree RightRotate(Tree t);

 int Height(Tree t);

 void Show(Tree t);

 #endif

//AVLTree.cpp

 #include <stdlib.h>

 #include <stdio.h>

 #include "AVLTree.h"

 #define MAX(a,b) ((a)>(b)?(a):(b))

 Tree Create()

 {

     Tree t=(Tree)malloc(sizeof(TreeNode));

     if(NULL==t)

     {

         printf("内存分配错误\n");

         return NULL;

     }

     t->data=;

     t->left=NULL;

     t->right=NULL;

     t->height=;

     return t;

 }

 Tree Find(ElementType e,Tree t)

 {

     if(NULL==t)

         return NULL;

     if(e==t->data)

         return t;

     else if(e>t->data)

         return Find(e,t->right);

     else

         return Find(e,t->left);

 }

 int Height(Tree t)

 {

     if(NULL==t)

         return -;

     else

         return t->height;

 }

 Tree LeftRotate(Tree t)

 {

     if(NULL==t)

         return NULL;

     Tree newtree=t->right;

     t->right=newtree->left;

     newtree->left=t;

     t->height=MAX(Height(t->left),Height(t->right))+;

     newtree->height=MAX(Height(newtree->left),Height(newtree->right))+;

     return newtree;

 }

 Tree RightRotate(Tree t)

 {

     if(NULL==t)

         return NULL;

     Tree newtree=t->left;

     t->left=newtree->right;

     newtree->right=t;

     t->height=MAX(Height(t->left),Height(t->right))+;

     newtree->height=MAX(Height(newtree->left),Height(newtree->right))+;

     return newtree;

 }

 Tree Insert(ElementType e,Tree t)

 {

     if(NULL==t)

     {

         Tree first=(Tree)malloc(sizeof(TreeNode));

         if(NULL==first)

         {

             printf("内存分配错误\n");

             return NULL;

         }

         first->left=NULL;

         first->right=NULL;

         first->height=;

         first->data=e;

         return first;

     }

     if(e==t->data)

         {

             printf("元素已存在\n");

             return t;

         }

     if(e>t->data)

     {

         t->right=Insert(e,t->right);

         int left=Height(t->left);

         int right=Height(t->right);

         if(right-left==)

             if (e<t->right->data)

             {

                 t->right=RightRotate(t->right);

                 t=LeftRotate(t);

             }

             else

                 t=LeftRotate(t);

     }

     else

     {

         t->left=Insert(e,t->left);

         int left=Height(t->left);

         int right=Height(t->right);

         if(left-right==)

             if (e>t->left->data)

             {

                 t->left=LeftRotate(t->left);

                 t=RightRotate(t);

             }

             else

                 t=RightRotate(t);

     }

     t->height=MAX(Height(t->left),Height(t->right))+;

     return t;

 }

 void Show(Tree t)

 {

     if(t==NULL)

         return;

     Show(t->left);

     printf("%d ",t->data);

     Show(t->right);

     return;

 }

平衡二叉搜索树/AVL二叉树 C实现的相关教程结束。