// AVL(二叉平衡树)树的实现.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<stdio.h>
#include<math.h>
#define ElementType char
using namespace std;
typedef struct AVLNode *Position;
typedef Position AVLTree; //AVL树类型
typedef struct AVLNode
{
ElementType Data;
AVLTree Left;
AVLTree Right;
int Height;
}AVLNode;
//函数声明
int GetHeight(AVLTree A); //得到树的高度
void InorderTraversal(AVLTree BT); //递归中序遍历
void PreorderTraversal(AVLTree A); //递归前序遍历树
void PostorderTraversal(AVLTree BT);//递归后序遍历
void GetOrderPrintLeaves(AVLTree BT);//递归求叶子节点
AVLTree SingleLeftRotation(AVLTree A);//将A与B做左旋转,更新A.B的高度,返回根节点B
AVLTree SingleRightRotation(AVLTree A);//将A与B做右旋转,更新A.B的高度,返回根节点B
AVLTree DoubleLeftRightRotation(AVLTree A);
AVLTree DoubleRightLeftRotation(AVLTree A);
AVLTree Insert(AVLTree T, ElementType X);//将X插入到AVL树中,并且返回调整后的AVL树
int Max(int a, int b); //返回a与b的最大值
//函数定义
int GetHeight(AVLTree A) //求树的高度
{
int AL, AR, MAX;
while (A)
{
AL = GetHeight(A->Left);
AR = GetHeight(A->Right);
MAX = (AL>AR) ? AL : AR;
return (MAX + 1);
}
return 0;
}
void InorderTraversal(AVLTree BT)
{
if (BT)
{
InorderTraversal(BT->Left);
/* 此处假设对BT结点的访问就是打印数据 */
cout << BT->Data;/* 假设数据为整型 */
InorderTraversal(BT->Right);
}
}
void PreorderTraversal(AVLTree A) //递归前序遍历树
{
if (A)
{
cout << A->Data;
PreorderTraversal(A->Left);
PreorderTraversal(A->Right);
}
}
void PostorderTraversal(AVLTree BT)
{
if (BT)
{
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
cout << BT->Data;
}
}
void GetOrderPrintLeaves(AVLTree BT)
{
if (BT)
{
if (!BT->Left&&!BT->Right)
{
cout << BT->Data;
}
GetOrderPrintLeaves(BT->Left);
GetOrderPrintLeaves(BT->Right);
}
}
int Max(int a, int b)
{
return a>b ? a : b;
}
//LL型平衡调整,又称单向右旋平衡处理
AVLTree SingleLeftRotation(AVLTree A)//将A与B做左旋转,更新A.B的高度,返回根节点B
{//A必须有一个左子树结点B
AVLTree B = A->Left;
A->Left = B->Right;
B->Right = A;
A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height = Max(GetHeight(B->Left), A->Height) + 1;
return B;
}
//RR型平衡调整,又称单向左旋平衡处理
AVLTree SingleRightRotation(AVLTree A)//将A与B做右旋转,更新A.B的高度,返回根节点B
{//A必须有一个右子树结点B
AVLTree B = A->Right;
A->Right = B->Left;
B->Left = A;
A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
B->Height = Max(A->Height, GetHeight(B->Right)) + 1;
return B;
}
//LR型平衡调整,又称双向旋转(先左后右)平衡处理
AVLTree DoubleLeftRightRotation(AVLTree A)
{//A必须有一个左子结点B,且B必须有一个右子结点C,将A、B与C做两次单旋,返回新的根结点C
// 将B与C做右单旋,C被返回
A->Left = SingleRightRotation(A->Left);
//将A与C做左单旋,C被返回
return SingleLeftRotation(A);
}
//RL型平衡调整,又称双向旋转(向右后左)平衡处理
AVLTree DoubleRightLeftRotation(AVLTree A)
{//A必须有一个左子结点B,且B必须有一个右子结点C,将A、B与C做两次单旋,返回新的根结点C
// 将B与C做左单旋,C被返回
A->Right = SingleLeftRotation(A->Right);
//将A与C做右单旋,C被返回
return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T, ElementType X)//将X插入到AVL树中,并且返回调整后的AVL树
{
if (!T) //若插入空树,则新建包含一个结点的树
{
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->Data = X;
T->Height = 0;
T->Left = T->Right = NULL;
}
else if (X<T->Data) //插入T的左子树
{
T->Left = Insert(T->Left, X);
if (GetHeight(T->Left) - GetHeight(T->Right) == 2) //如果需要左旋
if (X<T->Left->Data)
T = SingleLeftRotation(T); //左单旋
else
T = DoubleLeftRightRotation(T);//左右双旋
}
else if (X>T->Data) //插入T的左子树
{
T->Right = Insert(T->Right, X);
if (GetHeight(T->Right) - GetHeight(T->Left) == 2)//如果需要左旋
if (X>T->Right->Data)
T = SingleRightRotation(T);//左单旋
else
T = DoubleRightLeftRotation(T);//左右双旋
}
T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;//更新树高
return T;
}
int _tmain(int argc, _TCHAR* argv[])
{
AVLTree AVL = NULL;
int e = 0;
char ch;
cout << "请输入要创建的AVL树的结点个数:";
cin >> e;
for (int i = 0; i < e; i++)
{
cin >> ch;
AVL = Insert(AVL, ch);
}
cout << "递归先序遍历:";
PreorderTraversal(AVL);
cout << endl;
cout << "递归中序遍历:";
InorderTraversal(AVL);
cout << endl;
cout << "递归后序遍历:";
PostorderTraversal(AVL);
cout << endl;
cout << "递归输出叶子结点:";
GetOrderPrintLeaves(AVL);
cout << endl;
cout << "请输入要插入的结点:";
cin >> ch;
AVL = Insert(AVL, ch);
cout << "递归先序遍历:";
PreorderTraversal(AVL);
cout << endl;
cout << "递归中序遍历:";
InorderTraversal(AVL);
cout << endl;
cout << "递归后序遍历:";
PostorderTraversal(AVL);
cout << endl;
cout << "递归输出叶子结点:";
GetOrderPrintLeaves(AVL);
cout << endl;
return 0;
}