c - 平衡 BST 与四种情况 RR LL LR RL

Question

我已经编写了一个平衡 BST 的代码，但我无法在 BST 中添加超过 5 个元素!我们有 3 种情况，我们从不平衡的节点到我们想要插入它的节点进行 RR，当我添加 5 个节点时，这段代码工作正常..但是如果我添加更多节点，它会给我 overStack ..这是代码

#include"iostream"
using namespace std;
struct node{
    int x;
    node*left;
    node*right;
};
int max(int x,int y){
    if(x>y)return x;return y;
}
int depth(node*T){ // returns the depth of the BST
    if(!T)return 0;
    return max(depth(T->left),depth(T->right))+1;
}
int isBalance(node*T){   //check if the BST is Balanced or not
    return abs(depth(T->left)-depth(T->right))<=1;
}
int Expresion(char*x){ // for switch case
    if(!strcmp(x,"RR"))return 3;
    if(!strcmp(x,"LL"))return 2;
    if(!strcmp(x,"RL"))return 1;
    if(!strcmp(x,"LR"))return 0;
    return -1;
}
node* getBalance(node*T,char*x){   //Balance the node
    node*temp=NULL;
    node*temp1=NULL;
    node*z=NULL;
    switch(Expresion(x)){
    case 0:
        temp=T->left;
        temp1=temp->right;
        z = (temp1->right!=NULL)?temp1->right:temp1->left;
        temp1->right=T;
        T->left=z;
        temp->right=NULL;
        return temp1;
        break;
    case 1:
        temp=T->right;
        temp1=temp->left;
        z = (temp1->right!=NULL)?temp1->right:temp1->left;
        temp1->left=T;
        T->right=z;
        temp->left=NULL;
        return temp1;
        break;
    case 2:
        temp=T->left;
        temp1=temp->left;
        temp->right=T;
        temp->left=temp1;
        return temp;
        break;
    case 3:
        temp=T->right;
        temp1=temp->right;
        temp->left=T;
        temp->right=temp1;
        return temp;
        break;
    }
    return NULL;
}
char *Equation(node*x){ //find what is the situation (RR , LL , RL , LR)
    char*z=new char;z[0]=NULL;
    if(depth(x->right) > depth(x->left)){strcat(z,"R"); x=x->right;}
    else {strcat(z,"L");x=x->left;}
    if(depth(x->right) > depth(x->left)){strcat(z,"R"); x=x->right;}
    else {strcat(z,"L");x=x->left;}
    return z;
}
void balance (node*&T){ //balance the BST
    if(!T)return;
    if(!isBalance(T)){
        T=getBalance(T,Equation(T));
        return;
    }
    balance(T->left);
    balance(T->right);
}
node*insert1(node*T,int x){ //insert in the BST
    if(!T){node*temp=new node;
    temp->x=x;temp->left=temp->right=NULL;return temp;}
    if(T->x > x) T->left=insert1(T->left,x);
    else{T->right=insert1(T->right,x);}
    return T;
}
node* insert(node*T,int x){ //insert then Balance the BST
    T=insert1(T,x);
    balance(T);
    return T;
}
void print(node*T){ //prints the BST
    if(!T)return;
    cout<<T->x<<"  ";
    print(T->right);
    print(T->left);
}
void main(){
    node*head=NULL;
    /*for(int i=0;i<3;i++){
        if(i>50) head=insert(head,(i-3)/2);
        else head=insert(head,(i+3)*2);
    }*/
    head=insert(head,2);
    head=insert(head,4);
    head=insert(head,1);
    head=insert(head,0);
    head=insert(head,10);
    head=insert(head,64);
    head=insert(head,123);
    head=insert(head,121);
    head=insert(head,28);
    head=insert(head,12);
    head=insert(head,240);
    head=insert(head,42);
    head=insert(head,142);
    head=insert(head,76);
    head=insert(head,100);
    cout<<isBalance(head)<<endl;
    //print(head);
    system("pause");
}

Answer 1

你的树在某处有一个循环引用:

• (节点 4)->右指向(节点 10)
• (节点 10)->左点指向(节点 4)

然后，您尝试平衡树，但您的程序在计算其深度时卡住了:无限递归。

这是插入节点 123 后的树(平衡时):

root: (Node 2)

(Node 2)->left: (Node 1)
 (Node 1)->left: (Node 0)
 (Node 1)->right: none

(Node 2)->right: (Node 10)
 (Node 10)->left: (Node 4)
  (Node 4)->left: none
  (Node 4)->right: (Node 10) !!!!

 (Node 10)->right: (Node 64)
  (Node 64)->left: none
  (Node 64)->right: (Node 123)

我建议您创建一个函数来显示整个树，并在每次插入后调用它。您的插入路径(insert 本身或 balance)存在错误。