fork(2) download 
  1. #include<iostream>
  2. #define N 10
  3.  
  4. using namespace std;
  5.  
  6. struct TreeNode{
  7.       TreeNode *left;
  8.       TreeNode *right;
  9.       int data;
  10.       int bf; 
  11.  
  12.  
  13.        };
  14.  
  15. void leftRotation(TreeNode *,bool *);
  16. void rightRotation(TreeNode *,bool *);
  17. void avlInsert(TreeNode **,int,bool *);
  18. void display(TreeNode *);
  19.  
  20.  
  21. int main(void){
  22.  
  23.     TreeNode *head=NULL;
  24.     bool flag;
  25.  
  26.     avlInsert(&head,3,&flag);
  27.     avlInsert(&head,5,&flag);
  28.     avlInsert(&head,11,&flag);
  29.     avlInsert(&head,8,&flag);
  30.     avlInsert(&head,4,&flag);
  31.     avlInsert(&head,1,&flag);
  32.     avlInsert(&head,12,&flag);
  33.     avlInsert(&head,7,&flag);
  34.     avlInsert(&head,2,&flag);
  35.     avlInsert(&head,6,&flag);
  36.     avlInsert(&head,10,&flag);
  37.     avlInsert(&head,9,&flag);
  38.  
  39.     display(head);
  40.  
  41.     cout<<endl;
  42.  
  43.  
  44.     system("pause");
  45.     return 0;
  46. }
  47.  
  48.  
  49.  
  50. void avlInsert(TreeNode **root,int x,bool *unbalanced){
  51.      TreeNode *p;
  52.      p=*root;
  53.  
  54.  
  55.      if(p==NULL){
  56.      *unbalanced=true;         
  57.      TreeNode *s=new TreeNode;
  58.      s->data=x;
  59.      s->left=NULL;
  60.      s->right=NULL;       
  61.      s->bf=0;
  62.      *root=s;
  63.                  }
  64.      else if(x<(p->data)){
  65.           avlInsert(&((*root)->left),x,unbalanced);
  66.           if(*unbalanced)
  67.            switch(p->bf){
  68.              case -1:p->bf=0;
  69.                      *unbalanced=false;
  70.                       break;
  71.              case 0:p->bf=1;
  72.                       break;
  73.              case 1:leftRotation(p,unbalanced);                           
  74.  
  75.                     }
  76.           }
  77.      else if(x>(p->data)){
  78.         avlInsert(&((*root)->right),x,unbalanced);
  79.         if(*unbalanced)
  80.         switch(p->bf){
  81.              case 1:p->bf=0;
  82.                      *unbalanced=false;
  83.                       break;
  84.              case 0:p->bf=-1;
  85.                       break;
  86.              case -1:rightRotation(p,unbalanced);
  87.  
  88.                }
  89.  
  90.                }
  91.      else{
  92.            *unbalanced=false;
  93.           cout<<"鍵值已經在樹中"<<endl;
  94.  
  95.           }
  96.  
  97.      }
  98.  
  99.  
  100. void leftRotation(TreeNode *ptr,bool *unbalanced){
  101.       TreeNode *grandChild,*child;
  102.       child=ptr->left;
  103.       if(child->bf==1){
  104.         ptr->left=child->right;
  105.         child->right=ptr;
  106.         ptr->bf=0;
  107.         ptr=child;
  108.  
  109.      }
  110.      else{
  111.           grandChild=child->right;
  112.           child->right=grandChild->left;
  113.           grandChild->left=child;
  114.           ptr->left=grandChild->right;
  115.           grandChild->right=ptr;
  116.           switch(grandChild->bf){
  117.              case 1:ptr->bf=-1;
  118.                     child->bf=0;
  119.                     break;
  120.              case 0:ptr->bf=child->bf=0;break;
  121.              case -1:ptr->bf=0;
  122.                      child->bf=1;      
  123.           }
  124.           ptr=grandChild;
  125.  
  126.           }
  127.  
  128.      ptr->bf=0;
  129.      *unbalanced=false;
  130.  
  131.      }
  132.  
  133.  
  134. void rightRotation(TreeNode *ptr,bool *unbalanced){
  135.       TreeNode *grandChild,*child;
  136.       child=ptr->right;
  137.       if(child->bf==-1){
  138.         ptr->right=child->left;
  139.         child->left=ptr;
  140.         ptr->bf=0;
  141.         ptr=child;
  142.  
  143.      }
  144.      else{
  145.           grandChild=child->left;
  146.           child->left=grandChild->right;
  147.           grandChild->right=child;
  148.           ptr->right=grandChild->left;
  149.           grandChild->left=ptr;
  150.           switch(grandChild->bf){
  151.              case 1:ptr->bf=0;
  152.                     child->bf=-1;
  153.                     break;
  154.              case 0:ptr->bf=child->bf=0;break;
  155.              case -1:ptr->bf=1;
  156.                      child->bf=0;      
  157.           }
  158.           ptr=grandChild;
  159.  
  160.           }
  161.  
  162.      ptr->bf=0;
  163.      *unbalanced=false;
  164.  
  165.      }
  166.  
  167.  
  168. void display(TreeNode *ptr){
  169.  
  170.     if(ptr!=NULL){
  171.             display(ptr->left);       
  172.             cout<<ptr->data<<" ";
  173.             display(ptr->right);
  174.                    }
  175.  
  176.      }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:44: error: ‘system’ was not declared in this scope
stdout 
Standard output is empty
https://ideone.com/B6uAOz
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!