查询二叉树——Binary Sort Tree 设计与实现

野性酷女 2022-01-06 15:19 170阅读 0赞

二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

本代码是基本的结构，而更优的结构可以保证查询速度更快。

Size Balanced Tree(SBT)

AVL树

红黑树

Treap（Tree+Heap）

这些均可以使查找树的高度为O(log(n))。

如果插入次序是经过排序的，那么这种普通的二叉排序树的效果就差得一塌糊涂，由于树的偏移，树的深度是O（n），对于增删改查四个操作，每次操作都是O(n)的，这种情况完全不能满足要求。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #define LENGTH 5
      2 #include <iostream>
      3 #include <vector>
      4 #include <windows.h>
      5 #include <cmath>
      6 using namespace std;
      7 class Balanced_Binary_Tree{
      8 private:
      9     int infor;
     10     int balance_index;
     11     Balanced_Binary_Tree *left;
     12     Balanced_Binary_Tree *right;
     13     Balanced_Binary_Tree *father;
     14 public:
     15     friend int get_height(Balanced_Binary_Tree*);
     16     friend void print_tree(Balanced_Binary_Tree*);
     17     friend Balanced_Binary_Tree* exist(int);
     18     friend Balanced_Binary_Tree* get_max(Balanced_Binary_Tree*);
     19     friend Balanced_Binary_Tree* get_min(Balanced_Binary_Tree*);
     20     friend Balanced_Binary_Tree* search(int);
     21     friend void insert_node(int);
     22     friend void delete_node(int);
     23     friend void rotate(Balanced_Binary_Tree*);
     24     friend int max_distance(Balanced_Binary_Tree*);// a function for count the max distance between any two node in a BT
     25     friend void Balanced_Binary_Tree_Test();
     26     Balanced_Binary_Tree(int a){
     27         infor=a;
     28         left=NULL;
     29         right=NULL;
     30         father=NULL;
     31         Set_Balance_Index();
     32     }
     33     Balanced_Binary_Tree(){
     34         left=NULL;
     35         right=NULL;
     36         father=NULL;
     37         infor = -1;
     38         Set_Balance_Index();
     39     }
     40     void Set_Balance_Index(){
     41         balance_index = get_height(left) - get_height(right);
     42     }
     43     ~Balanced_Binary_Tree(){cout<<"Delete    "<<infor<<"    !"<<endl;}
     44     void print(){
     45         cout<<infor;
     46     }
     47 };
     48 static Balanced_Binary_Tree* Start = new Balanced_Binary_Tree(-2147483648);
     49 int get_height(Balanced_Binary_Tree* t)
     50 {
     51     if(t == NULL)
     52         return 0;
     53     else{
     54         int leftH=get_height((*t).left);
     55         int rightH=get_height((*t).right);
     56         return (leftH > rightH)?(leftH+1):(rightH+1);
     57     }
     58 }
     59 //返回这个节点的高度
     60 int max_distance(Balanced_Binary_Tree* root){
     61     if(root == NULL)return 0;
     62     else{
     63         int distance;
     64         distance = get_height((*root).left)+get_height((*root).right);
     65         return distance;
     66     }
     67 }
     68 //返回整个树的最大距离
     69 Balanced_Binary_Tree* exist(int a){
     70     if((*Start).right == NULL)
     71     {            
     72         return NULL;
     73     }
     74     else{
     75         Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
     76         t = (*Start).right;
     77         while(t!=NULL){
     78             if(a<(*t).infor){
     79                 t=(*t).left;
     80             }
     81             else if(a>(*t).infor){
     82                 t=(*t).right;
     83             }
     84             else if(a == (*t).infor)
     85                 break;
     86         }//while
     87         return t;
     88     }//else
     89 }//
     90 //exist 判断一个数据是否在排序树上，找到返回引用，未找到返回NULL；这是用在对数据进行判定的
     91 Balanced_Binary_Tree* search(int a){
     92     if(exist(a)==NULL)
     93     {
     94         if((*Start).right == NULL)
     95         {            
     96             return Start;
     97         }
     98         else{
     99             Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    100             Balanced_Binary_Tree *q = new Balanced_Binary_Tree();
    101             t = (*Start).right;
    102             while(t!=NULL){
    103                 q = t;
    104                 if(a<(*t).infor){
    105                     t=(*t).left;
    106                 }
    107                 else{
    108                     t=(*t).right;
    109                 }
    110             }//while
    111             return q;
    112         }//else
    113     }//if(!exist a)
    114     else return NULL;
    115 }//
    116 //search 查找一个数据应该插入的位置；不存在树时候返回头结点，存在树的时候，返回最后的结点的引用；这用于处理对数据插入过程中的插入位置判断。
    117 void insert_node(int a)
    118 {
    119     if(exist(a)==NULL)
    120     {
    121         Balanced_Binary_Tree *n = new Balanced_Binary_Tree(a);
    122         Balanced_Binary_Tree *t;
    123         t = search(a);
    124         (*n).father = t;
    125         if((*t).infor>a)
    126         {    (*t).left=n;    }
    127         else 
    128         {    (*t).right=n;    }
    129         // 首先将这个节点插入树上
    130         while(t!=Start){
    131             t->Set_Balance_Index();
    132             if(abs(t->balance_index)>=2)
    133                 break;
    134             t = t->father;
    135         }
    136         //判断这个树是不是平衡的
    137         if(t!=Start){
    138             rotate(t);
    139         }//这个子树不平衡
    140         //if(t!=Start)
    141     }//if(exist(a)==NULL)
    142 }
    143 //插入数据，如果数据不存在，就插入
    144 //当平衡的二叉排序树因为插入节点而失去平衡的时候，仅仅需要对最小不平衡子树进行平衡旋转处理。
    145 //因为经过旋转处理的子树深度与之前相同，因此不影响插入路径上所有祖先节点的平衡度。
    146 void rotate(Balanced_Binary_Tree *t){
    147             if(t->balance_index == 2){
    148                 t->left->Set_Balance_Index();
    149                 if(t->left->balance_index == 1){
    150                     Balanced_Binary_Tree *temp;
    151                     temp = t->left;
    152                     if((t->father->infor)>(t->infor))
    153                         t->father->left = temp;                    
    154                     else 
    155                         t->father->right = temp;
    156                     temp->father = t->father;
    157                     t->left = temp->right;
    158                     if(temp->right != NULL){
    159                         temp->right->father = t;                    
    160                     }
    161                     temp->right = t;
    162                     t->father = temp;    
    163                 }//if(t->left->balance_index == 1)
    164                 else{
    165                     Balanced_Binary_Tree *A,*B,*C;
    166                     A = t;
    167                     B = t->left;
    168                     C = B->right;
    169                     if((A->father->infor)>(A->infor))
    170                         A->father->left = C;                    
    171                     else 
    172                         A->father->right = C;
    173                     C->father = A->father;
    174 
    175                     A->father = C;
    176                     B->father = C;
    177 
    178                     A->left = C->right;
    179                     if(C->right != NULL)
    180                         C->right->father = A;
    181 
    182                     B->right = C->left;
    183                     if(C->left != NULL)
    184                         C->left->father = B;
    185 
    186                     C->right = A;
    187                     C->left = B;                    
    188 
    189                 }//if(t->left->balance_index == -1)
    190             }//if(t->balance_index == 2)
    191             else {
    192                 if(t->right->balance_index == -1){
    193                     Balanced_Binary_Tree *temp;
    194                     temp = t->right;
    195                     if((t->father->infor)>(t->infor))
    196                         t->father->left = temp;                    
    197                     else 
    198                         t->father->right = temp;
    199                     temp->father = t->father;
    200                     t->right = temp->left;
    201                     if(temp->left != NULL){
    202                         temp->left->father = t;
    203                     }
    204                     temp->left = t;
    205                     t->father = temp;
    206                 }//if(t->right->balance_index == -1)
    207                 else{
    208                     Balanced_Binary_Tree *A,*B,*C;
    209                     A = t;
    210                     B = t->right;
    211                     C = B->left;
    212                     if((A->father->infor)>(A->infor))
    213                         A->father->left = C;                    
    214                     else 
    215                         A->father->right = C;
    216                     C->father = A->father;
    217                     
    218                     A->father = C;
    219                     B->father = C;
    220 
    221                     A->right = C->left;
    222                     if(C->left != NULL)
    223                         C->left->father = A;
    224 
    225                     B->left = C->right;
    226                     if(C->right != NULL)
    227                         C->right->father = B;
    228 
    229                     C->right = B;
    230                     C->left = A;
    231                 }//if(t->right->balance_index == 1)
    232             }
    233 }
    234 
    235 
    236 Balanced_Binary_Tree* get_min(Balanced_Binary_Tree* a)
    237 {
    238     Balanced_Binary_Tree *t;
    239     t=a;
    240     while((*a).left!=NULL){
    241         t=a;
    242         a=(*a).left;
    243     }
    244     return t;
    245 }
    246 //找到最左节点
    247 Balanced_Binary_Tree* get_max(Balanced_Binary_Tree* a)
    248 {
    249     Balanced_Binary_Tree *t;
    250     while((*a).right!=NULL){
    251         t=a;
    252         a=(*a).right;
    253     }
    254     return t;
    255 }
    256 //找到最右节点
    257 void delete_node(int a){
    258     if(exist(a)!=NULL)
    259     {
    260         Balanced_Binary_Tree *t=exist(a);
    261         if((*t).left==NULL&&(*t).right==NULL)
    262         {
    263             if((*(*t).father).infor>(*t).infor){
    264                 (*(*t).father).left = NULL;
    265             }
    266             else (*(*t).father).right = NULL;
    267         }
    268         //删除的节点无子节点
    269         else if((*t).left==NULL||(*t).right==NULL)
    270         {
    271             
    272             if((*t).left == NULL)
    273             {
    274                 if((*(*t).father).infor>(*t).infor){
    275                     (*(*t).father).left = (*t).right;
    276                 }
    277                 else (*(*t).father).right = (*t).right;
    278                 (*(*t).right).father = (*t).father;
    279             }
    280             else{
    281                 if((*(*t).father).infor>(*t).infor){
    282                     (*(*t).father).left = (*t).left;
    283                 }
    284                 else (*(*t).father).right = (*t).left;
    285                 (*(*t).left).father = (*t).father;
    286             }
    287         }
    288         //删除的节点有一个子节点
    289         else{
    290             if((*(*t).father).infor>(*t).infor){
    291                     (*(*t).father).left = (*t).right;
    292                     (*(*t).left).father = get_min((*t).right);
    293                     Balanced_Binary_Tree *a = get_min((*t).right);
    294                     (*a).left = (*t).left;
    295                     (*(*t).right).father = (*t).father;
    296                 }
    297             else {
    298                 (*(*t).father).right = (*t).right;
    299                 (*(*t).left).father = get_min((*t).right);
    300                 Balanced_Binary_Tree *a = get_min((*t).right);
    301                 (*a).left = (*t).left;
    302                 (*(*t).right).father = (*t).father;
    303             }
    304         }
    305         //删除的节点有两个子节点
    306         Balanced_Binary_Tree *delete_node = t;
    307         while(t!=Start){
    308             t->Set_Balance_Index();
    309             if(abs(t->balance_index)>=2)
    310                 break;
    311             t = t->father;
    312         }
    313         if(t!=Start){
    314             rotate(t);
    315         }
    316         (*delete_node).left =NULL;
    317         (*delete_node).right =NULL;
    318         (*delete_node).father=NULL;
    319         delete delete_node;
    320         //delete t;
    321     }
    322 }
    323 //删除数据，如果数据存在，就删除
    324 void print_void(int k){
    325     while(k--)cout<<"  ";
    326 }
    327 //打印k个制表符
    328 void print_tree(Balanced_Binary_Tree* t){
    329     Balanced_Binary_Tree* temp = t;
    330     vector<Balanced_Binary_Tree*> list;
    331     list.push_back(temp);
    332     int k = get_height(t);
    333     while(k--){
    334         int print_length = pow((double)2,(double)k);
    335         int length = list.size();
    336         vector<Balanced_Binary_Tree*>::iterator iter;
    337         iter = list.begin();
    338         int number_son = list.size();
    339         print_void(print_length);
    340         for(int j=0;j<number_son;j++){
    341             if((*iter)->infor == -1)
    342                 cout<<"*";
    343             else 
    344                 (*iter)->print();
    345             if((*iter)->left == NULL)    {
    346                 t = new Balanced_Binary_Tree();
    347                 list.push_back(t);
    348                 iter = list.begin()+j;
    349             }
    350             else {
    351                 list.push_back((*iter)->left);
    352                 iter = list.begin()+j;
    353             }
    354             if((*iter)->right == NULL)    {
    355                 t = new Balanced_Binary_Tree();
    356                 list.push_back(t);
    357                 iter = list.begin()+j;
    358             }
    359             else {
    360                 list.push_back((*iter)->right);
    361                 iter = list.begin()+j;
    362             }
    363             iter++;
    364             print_void(print_length*2);
    365         }
    366         list.erase(list.begin(),list.begin()+number_son);
    367         cout<<endl;
    368     }
    369 }
    370 
    371 void Balanced_Binary_Tree_Test()
    372 {
    373     
    374     int test[LENGTH] = {
         1,3,5,4,2};
    375     for(int a=0;a<LENGTH;a++){
    376         insert_node(test[a]);
    377     }
    378     
    379 
    380     //TEST PART
    381     //int a;
    382     //while(cin>>a)insert_node(a);
    383     //TEST PART
    384     char c;
    385     int i;
    386     cout<<"AVL Tree!"<<endl;
    387     cout<<"d——delete a node;    "<<endl;
    388     cout<<"g——get the node's information;    "<<endl;
    389     cout<<"i——insert a node;    "<<endl;
    390     cout<<"l——get max length of the sub_tree;"<<endl;
    391     cout<<"c——clear the screen;"<<endl;
    392     cout<<"else——quit the test;"<<endl;
    393     while(cin>>c>>i){
    394         cout<<"AVL Tree!"<<endl;
    395         cout<<c<<" "<<i<<endl;
    396         cout<<"d——delete a node;    "<<endl;
    397         cout<<"g——get the node's information;    "<<endl;
    398         cout<<"i——insert a node;    "<<endl;
    399         cout<<"l——get max length of the sub_tree;"<<endl;
    400         cout<<"c——clear the screen;"<<endl;
    401         cout<<"else——quit the test;"<<endl;
    402         switch(c){
    403         case 'c':{
    404                 system("cls");
    405                 break;
    406                      }
    407         case 'g':
    408             {
    409                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    410                 t = exist(i);
    411                 if(t==NULL){
    412                     cout<<"The node "<<i<<" do not exist!"<<endl;
    413                         }
    414                 print_tree(Start->right);
    415                 break;
    416             }
    417         case 'd':
    418             {
    419                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    420                 t = exist(i);
    421                 if(t==NULL){
    422                     cout<<"The node "<<i<<" do not exist!"<<endl;
    423                 }
    424                 else{
    425                     delete_node((*t).infor);
    426                 }
    427                 print_tree(Start->right);
    428                 break;
    429             }
    430         case 'i':
    431             {
    432                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    433                 t = exist(i);
    434                 if(t==NULL){
    435                     cout<<"The node "<<i<<" do not exist!"<<endl;
    436                     insert_node(i);
    437                 }
    438                 else cout<<"The node "<<i<<" already exist!"<<endl;
    439                 print_tree(Start->right);
    440                 break;
    441             }
    442         case 'l':
    443             {
    444                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    445                 t = exist(i);
    446                 if(t==NULL){
    447                     cout<<"The node "<<i<<" do not exist!"<<endl;
    448                 }
    449                 else{
    450                     int l = max_distance(t);
    451                     print_tree(Start->right);
    452                     cout<<"max distance of sub tree "<<i<<" is " <<l<<endl;
    453                 }
    454                 break;
    455             }
    456         default:break;
    457         }
    458     }
    459 }
    460 
    461 
    462 int main(void)
    463 {
    464     Balanced_Binary_Tree_Test();
    465     return 0; 
    466 }

使用print（）函数打印这个树，通过广度优先遍历实现。

运行效果：

AVL Tree!  
i 3  
d——delete a node;  
g——get the node's information;  
i——insert a node;  
l——get max length of the sub\_tree;  
c——clear the screen;  
else——quit the test;  
The node 3 already exist!  
3  
1 5  
\* 2 4 \*  
i -4  
AVL Tree!  
i -4  
d——delete a node;  
g——get the node's information;  
i——insert a node;  
l——get max length of the sub\_tree;  
c——clear the screen;  
else——quit the test;  
The node -4 do not exist!  
3  
1 5  
\-4 2 4 \*  
i -6  
AVL Tree!  
i -6  
d——delete a node;  
g——get the node's information;  
i——insert a node;  
l——get max length of the sub\_tree;  
c——clear the screen;  
else——quit the test;  
The node -6 do not exist!  
3  
1 5  
\-4 2 4 \*  
\-6 \* \* \* \* \* \* \*

转载于:https://www.cnblogs.com/wangbiaoneu/archive/2013/04/25/BST\_Code\_Analysis.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/a7a2017f87ea489da3038b1cfe39824c.png