AVLTree的实现与分析

#include “stdio.h“
#include “stdlib.h“
#include “time.h“
#define  MAXSIZE 1000
#define  true  1
#define  false 0

typedef struct anode{
	int elem;
	int bf;
	struct anode *lchild;
	struct anode *rchild;
}AVLNode*AVLTree;
//平衡二叉排序树的数据结构


typedef struct{
	AVLTree data[MAXSIZE];
	int frontrear;
}sepQueue*PsepQueue;
//队列元素为指向树的指针

typedef struct node{
	AVLTree data;
	struct node * next;
}linkstack*Plinkstack;

typedef struct{
	Plinkstack top;
}stack*Pstack;
//以上的两个数据结构是链式栈的结构



int AVLTree_Insert（AVLTree *tAVLTree s）;
/*
*平衡二叉排序树的节点插入s为要插入的节点
*
*返回true表示插入数据成功false表示插入数据失败
*/


void levelOrder（AVLTree t）;
/*
*层次法遍历一棵二叉树
*
*此层次法遍历 <“优点“> 在于能够完全的显示一棵树
*/

PsepQueue Init_sepQueue（）;
//队的初始化

int empty_sepQueue（PsepQueue Q）;
//判断队是否为空

int full_sepQueue（PsepQueue Q）;
//判断队是否满

int push_sepQueue（PsepQueue QAVLTree data）;
//新队员入队

int pop_sepQueue（PsepQueue Q AVLTree *data）;
//队员出队

void Destory_sepQueue（PsepQueue *Q）;
//销毁队列

void visit（AVLTree t）;
//访问节点


AVLTree LL_Rotate（AVLTree a）;
/*                                        A
*对二叉排序树进行“左左”调整            / \
*                                       B   #
*原因在于:a->bf=2b->bf=1              / \ 
*                                     #   #
*/


AVLTree LR_Rotate（AVLTree a）;
/*                                     A
*对二叉排序树进行“左右”调整         / \
*                                    B   #
*原因在于:a->bf=2b->bf=-1          / \
*                                  #   C
*                                     / \
*                                    #   #
*/

AVLTree RL_Rotate（AVLTree a）;
/*                                         A
*对二叉排序树进行“右左”调整             / \
*                                        #   B
*原因在于:a->bf=-2b->bf=1                  / \
*                                          C   #
*                                         / \
*                                        #   #
*/                                        

AVLTree RR_Rotate（AVLTree a）; 
/*                                      A
*对二叉排序树进行“右右”调整          / \ 
*                                     #   B
*原因在于:a->bf=-2b->bf=-1              / \
*                                       #   #
*/                                    



void Rotate（AVLTree *tAVLTree a）;
/*
*调整节点的平衡包括了各种需要调节的情况
*
*此算法的优点在于 <“屏蔽“> 所有的旋转调节的情况
*/


void InOrder（AVLTree t）;
/*中序遍历二叉树*/


int locate_AVLNode（AVLTree *tAVLTree sAVLTree *faAVLTree *a）;
/*
*在平衡二叉排序树中插入一个新的节点
*
*入口参数a:最小不平衡因子;fa是a的双亲;t是待查树;s为待插入的节点
*
*返回true表示查找并且插入成功false表示失败
*/


void adjust_AVLTree_bf（AVLTree *aAVLTree s）;
/*
*插入数据后调节最小不平衡路径上的平衡因子
*
*入口参数a为最小不平衡因子s用于找路径
*/


int TreeHigh（AVLTree t）;
/*求解树的高度*/


int Delete_AVLTree_elem（AVLTree *tint kAVLTree *s）;
/*
*删除二叉排序树中的节点（仅仅只是删除节点）
*
*入口参数s用于存放需要删除节点的双亲
*
*返回true表示删除数据成功false表示删除数据失败; <“s是输出型的节点“>方便以后调节不平衡因子
*/


int AVLTree_Delete（AVLTree *tint k）;
/*