怎么平衡二叉树不能实现(烦了)
#define LH 1
#define EH 0
#define RH -1
typedef struct BSTNode{
int data;
int bf;
struct BSTNode *lchild;
struct BSTNode *rchild;
}BSTNode,*BSTree;
void R_Rotate(BSTree *p)
{ BSTree *lc ;
(*lc)=(*p)-> lchild;
(*p)-> lchild=(*lc)-> rchild;
(*lc)-> rchild=(*p);(*p)=(*lc);
}
void L_Rotate(BSTree *p)
{ BSTree *rc ;
(*rc)=(*p)-> rchild;
(*p)-> rchild=(*rc)-> lchild;
(*rc)-> lchild=(*p);(*p)=(*rc);
}
int insertavl(BSTree *root,int key,int taller)
{ if(!*root){
*root=(BSTree)malloc(sizeof(BSTNode));(*root)-> data=key;
(*root)-> lchild=(*root)-> rchild=NULL;(*root)-> bf=EH; taller=1;
}
else{
if(key==(*root)-> data) { taller=0; return 0;}
if(key <(*root)-> data)
{ if(!insertavl(&((*root)-> lchild), key,taller)) return 0;
if(taller)
switch((*root)-> bf)
{ case LH: Leftbalance(&(*root)); taller=0; break;
case EH: (*root)-> bf=LH; taller=1; break;
case RH: (*root)-> bf=EH; taller=0; break;
}
}
else{
if(!insertavl(&((*root)-> rchild), key,taller)) return 0;
if(taller)
switch((*root)-> bf)
{ case LH: (*root)-> bf=EH; taller=0; break;
case EH: (*root)-> bf=RH; taller=1; break;
case RH: Rightbalance(&(*root)); taller=0; break;
}
}
}
return 1;
}
int Leftbalance(BSTree *root)
{ BSTree *lc,*rd;
(*lc)=(*root)-> lchild;
switch((*lc)-> bf)
{ case LH: (*root)-> bf=(*lc)-> bf=EH;
R_Rotate(&(*root)) ; break;
case RH: (*rd)=(*lc)-> rchild;
switch((*rd)-> bf)
{ case LH: (*root)-> bf=RH; (*lc)-> bf=EH; break;
case EH: (*root)-> bf=(*lc)-> bf=EH; break;
case RH: (*root)-> bf=EH; (*lc)-> bf=LH; break;
}
(*rd)-> bf=EH;
L_Rotate(&((*root)-> lchild));
R_Rotate(&(*root)) ; break;
}
return 1;
}
int Rightbalance(BSTree *root)
{ BSTree *rc,*ld;
(*rc)=(*root)-> rchild;
switch((*rc)-> bf)
{ case LH: (*ld)=(*rc)-> lchild;
switch((*ld)-> bf)
{ case LH: (*root)-> bf=EH; (*rc)-> bf=RH; break;
case EH: (*root)-> bf=(*rc)-> bf=EH; break;
case RH: (*root)-> bf=LH; (*rc)-> bf=EH; break;
}
(*ld)-> bf=EH;
R_Rotate(&((*root)-> rchild));
L_Rotate(&(*root)) ; break;
case RH: (*root)-> bf=(*rc)-> bf=EH;
L_Rotate(&(*root)) ; break;
}
return 1;
}
void main()
{ int flag,key,m; int *k;
static int taller;
clrscr();
gotoxy(20,5); printf( "please input a series numbers end of ↙: ");
scanf( "%d ",&key);
g=NULL;
while(key!=0)
{ insertavl(&g, key, taller);
scanf( "%d ",&key);
}
}怎么得出的结果不正确?
------解决方案--------------------
有種技術叫做調試，有種能力叫做Debug
[解决办法]
//在WinTC下一大堆指针未初始化错误
//帮你修改了一下，WinTC编译通过，建议你给指针分配空间
#define LH 1
#define EH 0
#define RH -1
#define NULL (void *)0
typedef struct BSTNode{
int data;
int bf;
struct BSTNode *lchild;
struct BSTNode *rchild;
}BSTNode,*BSTree;
void R_Rotate(BSTree *p)
{ BSTree *lc=NULL ;
(*lc)=(*p)-> lchild;
(*p)-> lchild=(*lc)-> rchild;
(*lc)-> rchild=(*p);(*p)=(*lc);
}
void L_Rotate(BSTree *p)
{ BSTree *rc=NULL ;
(*rc)=(*p)-> rchild;
(*p)-> rchild=(*rc)-> lchild;
(*rc)-> lchild=(*p);(*p)=(*rc);
}
int insertavl(BSTree *root,int key,int taller)
{ if(!*root){
*root=(BSTree)malloc(sizeof(BSTNode));(*root)-> data=key;
(*root)-> lchild=(*root)-> rchild=NULL;(*root)-> bf=EH; taller=1;
}
else{
if(key==(*root)-> data) { taller=0; return 0;}
if(key <(*root)-> data)
{ if(!insertavl(&((*root)-> lchild), key,taller)) return 0;
if(taller)
switch((*root)-> bf)
{ case LH: Leftbalance(&(*root)); taller=0; break;
case EH: (*root)-> bf=LH; taller=1; break;
case RH: (*root)-> bf=EH; taller=0; break;
}
}
else{
if(!insertavl(&((*root)-> rchild), key,taller)) return 0;
if(taller)
switch((*root)-> bf)
{ case LH: (*root)-> bf=EH; taller=0; break;
case EH: (*root)-> bf=RH; taller=1; break;
case RH: Rightbalance(&(*root)); taller=0; break;
}
}
}
return 1;
}
int Leftbalance(BSTree *root)
{ BSTree *lc=NULL,*rd=NULL;
(*lc)=(*root)-> lchild;
switch((*lc)-> bf)
{ case LH: (*root)-> bf=(*lc)-> bf=EH;
R_Rotate(&(*root)) ; break;
case RH: (*rd)=(*lc)-> rchild;
switch((*rd)-> bf)
{ case LH: (*root)-> bf=RH; (*lc)-> bf=EH; break;
case EH: (*root)-> bf=(*lc)-> bf=EH; break;
case RH: (*root)-> bf=EH; (*lc)-> bf=LH; break;
}
(*rd)-> bf=EH;
L_Rotate(&((*root)-> lchild));
R_Rotate(&(*root)) ; break;
}
return 1;
}
int Rightbalance(BSTree *root)
{ BSTree *rc=NULL,*ld=NULL;
(*rc)=(*root)-> rchild;
switch((*rc)-> bf)
{ case LH: (*ld)=(*rc)-> lchild;
switch((*ld)-> bf)
{ case LH: (*root)-> bf=EH; (*rc)-> bf=RH; break;
case EH: (*root)-> bf=(*rc)-> bf=EH; break;
case RH: (*root)-> bf=LH; (*rc)-> bf=EH; break;
}
(*ld)-> bf=EH;
R_Rotate(&((*root)-> rchild));
L_Rotate(&(*root)) ; break;
case RH: (*root)-> bf=(*rc)-> bf=EH;
L_Rotate(&(*root)) ; break;
}
return 1;
}
void main()
{ int flag,key,m;
int *k;
static int taller;
BSTree g;
clrscr();
gotoxy(20,5); printf( "please input a series numbers end of ↙: ");
scanf( "%d ",&key);
g=NULL;
while(key!=0)
{ insertavl(&g, key, taller);
scanf( "%d ",&key);
}
}
[解决办法]
路过!!!
[解决办法]
//平衡二叉树的实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct node
{
int data;
int blance;
struct node * left;
struct node * right;
}node_t, * node_tp;
static node_tp avl_tab_p = NULL;
void init_node(node_tp node, int data)
{
if(node)
{
node->data = data;
node->blance = 0;
node->left = NULL;
node->right = NULL;
}
}
void free_tab_s(node_tp node)
{
if(!node)
return;
free_tab_s(node->left);
free_tab_s(node->right);
printf("\nfree data=%d", node->data);
free(node);
}
void free_tab(void)
{
free_tab_s(avl_tab_p);
avl_tab_p = NULL;
}
node_tp find_node(node_tp node, int data)
{
if(!node)
return node;
else if(node->data > data)
return find_node(node->left, data);
else if(node->data < data)
return find_node(node->right, data);
else
return node;
}
int node_depth(node_tp node, int * blance)
{
int l, r;
if(!node)
return 0;
l = node_depth(node->left, blance);
r = node_depth(node->right,blance);
if(blance && (l - r > 1 || l - r < -1))
{
*blance = 0;
printf("\ncha=%d, %d", l-r, node->data);
}
return 1 + ((l > r)? l:r);
}
int travesal_mid_s(node_tp node)
{
int l, r;
if(!node)
return 0;
l = travesal_mid_s(node->left);
printf(" %d(blance=%d depth=%d,) ", node->data, node->blance,node_depth(node,NULL));
r = travesal_mid_s(node->right);
return l + r + 1;
}
void travesal_mid(void)
{
int blance = 1;
int depth = node_depth(avl_tab_p, &blance);
int count;
printf("\n---tree is:--------\n");
count = travesal_mid_s(avl_tab_p);
printf("\n-----count=%d----depth=%d----blance=%d-----------", count, depth, blance);
}
node_tp max_node(node_tp node)
{
if(!node || !node->right)
return node;
return max_node(node->right);
}
node_tp left_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->right && node->right->right)
{
p = node->right;
node->right = p->left;
p->left = node;
if(p->blance == 0)
{
p->blance = -1;
p->left->blance = 1;
}
else
{
p->blance = 0;
p->left->blance = 0;
}
}
return p;
}
node_tp right_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->left && node->left->left)
{
p = node->left;
node->left = p->right;
p->right = node;
if(p->blance == 0)
{
p->blance = 1;
p->right->blance = -1;
}
else
{
p->blance = 0;
p->right->blance = 0;
}
}
return p;
}
node_tp left_right_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->left && node->left->right)
{
p = node->left->right;
node->left->right = p->left;
p->left = node->left;
node->left = p->right;
p->right = node;
switch(p->blance)
{
case -1:
p->left->blance = p->blance = 0;
p->right->blance = 1;
break;
case 0:
p->left->blance = p->right->blance = p->blance = 0;
break;
case 1:
p->left->blance = -1;
p->blance = p->right->blance = 0;
break;
default:
break;
}
}
return p;
}
node_tp right_left_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->right && node->right->left)
{
p = node->right->left;
node->right->left = p->right;
p->right = node->right;
node->right = p->left;
p->left = node;
switch(p->blance)
{
case -1:
p->left->blance = p->blance = 0;
p->right->blance = 1;
break;
case 0:
p->blance = p->left->blance = p->right->blance = 0;
break;
case 1:
p->blance = p->right->blance = 0;
p->left->blance = -1;
break;
default:
break;
}
}
return p;
}
[解决办法]
路过 头晕 帮顶
