[数据结构与算法]平衡二叉树

#ifndef _AVL_TREE_H__
#define _AVL_TREE_H__
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int ETYPE;

typedef struct AVLNode{
	ETYPE elem;
	struct AVLNode *lchild,*rchild;
	size_t hight;   //结点所在高度  
}AVLNode,*AVLTree;
void avl_tree_init(AVLTree *proot);//初始化
bool avl_tree_empty(AVLTree root);//判断是否为空
size_t avl_tree_size(AVLTree root);//元素的个数
size_t avl_tree_hight(AVLTree root);//树的高度
int avl_tree_insert(AVLTree *proot,ETYPE elem);//插入元素
int avl_tree_delete(AVLTree *proot,ETYPE elem);//删除元素

void avl_tree_front_travel(AVLTree root,void (*travel)(ETYPE));//前序遍历
void avl_tree_mid_travel(AVLTree root,void (*travel)(ETYPE));//中序遍历
void avl_tree_back_travel(AVLTree root,void (*travel)(ETYPE));//后序遍历
void avl_tree_clear(AVLTree *proot);//清空数据
void avl_tree_destroy(AVLTree *proot);//销毁树

#endif //_VAL_TREE_H__

#include "avltree.h"
/*
typedef int ETYPE;
typedef struct AVLNode{
	ETYPE elem;
	struct AVLNode *lchild,*rchild;
	size_t hight;   //结点所在高度 
}AVLNode,*AVLTree;
*/

#define HIGHT(node) (node==NULL?0:node->hight)
#define REHIGHT(node) (HIGHT(node->lchild)>HIGHT(node->rchild)?HIGHT(node->lchild)+1:HIGHT(node->rchild)+1)

void avl_tree_init(AVLTree *proot){
	*proot = NULL; 
}
bool avl_tree_empty(AVLTree root){
	return root == NULL;
}
size_t avl_tree_size(AVLTree root){
	if(root==NULL)
		return 0;
	return 1+avl_tree_size(root->lchild)+avl_tree_size(root->rchild);
}
size_t avl_tree_hight(AVLTree root){
	return root==NULL?0:root->hight;
}

static struct AVLNode *avl_tree_create_node(ETYPE elem){
	struct AVLNode *node = malloc(sizeof(struct AVLNode));
	if(node!=NULL){
		node->elem = elem;
		node->lchild = NULL;
		node->rchild = NULL;
		node->hight = 1;
	}
	return node;
}
/*
          |                                  |
		node                               left 
	    /  \                              /   \
    left    right  			  右旋      ll     node
    / \                                        /  \
   ll  lr                                     lr   right
*/

static struct AVLNode *LL_rotation(struct AVLNode *node){
	struct AVLNode *left = node->lchild;
	node->lchild = left->rchild;
	left->rchild = node;
	node->hight = REHIGHT(node);
	left->hight = REHIGHT(left);
	return left;
}

/*
        |                                 |
       node                             right
      /    \                            /   \
    left   right          左旋        node   rr
           / \                        /  \
          rl  rr                    left  rl
*/

static struct AVLNode *RR_rotation(struct AVLNode *node){
	struct AVLNode *right = node->rchild;
	node->rchild = right->lchild; 
	right->lchild = node;
	node->hight = REHIGHT(node);
	right->hight = REHIGHT(right);
	return right;
}
/*
          |
         node
        /   \
      left   right
      / \
    ll  lr
*/

static struct AVLNode *LR_rotation(struct AVLNode *node){
	node->lchild = RR_rotation(node->lchild);
	return LL_rotation(node); 
}
/*
          |
         node
        /   \
      left   right
             / \
            rl  rr
*/
static struct AVLNode *RL_rotation(struct AVLNode *node){
	node->rchild = LL_rotation(node->rchild);
	return RR_rotation(node);
}

static void avl_tree_inset_repair(AVLTree *proot){
	struct AVLNode *node = *proot;
	int bn = HIGHT(node->lchild) - HIGHT(node->rchild);
	if(bn==2){//左高 
		int lbn = HIGHT(node->lchild->lchild) - HIGHT(node->lchild->rchild);
		if(lbn==1){
			*proot = LL_rotation(node);//对node结点进行右旋   LL 
		}else{//lbn==-1
			*proot = LR_rotation(node);//LR
		}
	}else if(bn==-2){//右高 
		int rbn = HIGHT(node->rchild->lchild) - HIGHT(node->rchild->rchild);
		if(rbn==-1){
			*proot = RR_rotation(node);//RR
		}else{
			*proot = RL_rotation(node);//RL
		}
	}
}
int avl_tree_insert(AVLTree *proot,ETYPE elem){
	//先把结点插入进去   如果失去平衡进行调整(旋转)   递归形式 
	if(*proot == NULL){
		*proot = avl_tree_create_node(elem);
		if(*proot == NULL){
			return -2;
		}
		return 0;
	} 
	int ret = 0;
	if(elem < (*proot)->elem){
		ret = avl_tree_insert(&(*proot)->lchild,elem);
	}else if(elem > (*proot)->elem){
		ret = avl_tree_insert(&(*proot)->rchild,elem);
	}else{
		return -1;
	}
	if(ret == 0){//插入成功  可能失衡  需要调整 
		avl_tree_inset_repair(proot); 
		(*proot)->hight = REHIGHT((*proot));
	}
	return ret;
}
int avl_tree_delete(AVLTree *proot,ETYPE elem){
	
}

void avl_tree_front_travel(AVLTree root,void (*travel)(ETYPE)){
	if(root!=NULL){
		travel(root->elem);
		avl_tree_front_travel(root->lchild,travel);
		avl_tree_front_travel(root->rchild,travel);
	}
}
void avl_tree_mid_travel(AVLTree root,void (*travel)(ETYPE)){
	if(root!=NULL){
		avl_tree_mid_travel(root->lchild,travel);
		travel(root->elem);
		avl_tree_mid_travel(root->rchild,travel);
	}
}
void avl_tree_back_travel(AVLTree root,void (*travel)(ETYPE)){
	if(root!=NULL){
		avl_tree_back_travel(root->lchild,travel);
		avl_tree_back_travel(root->rchild,travel);
		travel(root->elem);
	}	
}
void avl_tree_clear(AVLTree *proot){
	if(*proot!=NULL){
		avl_tree_clear(&(*proot)->lchild);
		avl_tree_clear(&(*proot)->rchild);
		free(*proot);
		*proot = NULL;
	}
}
void avl_tree_destroy(AVLTree *proot){
	avl_tree_clear(proot);
}