加载中…【C语言】平衡二叉树插入和删除操作演示代码
(2013-03-23 22:49:28)| 分类： 算法#C语言 |
#include
#include
//这里ElemType可以是整型(Int,Long)、浮点数(Float,Double)和字符(Char)
typedef int ElemType;
typedef struct TreeNode{
ElemType data;
struct TreeNode * lchild;
struct TreeNode * rchild;
}BiTreeNode,*BiTree;
void InitBiTree(ElemType elem,BiTree&
bt)
{
bt->data = elem;
bt->lchild = NULL;
bt->rchild = NULL;
}
void InsertBiTree(ElemType elem,BiTree&
bt)
{
if(bt == NULL) {
bt = (BiTree)malloc(sizeof(BiTreeNode));
bt->data = elem;
bt->lchild = NULL;
bt->rchild = NULL;
}
else{
if(elem>bt->data)
{
InsertBiTree(elem,bt->lchild);
}
else{
InsertBiTree(elem,bt->rchild);
}
}
}
int HightBiTree(BiTree bt)
{
int hight_left,hight_right;
if(bt == NULL) return 0;
else{
hight_left = 1 + HightBiTree(bt->lchild);
hight_right = 1 +
HightBiTree(bt->rchild);
if(hight_left>hight_right)
{
return hight_left;
}else
{
return hight_right;
}
}
}
void DisplayBiTree(BiTree bt)
{
if(bt != NULL){
printf("%d#",bt->data);
DisplayBiTree(bt->lchild);
DisplayBiTree(bt->rchild);
}
else return;
}
void AdjustBiTreeByLL(BiTree& bt)
{
BiTree lc = (BiTree)malloc(sizeof(BiTreeNode));
lc=bt->lchild;
//lc指向B
bt->lchild=lc->rchild;
//把B结点的右子树挂接为A的左子树
lc->rchild=bt;
//A结点成为B的右孩子
bt=lc;
//p指向新的根结点
}
void AdjustBiTreeByRR(BiTree& bt)
{
BiTree lc = (BiTree)malloc(sizeof(BiTreeNode));
lc=bt->rchild;
//lc指向B
bt->rchild=lc->lchild;
//把B结点的右子树挂接为A的左子树
lc->lchild=bt;
//A结点成为B的右孩子
bt=lc;
//p指向新的根结点
}
void AdjustBiTreeByLR(BiTree& bt)
{
BiTree b = (BiTree)malloc(sizeof(BiTreeNode));
BiTree c = (BiTree)malloc(sizeof(BiTreeNode));
b = bt->lchild;
c = bt->lchild->rchild;
bt->lchild=c->rchild;
b->rchild=c->lchild;
c->lchild=b;
c->rchild=bt;
bt = c;
}
void AdjustBiTreeByRL(BiTree& bt)
{
BiTree b = (BiTree)malloc(sizeof(BiTreeNode));
BiTree c = (BiTree)malloc(sizeof(BiTreeNode));
b = bt->rchild;
c = bt->rchild->lchild;
bt->rchild=c->lchild;
b->lchild=c->rchild;
c->rchild=b;
c->lchild=bt;
bt = c;
}
void AdjustAVLBiTree(BiTree& bt)
{
int bf,lbf,rbf;
bf = HightBiTree(bt->lchild) -
HightBiTree(bt->rchild);
if(bf == NULL) return;
if(bf>=2)
{
printf("\n\n这课二叉树不平衡，正在进行调整二叉树");
lbf =
HightBiTree(bt->lchild->lchild) -
HightBiTree(bt->lchild->rchild);
//属于LL型变换
if(lbf>=1){
printf("\n正在进行LL型变换\n");
AdjustBiTreeByLL(bt);
DisplayBiTree(bt);
}
//属于LR型变换
else if(lbf<=-1){
printf("\n正在进行LR型变换\n");
AdjustBiTreeByLR(bt);
DisplayBiTree(bt);
}
}else if(bf<=-2)
{
printf("\n\n这课二叉树不平衡，正在进行调整二叉树");
rbf =
HightBiTree(bt->rchild->lchild) -
HightBiTree(bt->rchild->rchild);
//属于RL型变换
if(rbf>=1)
{
printf("\n正在进行RL型变换\n");
AdjustBiTreeByRL(bt);
DisplayBiTree(bt);
}
//属于RR型变换
else if(rbf<=-1)
{
printf("\n正在进行RR型变换\n");
AdjustBiTreeByRR(bt);
DisplayBiTree(bt);
}
}
else{
if((bt->lchild==NULL)&&(bt->rchild==NULL))
{
return;
}
else{
if(bt->lchild !=NULL){
AdjustAVLBiTree(bt->lchild);
}
if(bt->rchild !=NULL){
AdjustAVLBiTree(bt->rchild);
}
}
}
}
bool DeleteBiTree(ElemType elem,BiTree&
bt)
{
bool flag,flagl,flagr;
BiTree temp = (BiTree)malloc(sizeof(BiTreeNode));
BiTree p = (BiTree)malloc(sizeof(BiTreeNode));
if(bt == NULL) return false;
else{
if(bt->data == elem)
{
if(bt->lchild!=NULL){
temp = bt->lchild;
while(temp->rchild!=NULL){
temp = temp->rchild;
}
if(temp->lchild == NULL)
{
printf("\n进行LR型删除!\n");
bt->data = temp->data;
temp = NULL;
}else{
printf("\n进行LRL型删除!\n");
bt->data = temp ->data;
p = temp->lchild;
temp->data = p->data;
temp->lchild = p->lchild;
temp->rchild = p->rchild;
}
}else {
//将bt置空
if(bt->rchild==NULL){
printf("\n进行NULL型删除!\n");
bt = NULL;
}else
{
temp = bt->rchild;
while(temp->lchild!=NULL){
temp = temp->lchild;
}
if(temp->rchild == NULL)
{
printf("\n进行RL型删除!\n");
bt->data = temp->data;
temp = NULL;
}else{
printf("\n进行RLR型删除!\n");
bt->data = temp ->data;
p = temp->rchild;
temp->data = p->data;
temp->lchild = p->lchild;
temp->rchild = p->rchild;
}
}
}
return true;
}else{
flagl = DeleteBiTree(elem,bt->lchild);
flagr = DeleteBiTree(elem,bt->rchild);
flag = flagl | flagr;
}
}
return flag;
}
void InsertAVLBiTree(ElemType elem,BiTree&
bt)
{
InsertBiTree(elem,bt);
AdjustAVLBiTree(bt);
}
void DeleteAVLBiTree(ElemType elem,BiTree&
bt)
{
printf("\n正在试图删除元素%d......\n",elem);
if(DeleteBiTree(elem,bt)) printf("\n删除%d成功!\n",elem);
else printf("\n删除%d失败!\n",elem);
AdjustAVLBiTree(bt);
}
void CreateAVLBiTree(ElemType arr[],BiTree&
bt)
{
int i;
printf("\n初始化二叉树:\n");
printf("\n插入元素%d\n",arr[0]);
InitBiTree(arr[0],bt);
printf("\n创建二叉树:\n");
for(i=1;i<12;i++){
printf("\n插入元素%d\n",arr[i]);
InsertBiTree(arr[i],bt);
AdjustAVLBiTree(bt);
}
}
int main()
{
BiTree bt = (BiTree)malloc(sizeof(BiTreeNode));
ElemType arr[256] = {49,12,32,4,78,10,7,5,99,20,77,56};
CreateAVLBiTree(arr,bt);
printf("\n显示:\n");
DisplayBiTree(bt);
DeleteAVLBiTree(10,bt);
printf("\n显示:\n");
DisplayBiTree(bt);
DeleteAVLBiTree(10,bt);
printf("\n显示:\n");
DisplayBiTree(bt);
return 0;
}
喜欢
0
赠金笔
后一篇：VB字符编码转换函数