C++实现二叉搜索书（参考算法导论）

短命女 2022-02-28 08:14 166阅读 0赞

# [C++实现二叉搜索书（参考算法导论）][C] #

1 #include <iostream>
      2 using namespace std;
      3 
      4 struct node 
      5 {
      6     // 数据域
      7     int data;
      8 
      9     // 左节点
     10     node *lc;
     11 
     12     // 右结点
     13     node *rc;
     14 
     15     // 构造函数
     16     node()
     17         : data(0)
     18         , lc(NULL)
     19         , rc(NULL)
     20     {
     21     }
     22 };
     23 
     24 
     25 // bst
     26 class bstree
     27 {
     28 public:
     29     enum
     30     {
     31         hmax_size_32767     = 32767,
     32         hmin_size_0         = 0,
     33     };
     34 
     35 public:
     36 
     37     // 构造函数
     38     bstree()
     39         : root(NULL)
     40         , size(0)
     41     {
     42     }
     43 
     44     // 析构函数
     45     virtual ~bstree(){}
     46     
     47     int get_size()
     48     {
     49         return size;
     50     }
     51 
     52     // 插入结点
     53     void insert_node(int data)
     54     {
     55         int cur_size = get_size();
     56         if (hmax_size_32767 == cur_size)
     57         {
     58             cout << "insert node error, the size of the tree is max" << endl;
     59             return ;
     60         }
     61         root = insert(root, data);
     62     }
     63 
     64     // 先序遍历（前序遍历）
     65     void pre_order()
     66     {
     67         pre_order_traverse(root);
     68     }
     69 
     70     // 中序遍历
     71     void in_order()
     72     {
     73         in_order_traverse(root);
     74     }
     75 
     76     // 后序遍历
     77     void post_order()
     78     {
     79         post_order_traverse(root);
     80     }
     81 
     82     /*
     83         查找某个结点
     84         int key - 查找结果
     85 
     86         返回值：
     87             NULL : 可能为root为空 或者 没有找到
     88             != NULL, 找到结点
     89     */
     90     node* query(int key)
     91     {
     92         if (NULL == root)
     93         {
     94             cout << "query error, root = null" << endl;
     95             return NULL;
     96         }
     97 
     98         return query_node(root, key);
     99     }
    100 
    101     // 删除树
    102     void remove_all()
    103     {
    104         if (NULL == root)
    105         {
    106             cout << "remove all failed, root = null" << endl;
    107             return;
    108         }
    109         
    110         remove_all(root);
    111 
    112         int cur_size = get_size();
    113         if (0 == cur_size)
    114             root = NULL;
    115     }
    116 
    117     // 删除某个结点
    118     void remove_node(int del_data)
    119     {
    120         if (NULL == root)
    121         {
    122             cout << "remove node error, root = null" << endl;
    123             return;
    124         }
    125 
    126         node *parent_node   = NULL;
    127         node *del_node      = root;
    128 
    129         // 找到删除结点的父节点与删除结点
    130         while (del_node)
    131         {
    132             if (del_data == del_node->data)
    133                 break;
    134             else if (del_data > del_node->data)
    135             {
    136                 parent_node = del_node;
    137                 del_node    = del_node->rc;
    138             }
    139             else if (del_data < del_node->data)
    140             {
    141                 parent_node = del_node;
    142                 del_node = del_node->lc;
    143             }
    144         }
    145 
    146         // 若没有找到要删除的结点
    147         if (NULL == del_node)
    148         {
    149             cout << "remove node error, " << del_data << " was not find" << endl;
    150             return;
    151         }
    152 
    153         // 1、若删除的结点没有左子树和右子树
    154         if ( (NULL == del_node->lc) && (NULL == del_node->rc)  )
    155         {
    156             // 为什么要先判断根结点，因为根结点的父节点找不到，结果为NULL，
    157             // 1.1 可能只有一个根结点， 将root释放值为空
    158             if (del_node == root)
    159             {
    160                 root = NULL;
    161                 delete del_node;
    162                 del_node = NULL;
    163 
    164                 dec_size();
    165                 return;
    166             }
    167 
    168             // 1.2 非根结点，那就是叶子结点了， 将父节点指向删除结点的分支指向NULL
    169             if  (del_node == parent_node->lc)
    170                 parent_node->lc = NULL;
    171             else if (del_node == parent_node->rc)
    172                 parent_node->rc  = NULL;
    173 
    174             // 释放结点
    175             delete del_node;
    176             del_node = NULL;
    177             dec_size();
    178         }
    179 
    180         // 2、若删除结点只有左孩子，没有右孩子
    181         else if ( (NULL != del_node->lc) && (NULL == del_node->rc) )
    182         {
    183             // 2.1 删除结点为根结点，则将删除结点的左孩子替代当前删除结点
    184             if (del_node == root)
    185             {
    186                 root = root->lc;
    187             }
    188             // 2.2 其他结点，将删除结点的左孩子作为父节点的左孩子
    189             else
    190             {
    191                 if (parent_node->lc == del_node)
    192                     parent_node->lc = del_node->lc;
    193                 else if (parent_node->rc == del_node)
    194                     parent_node->rc = del_node->lc;
    195             }
    196 
    197             delete del_node;
    198             del_node = NULL;
    199 
    200             dec_size();
    201         }
    202 
    203         // 3、若删除结点只有右孩子
    204         else if ( (NULL == del_node->lc) && (NULL != del_node->rc) )
    205         {
    206             // 3.1 若为根结点
    207             if (root == del_node)
    208             {
    209                 root = root->rc;
    210             }
    211             else
    212             {
    213                 if (del_node == parent_node->lc)
    214                     parent_node->lc = del_node->rc;
    215                 else if (del_node == parent_node->rc)
    216                     parent_node->rc = del_node->rc;
    217             }
    218 
    219             delete del_node;
    220             del_node = NULL;
    221 
    222             dec_size();
    223         }
    224 
    225         // 4、若删除结点既有左孩子，又有右孩子,需要找到删除结点的后继结点作为根结点
    226         else if ( (NULL != del_node->lc) && (NULL != del_node->rc) )
    227         {
    228             node *successor_node = del_node->rc;
    229             parent_node = del_node;
    230 
    231             while (successor_node->lc)
    232             {
    233                 parent_node = successor_node;
    234                 successor_node = successor_node->lc;
    235             }
    236 
    237             // 交换后继结点与当前删除结点的数据域
    238             del_node->data = successor_node->data;
    239             // 将指向后继结点的父节点的孩子设置后继结点的右子树
    240             if (successor_node == parent_node->lc)
    241                 parent_node->lc = successor_node->rc;
    242             else if (successor_node == parent_node->rc)
    243                 parent_node->rc = successor_node->rc;
    244 
    245             // 删除后继结点
    246             del_node = successor_node;
    247             delete del_node;
    248             del_node = NULL;
    249 
    250             dec_size();
    251         }
    252     }
    253 
    254     // 返回以proot为根结点的最小结点
    255     node *get_min_node(node *proot)
    256     {
    257         if (NULL == proot->lc)
    258             return proot;
    259 
    260         return get_min_node(proot->lc);
    261     }
    262 
    263     // 返回以proo为根节点的最大结点
    264     node *get_max_node(node *proot)
    265     {
    266         if (NULL == proot->rc)
    267             return proot;
    268         
    269         return get_max_node(proot->rc);
    270     }
    271 
    272     // 返回根节点
    273     node *get_root_node()
    274     {
    275         return root;
    276     }
    277 
    278     // 返回proot结点的父节点
    279     node *get_parent_node(int key)
    280     {
    281         // 当前结点
    282         node *cur_node = NULL;
    283         // 父节点
    284         node *parent_node = NULL;
    285 
    286         cur_node = root;
    287 
    288         // 标记是否找到
    289         bool is_find = false;
    290         while (cur_node)
    291         {
    292             if (key == cur_node->data)
    293             {
    294                 is_find = true;
    295                 break;
    296             }
    297 
    298             // 因为比当前结点的值还要小，所以需要查找当前结点的左子树
    299             else if (key < cur_node->data)
    300             {
    301                 parent_node = cur_node;
    302                 cur_node = cur_node->lc;
    303             }
    304             // 同上， 查找当前结点的右子树
    305             else if (key > cur_node->data)
    306             {
    307                 parent_node = cur_node;
    308                 cur_node    = cur_node->rc;
    309             }
    310         }
    311 
    312         return (true == is_find)?  parent_node :  NULL; 
    313     }
    314 
    315     // 查找某个结点为根节点的最结点
    316 
    317 private:
    318 
    319 
    320     //查找某个值
    321     node *query_node(node *proot, int key)
    322     {
    323         if (NULL == proot)
    324         {
    325             return proot;
    326         }
    327 
    328         if (proot->data == key)
    329             return proot;
    330         else if (proot->data > key)
    331         {
    332             return query_node(proot->lc, key);
    333         }
    334         else if (proot->data < key)
    335         {
    336             return query_node(proot->rc, key);
    337         }
    338         
    339         return NULL;
    340     }
    341 
    342     // 后序遍历删除所有结点
    343     void remove_all(node *proot)
    344     {
    345         if (NULL != proot)
    346         {
    347             remove_all(proot->lc);
    348             remove_all(proot->rc);
    349             delete proot;
    350 
    351             dec_size();
    352         }
    353     }
    354 
    355     // 先序遍历
    356     void pre_order_traverse(node *proot)
    357     {
    358         if (NULL != proot)
    359         {
    360             cout << proot->data << ",   "; 
    361             pre_order_traverse(proot->lc);
    362             pre_order_traverse(proot->rc);
    363         }
    364     }
    365 
    366     // 中序遍历
    367     void in_order_traverse(node *proot)
    368     {
    369         if (NULL != proot)
    370         {
    371             in_order_traverse(proot->lc);
    372             cout << proot->data << ",   "; 
    373             in_order_traverse(proot->rc);
    374         }
    375     }
    376 
    377     // 后续遍历
    378     void post_order_traverse(node *proot)
    379     {
    380         if (NULL != proot)
    381         {
    382             post_order_traverse(proot->lc);
    383             post_order_traverse(proot->rc);
    384             cout << proot->data << ",   ";
    385         }
    386     }
    387 
    388     // 插入结点
    389     node *insert(node *proot, int data)
    390     {
    391         // 结点不存在， 则创建
    392         if (NULL == proot)
    393         {
    394             node *new_node = new(std::nothrow) node;
    395             if (NULL != new_node)
    396             {
    397                 new_node->data = data;
    398                 proot = new_node;
    399                 
    400                 // 结点+1；
    401                 add_size();
    402             }
    403 
    404             return proot;
    405         }
    406 
    407         //  插入值比当前结点值还要小， 则应该插入到当前节点的左边
    408         if (proot->data > data)
    409         {
    410             proot->lc = insert(proot->lc, data);
    411         }
    412         // 插入之比当前结点值还要打，则应该插入到当前结点的右边
    413         else if (proot->data < data)
    414         {
    415             proot->rc = insert(proot->rc, data);
    416         }
    417 
    418         // 相等，则不插入结点。
    419 
    420         return proot;
    421     }
    422 
    423     // size + 1
    424     void add_size()
    425     {
    426         if (hmax_size_32767 == size)
    427             return ;
    428         size++;
    429     }
    430 
    431     // size - 1
    432     void dec_size()
    433     {
    434         if ( hmin_size_0 == size)
    435         {
    436             return ;
    437         }
    438 
    439         size--;
    440     }
    441 
    442 private:
    443     // 根结点
    444     node *root;
    445 
    446     // 当前树的结点个数
    447     int size;
    448 };
    449 
    450 
    451 
    452 // 测试代码
    453 int main()
    454 {
    455 
    456     bstree tree;
    457 
    458     //
    459     tree.insert_node(50);
    460 
    461     tree.insert_node(30);
    462     tree.insert_node(10);
    463     tree.insert_node(0);
    464     tree.insert_node(20);
    465     tree.insert_node(40);
    466 
    467     tree.insert_node(70);
    468     tree.insert_node(90);
    469     tree.insert_node(100);
    470     tree.insert_node(60);
    471     tree.insert_node(80);
    472 
    473     // 前序遍历
    474     cout << "前序遍历" << endl;
    475     tree.pre_order();
    476     cout << endl;
    477 
    478     // 中序遍历
    479     cout << "中序遍历" << endl;
    480     tree.in_order();
    481     cout << endl;
    482 
    483     // 后序遍历
    484     cout << "后序遍历" << endl;
    485     tree.post_order();
    486     cout << endl;
    487 
    488     cout << "删除结点开始，结束请输入10086" << endl;
    489 
    490     int del_key = 0;
    491 
    492     while (true)
    493     {
    494         cout << "输入删除结点值 = ";
    495         cin >> del_key;
    496         if (10086 == del_key)
    497             break;
    498 
    499         tree.remove_node(del_key);
    500 
    501         cout << "删除后,结点个数 = " << tree.get_size() << endl;
    502         cout << "删除后， 中序遍历结果:" ;// << endl;
    503         tree.in_order();
    504         cout << endl << endl;
    505     }
    506 
    507     tree.remove_all();
    508 
    509     return 0;
    510 }

参考：《算法导论》

参考博文：[https://www.cnblogs.com/fivestudy/p/10340647.html][https_www.cnblogs.com_fivestudy_p_10340647.html]

posted @ 2019-03-14 23:20 [mohist][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

[C]: https://www.cnblogs.com/pandamohist/p/10534335.html
[https_www.cnblogs.com_fivestudy_p_10340647.html]: https://www.cnblogs.com/fivestudy/p/10340647.html
[mohist]: https://www.cnblogs.com/pandamohist/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=10534335