平衡二叉树
废话不说，直接上码。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
typedef int RcdType;
typedef int Status;
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define LH +1
#define EH 0
#define RH -1
typedef struct BBSTNode { //平衡二叉树结构
RcdType data;
int bf; //节点平衡因子
struct BBSTNode *lchild, *rchild;
}*BBSTree; //平衡二叉树
void R_Rotate(BBSTree &p); //右旋
void L_Rotate(BBSTree &p); //左旋
void LeftBalance(BBSTree &T);
void RightBalance(BBSTree &T);
bool InsertAVL(BBSTree &T,RcdType e,bool &taller);
void InOrderTraverse(BBSTree T);
BBSTree SearchBBST(BBSTree &T,RcdType e);
void DeleteNode(BBSTree &p);
int main() {
BBSTree T=NULL;
bool taller;
int DeletePoint;
srand((unsigned)time(NULL));
cout << "生成一组随机数" << endl;
for (int i = 0; i <10; i++) {
int temp = rand()%100;
InsertAVL(T, temp, taller);
printf("%5d", temp);
}
cout << endl;
printf("生成一颗平衡二叉树，遍历平衡二叉树\n");
InOrderTraverse(T);
printf("\n");
printf("请输入要删除的节点\n");
scanf_s("%d",&DeletePoint);
BBSTree BT=SearchBBST(T, DeletePoint);
DeleteNode(BT);
printf("删除%d后遍历二叉树为\n",DeletePoint);
InOrderTraverse(T);
cout << endl;
cout << "请输入要插入的节点" << endl;
int InsertPoint;
cin >> InsertPoint;
InsertAVL(T,InsertPoint,taller);
cout << "添加节点"<<InsertPoint<< "后遍历顺序为";
cout << endl;
InOrderTraverse(T);
cout << endl;
}
void R_Rotate(BBSTree &p) { //对最小失衡树进行右旋调整
BBSTree lc = p->lchild; //lc指向p节点的的左孩子
p->lchild = lc->rchild; //lc节点的右子树作为p节点的左子树
lc->rchild = p; //p节点（原来的根节点）作为lc节点的右孩子
p = lc; //p指向新的根节点
}
void L_Rotate(BBSTree &p) { //对最小失衡树进行左旋调整
BBSTree rc = p->rchild; //rc指向p节点的右孩子
p->rchild = rc->lchild; //rc节点的左子树作为p节点的右子树
rc->lchild = p; //p节点（原根节点）作为rc节点的左孩子
p = rc; //p指向新的根节点
}
void LeftBalance(BBSTree &T) { //左平衡处理操作
BBSTree lc, rd;
lc = T->lchild;
switch (lc->bf)
{
case LH: //LL型
T->bf = lc->bf = EH;
R_Rotate(T);
break;
case RH: //LR型
rd = lc->rchild;
switch (rd->bf) //修改T及其左孩子的平衡因子
{
case LH:
T->bf = RH;
lc->bf = EH;
break;
case EH:
T->bf = lc->bf = EH;
break;
case RH:
T->bf = EH;
lc->bf = LH;
break;
}
rd->bf = EH;
L_Rotate(T->lchild);
R_Rotate(T);
break;
}
}
void RightBalance(BBSTree &T) { //右平衡调整
BBSTree rc, ld;
rc = T->rchild;
switch (rc->bf)
{
case RH:
T->bf = rc->bf = EH;
L_Rotate(T);
break;
case LH:
ld = rc->lchild;
switch (ld->bf)
{
case LH:
T->bf = EH;
rc->bf = RH;
break;
case EH:
T->bf = rc->bf = EH;
break;
case RH:
T->bf = LH;
rc->bf = EH;
break;
}
ld->bf = EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}
void InOrderTraverse(BBSTree T) { //中序遍历
if (T) {
InOrderTraverse(T->lchild);
printf("%5d",T->data);
InOrderTraverse(T->rchild);
}
}
bool InsertAVL(BBSTree &T, RcdType e, bool &taller) { //插入e到二叉树中
if (T == NULL) { //T为空，树长高
T = (BBSTree)malloc(sizeof(BBSTNode));
T->data = e;
T->bf = EH;
T->lchild = NULL;
T->rchild = NULL;
taller = TRUE;
}
else if (e == T->data) { //树中已经存在和e相同的节点
taller = FALSE;
return FALSE; //未插入
}
else if (e<T->data) { //插入到左子树
if (FALSE == InsertAVL(T->lchild, e, taller)) return FALSE;
if (TRUE==taller) {
switch (T->bf) //检查T的平衡因子
{
case LH:
LeftBalance(T);//原左高，左平衡处理
taller = FALSE;
break;
case EH:
T->bf = LH;
taller = TRUE;
break;
case RH:
T->bf = EH;
taller = FALSE;
break;
}
}
}
else{ //插入到右子树
if (FALSE == InsertAVL(T->rchild, e, taller)) return FALSE;
if (TRUE==taller) {
switch (T->bf)
{
case LH:
T->bf = EH;
taller = false;
break;
case EH:
T->bf=RH;
taller = FALSE;
break;
case RH:
RightBalance(T);
taller = FALSE;
break;
}
}
}
return TRUE;
}
void DeleteNode(BBSTree &p) {
//删除二叉树中的p节点，引用的形参p是实参要删除的p节点的双亲指向其的指针域
BBSTNode *q, *s;
q = p;
if (p->rchild == NULL) {
p = p->lchild;
free(q);
}
else if (p->lchild == NULL) {
p = p->rchild;
free(q);
}
else {
s = p->lchild;
while (s->rchild!=NULL) //寻找直接前驱
{
q = s;
s = s->rchild;
}
p->data = s->data;
if (q == p)
q->lchild = s->lchild;
else q->rchild = s->lchild;
free(s);
}
}
BBSTree SearchBBST(BBSTree &T, RcdType e) { //查找节点
if (T == NULL) return NULL;
if (T->data == e) return T;
if (T->data > e)
return SearchBBST(T->lchild,e);
return SearchBBST(T->rchild,e);
}
