#include<cstdio>
//平衡二叉树的结构体
typedef int elementType;
typedef struct AVLNODE
{
elementType data;
struct AVLNODE * left;
struct AVLNODE * right;
int height; //以此节点为根,树的高度;
unsigned int freq;//此节点保存的数据出现的频率
}AvlNode,*PtrToNode;
//函数声明
void AVL_Insert(PtrToNode & node,elementType x);
PtrToNode AVL_Find(PtrToNode & node,elementType x);
void AVL_Delete(PtrToNode &node,elementType x);
void print(PtrToNode & root) ;
int max(int a,int b);
int NodeHeight(PtrToNode ptrTree);
void RotateWithLeft(PtrToNode &k1);
void LeftBalance(PtrToNode &node);
void RightBalance(PtrToNode &node);
int main()
{
//C++引入的引用概念,可以直接对树的节点进行插入操作,而不用返回树的根节点
PtrToNode root =NULL;
/* for(int i=0;i<5;i++)
{
AVL_Insert(root,i);
}
*/
AVL_Insert(root,4);
AVL_Insert(root,2);
AVL_Insert(root,6);
AVL_Insert(root,1);
AVL_Insert(root,3);
AVL_Insert(root,5);
AVL_Insert(root,7);
AVL_Insert(root,16);
AVL_Insert(root,15);
print(root);
printf("\n%d\n",root->height);
AVL_Delete(root,15);
AVL_Delete(root,5);
print(root);
PtrToNode y=AVL_Find(root,15);
if (y==NULL)
{
printf("没有查找到15\n");
}
else
{
printf("所在节点的高度:%d\n",y->height);
if (NULL!=y->left)
{
printf("所在节点的左孩子:%d\n",y->left->data);
}
if (NULL!=y->right)
{