linux下平衡二叉树以树形打印来描述插入、删除的流程

这篇文章主要是为了温习下平衡二叉树，同时添加了树型打印的接口，让平衡二叉树的添加和删除更容易理解。

接下来的篇幅很长，需要有很多的耐心，做好了准备接下来往下看吧。

通俗的来说：

二叉树就是节点度最大为2的树，也就是最多包含两个子树，左子树和右子树，包含了空树。

二叉排序树(Binary Sort Tree)是在二叉树的基础上进行了规整，满足以下规则：

　　　　1）节点的值是能够进行大小比较的。

　　　　2）如果节点的左子树不为空，则左子树上的节点都比该节点小。

　　　　3）如果节点的右子树不为空，则右子树上的节点都比该节点大。

　　　　4）节点的左、右子树同时也是二叉排序树。

 

看完规则，那满足二叉排序树的树有很多，如下列图：

　　                

　　　　　图1　　　　　　　　　　　　　    图2

                   

　　　     图3                                                 图4

上面的图都满足二叉排序树，左边的节点都比右边的节点小，我们知道二分查找的最好时间复杂度为O(log2n)，而二叉排序树的查找类似于二分查找，要么找左边，要么找右边。

在上述的图中，图1中如果要寻找节点5，则必须将整个树全部遍历一遍，才能比较找到5这个节点，图2花的步数会少一些，图3和图4就花费的步数就更少了。

所以为了让二叉排序树也能像二分查找一样，保持接近于最好的时间复杂度O(log2n)，则二叉排序树的深度越少越好，这样就有了平衡二叉树(AVL)。

 

平衡二叉树其实就是所有节点的左右子树高度相差不超过1的二叉排序树，包含空树。

所以平衡二叉树是要满足二叉排序树的规则的，所以平衡二叉树只是二叉排序树的一个约定的特例，就比如皇帝柑之于柑橘，只是好吃了一点而已。

左右子树的高度差都不超过1，没有要求是左边高还是右边高，那就存在以下三种情况：

　　　　注：（有的以高度为0开始，这里高度以1开始，也就是空节点高度为0，一个节点的高度为1）

　　　　如果一样高则高度一致，所以高度差为0;

　　　　如果左边高则左边比右边高，满足平衡二叉树高度不超过1，我们把高度差记为1（左子树高度减去右子树高度）;

              如果右边高则右边比左边高，满足平衡二叉树高度不超过1，我们把高度差记为-1（左子树高度减去右子树高度）;

       这就是平衡因子的概念，平衡因子是相对于每一个节点而言的，概括就是左高减右高，如果要求出平衡因子，那么肯定是某个节点的平衡因子，求解得出来的平衡因子也是相对

某一个节点而言的。接下来我们讨论下这三种情况，并且解释下平衡因子的标识，以下三种情况以高度差来表示平衡因子。

　　1）两边一样高，也就是高度差为0，如下图

　　　     　                            

　　　　　　图5                            图6

               在图5和图6中，

　　　　首先看下图5，单个节点构成一棵二叉树，只有根节点，根节点没有左节点和右节点，所以图5中节点高度差为0。记录为下图

　　　　

 

　　　　再看图6，首先根节点有了两个子节点，也可以称为子树。首先1节点和3节点属于叶子节点(树上度为0的节点，没有左右子树，长得和图5中的节点很像)，

　　   所以1节点和3节点的高度差为0。

　　　　

 

　　　　再来看2节点，2节点左边有一个1节点，所以左边的高度为1,同理，右边的3节点的高度也为1，高度差为两边

          高度差，1-1=0。

　　　　

 

　　2）左边高，也就是左边的高度比右边高1，如下图

                                  

                    图7                                 图8

　　　　   先看图7，图中有两个节点，1节点属于叶子节点，没有左右子树，1节点的高度差为0，然后看2节点，2节点左边有一个1节点，左边高度为1，

　　　　右边是没有节点的，高度为0，所以高度差为1-0=1。

　　　　

 

　　　　在图7的基础上补上节点3和4形成图8，节点1和4属于叶子节点，高度差为0, 2节点高度差为1，我们先标上已知的高度差

　　　　

 

　　　　然后看下3节点，左边子树包含了1节点和2节点，高度为2，右边只有一个4节点，高度为1，所以高度差为2-1=1，所以图中

　　　　节点2和节点3的左子树都比右子树高1。

              

　　3）右边高，也就是右边的高度比左边高1，但是按照平衡因子计算方法，左高减右高，所以高度差是-1，如下图

                               

                        图9                                       图10

　　　　　在图9中，我们根据前面查看的示例，可以发现右边肯定是比左边高的，还是来标高度差，首先1节点和4节点不用说了

　　　　属于叶子节点，所以1节点和4节点的高度差为0，还要补充的是，我们查看高度差，采取从我们理解的下到上来标识，先叶子节点，

　　　　然后逐层上升。

　　　　

　　　　　然后3节点的高度，左边高度为0，右边有一个4节点，所以高度差为0-1=-1，同理2节点的左边子树高度为1，右边高度为2，所以

　　　　高度差为1-2=-1。

               

　　　　讨论完这三种情况，我们找一个平衡二叉树来标识平衡因子，下面还是按照平衡因子来说，我们来标识图11的平衡因子

　　　           　

                                      图11

　　　　　标完的图如下：

                        

                     可能-1的标识不是很清晰，看框的大小吧，-1的框比1的框要大一些的。

 

说完平衡因子，接下来说下二叉排序树，为什么说这个呢，因为平衡二叉树也是属于二叉排序树，只是对高度做了限制，所以平衡二叉树的添加和删除都是和二叉排序树一样的

只是当添加和删除了节点之后，还是二叉排序树，但是可能不满足平衡二叉树的要求，所以就会有后续的旋转啥的。先说二叉排序树的添加和删除，以添加起头。

 

二叉排序树添加节点

首先最先加入的节点肯定是根节点，我们以上面的图11为例，我们插入的顺序定为{5,2,1,4,3,6,7}，先插入5节点，

插入2节点，先和5进行比较，按照二叉排序树的要求，比节点小，就往左走，比节点大，就往右走，那么和节点一样大呢

那就不要了，不加入二叉排序树了。因为2比5小，所以往左找，发现没有左节点，2节点就作为5的左节点。

 

插入1节点，比5小，往左，比2小，再往左，没找到节点就添加

 

插入4节点，比5小，往左走，比2大，往右走，没找到节点就添加

 

插入3节点，比5小，往左走，比2大，往右走，比4小，往左走，没找到节点就添加

 

插入6节点，比5大，往右走，没找到节点就添加

 

插入7节点，比5大，往右走，比6大，往右走，没找到节点就添加

 

这样就和图11是一致的了，如果我们在图11的基础上再加入一些节点来说明有相同节点如何处理。那么插入队列就改成

{5,2,1,4,3,6,7,9,8,7}，加入了后面的9,8,7三个节点，先插入9和8.

              

 

然后插入7节点，比5大，往右走，比6大，往右走，发现和已存的节点7相等，取消插入，直接丢弃。

所以最后的二叉排序树是

　　　　　图12

 

二叉排序树添加的代码

首先二叉树的节点的定义如下：

 1）结构体定义

typedef struct _BiTree
{
    int node_data;//节点值

    int bf;//平衡因子

    struct _BiTree *left;//左子树指针
    struct _BiTree *right;//右子树指针
    _BiTree(int data)
        : node_data(data), bf(0), left(nullptr), right(nullptr)
    {}
}BiTreeType, *BiTreeTypePtr;

2）二叉排序树插入节点

　　我们回想之前的插入节点的逻辑：如果树为空，则添加节点为根节点，不为空，则查找后续节点，如果比查找节点小往左找，如果比查找节点大则往右，

　　如果存在查找节点等于预插入的节点，则丢弃预插入的节店，如果不存在，直到找到树的最下面，也就是最后找到nullptr，则插入节点。

　   插入的代码按照之前画的图的思路，

　　1）先判断是不是空树，空树直接添加，

　　2）如果不是空树，则要找到合适位置，如果节点存在，则不添加，

　　3）反之节点不存在，接着往下找，每一次查找，小于查找节点往左找，大于查找节点往右找，最后添加节点。

bool InsertNode(BiTreeTypePtr &bi_tree, int data)
{
    /*根节点*/
    if (bi_tree == nullptr)
    {
        BiTreeTypePtr node = new BiTreeType(data);
        bi_tree = node;
        return true;
    }
    
    /*在已存的二叉树中查找节点，如果不存在，就找到合适的位置加入节点*/
    BiTreeTypePtr p = nullptr;
    if (!SearchBBST(bi_tree, data, nullptr, p))
    {
        BiTreeTypePtr node = new BiTreeType(data);
        if (p->node_data > data)
        {
            p->left = node;
        }
        else
        {
            p->right = node;
        }
            
        return true;
    }

    return false;
}

 

 搜索的代码如下：小往左，大往右，找到nullptr表示走到头

bool SearchBBST(BiTreeTypePtr bi_tree, int data, BiTreeTypePtr parent, BiTreeTypePtr &choose_node)
{
    /*找到了最后为空的位置，没有找到节点，记录父节点，方便添加*/    
    if (nullptr == bi_tree)
    {
        choose_node = parent;
        return false;
    }        
    else if (bi_tree->node_data == data)
    {
        choose_node = bi_tree;
        return true;
    }
    else if (bi_tree->node_data > data)
    {
        return SearchBBST(bi_tree->left, data, bi_tree, choose_node);
    }
    else
    {
        return SearchBBST(bi_tree->right, data, bi_tree, choose_node);
    }
}

 

二叉排序树删除节点

插入节点就是在二叉树中找到对应的位置就添加节点，如果节点存在就丢弃节点，插入成功的节点都是叶子节点。接下来是删除节点，删除节点和插入不一样，

删除的节点可能是叶子节点，也有可能不是叶节点，存在左子树或者右子树，又或者两者都有，这样删除节点之后，子树必须接上来，继续组成一个二叉排序树。

当然如果节点不存在，找不到就没得删了。

接下来说删除节点的4个情况：以图12为例

　　　　1）删除的是叶子节点

　　　　　　比如删除的是1、3、8节点，这几个节点是没有子树的，以删除8节点为例

　　　　　　    

　　　　　　找到8节点，删除

　　　　　　            

 

　　　　2）删除的节点存在左节点，没有右节点

　　　　　　比如删除4节点，4节点存在左边的3节点，右边是空的

　　　　　　                  

　　　　　　

 

 

　　　　               

 

　　　　3）删除的节点存在右节点，没有左节点

　　　　　　比如删除6，7节点，6节点存在右边的7节点 ，  7节点存在右边的9节点，而左边是空的

　　　　　　以删除7节点为例

　　　　　　                            

 

　　　　　　       

 

 　　　　所以前三种情况中，删除节点之后，都是让节点的左节点或者右节点节点顶上来，叶子节点也是如此，可以认为叶子节点的左右节点

　　　　为空，删除叶子之后，空给了叶子节点的父节点。这时候父节点也变成了叶子节点

　　　　　　

　　　　4）删除的节点存在左节点和右节点

　　　　　　比如删除2节点，2节点存在左边的1节点和右边的3节点，同时存在左子树和右子树的节点删除的时候，会跟前三种情况不一样，

　　　　原则是这样的，如果删除的节点同时存在左子树和右子树，则让该节点的前继节点或者后继节点来代替该节点，然后删除前继节点或者

　　　　后继节点，前继节点：数值比删除节点小并且大小最接近删除节点的值，后继节点：数值比删除节点大并且大小最接近删除节点的值。

　　　　这里以后继节点来演示，首先看如何找后继节点，因为找后继节点，所以是要比节点大，那就往右走，再要找到大小最接近删除节点的值，

              那就是找右边最小的值。找小的值就往左边找。

　　　　那找后继就是往右边找最左边的值。

　　　　那找上图2节点的后继节点先往右，找到了3节点，再往左，发现没有节点了，所以3就是要找的节点

　　　　

　　　　这种情况是在3节点之后没有节点了，那再以其他情况解析下

　　　　

　　　　　　图13

 　　比如删除图13中的2节点，先往右找到5，然后往左找，一直找，会找到最左边的3节点

　　找到了后继节点，则删除有左子树和右子树的节点的如下图：

　　          

　　            

 

 复杂一点的就是：

                      

 

                

 

二叉排序树删除节点的代码

　  删除节点需要分4种情况，但是删除叶子节点的情况，跟只有左子树或者右子树的逻辑一致，可以按照后者来理解，也就是删除叶子节点的时候

     将叶子节点的左子树或者右子树给父节点，反正最后都会成为nullptr。

　　1）首先要找到删除的节点，找不到都是扯淡，找节点跟添加时候的搜索是一样的，都满足一样的规则，小往左，大往右

　　2）判断左子树是否为空，如果为空，标记父节点，将指向父节点的指针指向右子树，这时候可以想象，如果右子树为空，相当于删除的是叶子节点

　　　如果右子树不为空，则就是上面图中右子树顶上来的情况

/*左为空，删除父节点，右顶上*/
BiTreeTypePtr tmp;
if (nullptr == bi_tree->left)
{
    tmp = bi_tree;
    bi_tree = bi_tree->right;
    delete tmp;
    tmp = nullptr;
}

　　3）同理，右边的处理和左边一致，右边为空，左边不为空

/*右为空，删除父节点，左顶上*/
BiTreeTypePtr tmp;
if (nullptr == bi_tree->right)
{
    tmp = bi_tree;
    bi_tree = bi_tree->left;
    delete tmp;
　　 tmp = nullptr;
}

　　4）左子树和右子树都不为空的情况：找后继，右边找最小的值。后继节点替换删除节点，删除后继节点

/*先往右找大的节点*/
BiTreeTypePtr p = bi_tree->right;
BiTreeTypePtr tmp = p;
/*往左找最接近的值，后继值*/
while (nullptr != p->left)
{
    tmp = p;
    p = p->left;
}

/*后继节点的值给删除节点，然后后继节点的父节点左子树指向后继节点的右子树*/
bi_tree->node_data = p->node_data;
tmp->left = p->right;
delete p;
p = nullptr；

其中有一句tmp->left = p->right;

这句的意思是后继节点的父节点指向后继节点的右子树，因为在此刻后继节点是找到的最左边的值，

是肯定没有左子树的，但是可能有右子树，这时候删除后继节点，右子树得接上父节点。

所以上面while中tmp = p;就是在保存后继节点的父节点。

在前面的图中

      

上两图都是没有右子树的，加上代码中是找到最左边的值，所以后继节点是没有左子树的，所以这种情况就相当于节点的子树都没有，等同于叶子节点，删了就直接删了

但是如果有右子树的情况呢，我们加上一个3.5的点，在3节点替换了删除节点，删除3节点，那么3.5节点就需要接上3的父节点，不然后面的

数据就全丢了，因为后面的节点是属于3的节点，不管多大，都应该是比3的父节点小的，所以后面的所有节点都应该放在4的左子树上。

        

 

删除的代码总结起来如下：

bool DeleteNode(BiTreeTypePtr &bi_tree, int data)
{
    if (nullptr == bi_tree)
    {
        return false;
    }
    else if (bi_tree->node_data > data)
    {
        return DeleteNode(bi_tree->left, data);
    }
    else if (bi_tree->node_data < data)
    {
        return DeleteNode(bi_tree->right, data);
    }
    else
    {
        /*左为空，删除父节点，右顶上*/
        BiTreeTypePtr tmp;
        if (nullptr == bi_tree->right)
        {
            tmp = bi_tree;
            bi_tree = bi_tree->left;
            delete tmp;
        }
        else if (nullptr == bi_tree->left)
        {
            /*右为空，删除父节点，左顶上*/
            tmp = bi_tree;
            bi_tree = bi_tree->right;
            delete tmp;
        }
        else
        {
            /*先往右找大的节点*/
            BiTreeTypePtr p = bi_tree->right;
            tmp = p;
            /*往左找最接近的值，后继值*/
            while (nullptr != p->left)
            {
                tmp = p;
                p = p->left;
            }
           
            /*后继节点的值给删除节点，然后后继节点的父节点左子树指向后继节点的右子树*/
            bi_tree->node_data = p->node_data;
            tmp->left = p->right;
            delete p;
        }
        
        return true;
    }
} 

这时候可能有疑问，说添加节点为什么不直接搞成递归，还准们搞了一个搜索接口在里面，我的回答是完全可以的。

那么二叉排序树的搜索、添加、删除的代码综合如下：

先补上makefile，然后弄上代码，本人懒了一下，所有的验证代码都写在了构造函数中，没有写在main函数中。

如果对makefile不了解，在linux下创建一个文件，命名makefile,拷贝下面的makefile中的内容到创建makefile中，然后将代码

拷贝到main.cpp中，直接敲命令make就可以进行编译

注：如果linux中gcc版本过低，就是通过gcc -v查看到的版本发现低于4.7的，可以按如下方式做

　　1）将makefile中-std=c++11删除

　　2）将nullptr改为NULL

　　3）to_string可以用如下代码代替

#pragma once

#include <string>
#include <sstream>

using std::string;
using std::stringstream;

template <typename ValType>
string ToString(ValType val)
{
    stringstream ss;
    ss << val;
    return ss.str();
}

makefile和代码如下：

CC := g++

EXEC = bbst_test

RELEASE = ./

INCLUDES = -I. \

CFLAGS = $(INCLUDES) -Wall -O3 -std=c++11

LIBS = -L$(RELEASE)

CPPPATH = ./main.cpp

$(EXEC):
        $(CC) -o $(EXEC) $(CFLAGS) $(CPPPATH) $(LIBS)

clean:
        rm -rf *.o $(EXEC)

makefile

#include <string>
#include <iostream>
#include <cstdio>
#include <map>

using std::string;
using std::cout;
using std::endl;
using std::map;
using std::to_string;

typedef struct _BiTree
{
    int node_data;

    int bf;

    int height;

    int position;
    int splice;

    struct _BiTree *left;
    struct _BiTree *right;
    _BiTree(int data)
        : node_data(data), bf(0), height(0),
        position(0), splice(0), left(nullptr), right(nullptr)
    {}
}BiTreeType, *BiTreeTypePtr;

class BBST
{
public:
    BBST()
    {
        int arr[] = {49, 38, 65, 97, 76, 13, 27, 50};
//        int arr[] = {2,1,0,3,4,5,6,9,8,7};

        m_bi_tree_depth = 0;
        m_root_ptr = nullptr;
        for (unsigned i=0; i<sizeof(arr)/sizeof(arr[0]); ++i)
        {
            InsertNode(m_root_ptr, arr[i]);
        }

        PromptExistBiTree();

    }
    
    ~BBST()
    {
        Destory(m_root_ptr);
    }

private:

    void Destory(BiTreeTypePtr &bi_tree)
    {
        if (bi_tree)
        {
            Destory(bi_tree->left);
            Destory(bi_tree->right);

            delete bi_tree;
            bi_tree = nullptr;
        }
    }
    

    bool SearchBBST(BiTreeTypePtr bi_tree, int data, BiTreeTypePtr parent, BiTreeTypePtr &choose_node)
    {
        if (nullptr == bi_tree)
        {
            /*找到了最后为空的位置，没有找到节点，记录父节点，方便添加*/
            choose_node = parent;
            return false;
        }        
        else if (bi_tree->node_data == data)
        {
            choose_node = bi_tree;
            return true;
        }
        else if (bi_tree->node_data > data)
        {
            return SearchBBST(bi_tree->left, data, bi_tree, choose_node);
        }
        else
        {
            return SearchBBST(bi_tree->right, data, bi_tree, choose_node);
        }
    }

    bool InsertNode(BiTreeTypePtr &bi_tree, int data)
    {
        /*根节点*/
        if (bi_tree == nullptr)
        {
            BiTreeTypePtr node = new BiTreeType(data);
            bi_tree = node;
            return true;
        }

        /*在已存的二叉树中查找节点，如果不存在，就找到合适的位置加入节点*/
        BiTreeTypePtr p = nullptr;
        if (!SearchBBST(bi_tree, data, nullptr, p))
        {
            BiTreeTypePtr node = new BiTreeType(data);
            if (p->node_data > data)
            {
                p->left = node;
            }
            else
            {
                p->right = node;
            }
            
            return true;
        }

        return false;
    }

    bool DeleteNode(BiTreeTypePtr &bi_tree, int data)
    {
        if (nullptr == bi_tree)
        {
            return false;
        }
        else if (bi_tree->node_data > data)
        {
            return DeleteNode(bi_tree->left, data);
        }
        else if (bi_tree->node_data < data)
        {
            return DeleteNode(bi_tree->right, data);
        }
        else
        {
            /*左为空，删除父节点，右顶上*/
            BiTreeTypePtr tmp;
            if (nullptr == bi_tree->right)
            {
                tmp = bi_tree;
                bi_tree = bi_tree->left;
                delete tmp;
            }
            else if (nullptr == bi_tree->left)
            {
                /*右为空，删除父节点，左顶上*/
                tmp = bi_tree;
                bi_tree = bi_tree->right;
                delete tmp;
            }
            else
            {
                /*先往右找大的节点*/
                BiTreeTypePtr p = bi_tree->right;
                tmp = p;
                /*往左找最接近的值，后继值*/
                while (nullptr != p->left)
                {
                    tmp = p;
                    p = p->left;
                }

                /*后继节点的值给删除节点，然后后继节点的父节点左子树指向后继节点的右子树*/
                bi_tree->node_data = p->node_data;
                tmp->left = p->right;
                delete p;
            }
            
            return true;
        }
    }

    void PromptExistBiTree()
    {
        m_level_str_map.clear();
        m_bi_tree_depth = 0;
        MarkNodeHeight(m_root_ptr, 0);
        MarkBinaryTree(m_root_ptr, GetRootPosition(m_bi_tree_depth));
        SpliceBiTreeStr(m_root_ptr);

        PaintBiTree();
    }

    void MarkNodeHeight(BiTreeTypePtr &bi_tree, int height)
    {
        if (bi_tree == nullptr)
        {
            return;
        }
        
        bi_tree->height = height;
        if (height > m_bi_tree_depth)
        {
            m_bi_tree_depth = height;
        }

        if (bi_tree->left != nullptr)
        {
            MarkNodeHeight(bi_tree->left, height + 1);
        }

        if (bi_tree->right != nullptr)
        {
            MarkNodeHeight(bi_tree->right, height + 1);
        }
    }

    void MarkBinaryTree(BiTreeTypePtr &bi_tree, int position)
    {
        if (bi_tree == nullptr)
        {
            return;
        }
        
        bi_tree->position = position;
        bi_tree->splice = GetRootSplice(m_bi_tree_depth - bi_tree->height);
    
//        cout << bi_tree->height << ":" << bi_tree->splice << ":" << bi_tree->position << ":" << bi_tree->data << endl;

        if (bi_tree->left != nullptr)
        {
            MarkBinaryTree(bi_tree->left, position - GetRootPosition(m_bi_tree_depth - bi_tree->height - 1) - 1);
        }

        if (bi_tree->right != nullptr)
        {
            MarkBinaryTree(bi_tree->right, position + GetRootPosition(m_bi_tree_depth - bi_tree->height - 1) + 1);
        }
    }

    void SpliceBiTreeStr(BiTreeTypePtr &bi_tree)
    {
        if (bi_tree != nullptr)
        {
            string p_str = FindLevelStr(bi_tree->splice);

            if (!p_str.empty())    
            {                
                p_str.append(bi_tree->position - p_str.size(), ' ');
            }
            else
            {            
                p_str.append(bi_tree->position, ' ');
            }

            p_str.append(to_string(bi_tree->node_data));                
            m_level_str_map[bi_tree->splice] = p_str;
            
#if 1
            if (bi_tree->height != m_bi_tree_depth)
            {
                int brance_splice = GetRootPosition(m_bi_tree_depth - bi_tree->height - 1);
                for (int i=1; i<=brance_splice; ++i)
                {
                    string brance_str = FindLevelStr(bi_tree->splice - i);
                    
                    if (!brance_str.empty())
                    {
                        brance_str.append(bi_tree->position - brance_str.size() - i, ' ');    
                    }
                    else
                    {
                        brance_str.append(bi_tree->position - i, ' ');
                    }

                    if (bi_tree->left != nullptr)
                    {
                        brance_str.append("/");
                    }
                    else
                    {
                        brance_str.append(" ");
                    }


                    if (bi_tree->right != nullptr)
                    {
                        brance_str.append(i*2 - 1, ' ');
                        brance_str.append("\\");
                    }
                                            
                    m_level_str_map[bi_tree->splice - i] = brance_str;
                }
            }
#endif
            if (bi_tree->left != nullptr)
            {
                SpliceBiTreeStr(bi_tree->left);
            }

            if (bi_tree->right != nullptr)
            {
                SpliceBiTreeStr(bi_tree->right);
            }
        }
    }

    void PaintBiTree()
    {
        int splice = -1;
        while ((splice = SelectLowestNode()) != -1)
        {
            cout << m_level_str_map[splice] << endl;
            m_level_str_map.erase(splice);
        }
    }

    int SelectLowestNode()
    {
        int mininal_num = -1;
        for (auto map_pair : m_level_str_map)
        {
            if (map_pair.first > mininal_num)
            {
                mininal_num = map_pair.first;
            }
        }

        return mininal_num;
    }

    int GetRootPosition(int height)
    {
        return abs(GetPrintSide(height, 1) * 3 - 1);
    }

    int GetRootSplice(int height)
    {
        int splice_num = GetPrintSide(height, 1) * 3 - 1;
        return (splice_num > 0) ? splice_num : 0;
    }

    int GetPrintSide(int height, int side)
    {
        if (height <= 0)
        {
            return 0;
        }
        else if (height == 1)
        {
            return side;
        }
        else
        {
            return GetPrintSide(height-1, side*2);
        }
    }

    string FindLevelStr(int splice)
    {
        string tmp_str;
        for (auto node : m_level_str_map)
        {
            if (node.first == splice)
            {
                return node.second;
            }
        }

        return tmp_str;
    }

private:
    BiTreeTypePtr m_root_ptr;

    int m_bi_tree_depth;

    map<int, string> m_level_str_map;
};

int main()
{
    BBST bb_st;
    
    return 0;
}

二叉排序树search、insert、delete

 代码中的PromptExistBiTree为打印接口，会以树形打印数据，可以在你想调试的代码的位置打印数据，比如可以放在插入接口中

打印逻辑如下图，可以对着代码看

 

运行完的结果应该如下：

 

平衡二叉树

接下来就是平衡二叉树的操作了，前面的理解清楚再来看最好了

我们拿前面结果中的二叉排序树来标记平衡因子

           

        

可以看到38这个节点的平衡因子已经不再有效范围内了，高度差已经达到2了。所以为了让二叉排序树能够变成平衡二叉树，就需要

将38的平衡因子降到有效范围之内(-1、0、1)，那么就是接下来说的事情------旋转

旋转的4种情况先列举出来：

1）单次右旋转，（找左，右变左，父变右），

　先标下图的平衡因子

             

那么平衡因子右问题的是3节点，那么找左就是找问题节点3的左节点，因为左边高，所以肯定是存在左节点的。

找到左子节点为2，然后右变左是子节点的右子树变成父节点的左子树，最后父变右就是父节点变成子节点的右节点。

在变动完成后，调整平衡因子就可以了

用图来演示就是：

　　I.找左

    

      II.右变左

　　　因为2的右节点为空，所以将3的左节点置空　　

       

　　III.父变右

　　

 　　父节点变成右节点，也就是3节点变成2节点的右节点，

　　重新调整下平衡因子

       

 

接下来还是演示一下存在右节点的的操作

         

      4节点的平衡因子为2，不属于有效范围，右旋转，首先找左

　　

　　右变左，2的右节点3变成父节点4的左节点

      

     父变右

 　　

　　重新标识平衡因子

　　

 

可以看出来，当平衡因子为正的时候，进行右旋转

void R_Rotate(BiTreeTypePtr &bi_tree)
{
    cout << "    right rotate " << endl;
    BiTreeTypePtr tmp = bi_tree->left;//找左
    bi_tree->left = tmp->right;//右变左
    tmp->right = bi_tree;//父变右
    bi_tree = tmp;//节点接上
}

 

 

2）单次左旋转，（找右，左变右，父变左）

 直接图来标识，

            

  

当平衡因子为负的时候，进行坐旋转

子节点存在左节点的情况可以自己验证下，这里就不演示了

void L_Rotate(BiTreeTypePtr &bi_tree)
{
    cout << "    left rotate " << endl;
    BiTreeTypePtr tmp = bi_tree->right;//找右
    bi_tree->right = tmp->left;//左变右
    tmp->left = bi_tree;//父变左
    bi_tree = tmp;//节点接上
}

 

 

3）先右旋后左旋

为什么会有这个旋转呢，先按照单旋转来演示下，如果存在以下情况：

            

按照之前的问题节点的平衡因子-2，为负，左旋转

    

可以看到依旧是不符合要求，再进行右旋转，会发现又变回了最开始的情况，可以大家自己试一试

碰到这种情况，再看看图中的平衡因子，会发现跟单次旋转的不一样，单次旋转的问题节点和子节点的平衡因子

是同符号的，也就是同为正或者同为负。

而刚才的图中问题节点和子节点的平衡因子符号是相反的，互为正负。

这样就需要两次旋转，怎么旋转呢，先看子节点的平衡因子，还是正-右转，负-左转

那么重新以上图来演示

               

这时候先看子节点，3节点的平衡因子为1，则右转，右转的支点为3节点。这时候3变成支点之后，那么右转就要按照右转的规则

           

 

          

 

 

这时候可以发现，这已经跟前面单次左旋转的情况是一样的，负-左转，然后支点变成了之前的父节点1

按照单次左转的操作，大家可以试一下。这样最后得到的结果也是前面单次旋转得到的结果

 

 

4）先左旋后右旋

 还记得前面3）先右旋后左旋的开始，单次旋转无法解决问题的结果，结果如下图

　　

可以看出平衡因子互为正负，那么先看子节点的，负-左转，然后父节点正-右转，直接以图来标识

          

 

 

 

可以看到旋转完了之后，就能达到平衡的状态了

 

平衡二叉树添加节点

那接下来就是平衡二叉树添加节点，平衡二叉树添加节点和二叉排序树添加节点都是一样的，还是找合适的位置，

但是平衡二叉树较二叉排序树更严格，所以添加完节点之后还是需要考虑平衡性的。我们还是以二叉排序树用的节点来演示

节点为：{49, 38, 65, 97, 76, 13, 27, 50}

　　　　1）根节点

　　　　

　　　　2) 添加节点38

　　　　

　　　　3）添加节点65

　　　　

　　　　4）添加节点97

　　　　

　　　　5）添加节点76

　　　　        平衡因子子节点1，正-右转，父节点-2，负-左转

　　　　

　　　　6）添加节点13

　　　　

　　　　7）添加节点27

　　　　平衡因子子节点-1，负-左转，父节点2，正-右转

　　　　

　　　　8）添加节点50

　　　　

 

最后调整完的样子是这样的，跟二叉排序树完成时候的样子还是差别一些的

那下面开始讲解代码怎么弄

首先，我们可以看到添加节点会引起一连串的变化，从节点到根节点的一条路上的节点的平衡因子都可能发生了改变，因为影响平衡因子的就是子树的高低

所以其他没有发生子树改变，所以不会发生平衡因子改变。而从根节点一路找下来的这条路都会发生子树发生变化，所以这一路的根节点的平衡因子可能会发

生变化。

当我们添加完节点的时候，刚好处于树的最下端，这时候去改变这条路上的节点平衡因子，可以一路按照查找的路径返回回去，这就是递归的好处。

接下来我们要从代码角度讨论，所以先定义三个变量来标识正常的平衡因子

#define LH 1    //左高
#define EH 0    //等高
#define RH -1   //右高

我们分析当添加一个节点，如果父节点之前是EH，则再添加节点高度会增加1层

如果父节点是LH，在右边添加节点，或者父节点是RH，在左边添加节点，则高度不会添加，但是父节点的平衡因子会变成EH

如果父节点是LH，接着在左边添加节点，则LH会接着添加一层，会出现不平衡的状况

同理，如果父节点是RH，接着在右边添加节点，则RH会接着添加一层，会出现不平衡的状态

这时候就需要旋转，旋转是为了让节点的层次减一，变成之前的平衡状态，这时候相当于添加了节点，高度还是没有增加

以图说明问题

　　1）父节点是EH，添加左节点或者右节点，高度会增加

　　

　　

 

　　我们可以看到往左边加肯定是左边会高，右边加肯定是右边高

　　2）如果父节点不是EH，而是某一边高，然后添加另外一边，保持节点平衡了，高度不变

　　       

 

　　      

　　3）如果父节点不是EH，是某一边高，然后接着往高的一遍添加

　　         或者

 

或者，可以看到的是树的高度没有增加，经过旋转了之后，高度是重新跟之前一样了

　　    或者

  或者  也同上面，高度是没有增加的

 

接下来讨论下平衡因子的变化，首先添加进去的叶子节点的平衡因子肯定是0.

如果没有旋转，平衡因子的变化很好计算，首先叶子节点添加叶子节点，叶子节点的平衡因子由EH变为LH或者RH

如果是已经有左节点或者右节点，再添加另外一边的节点，则将父节点的平衡因子改为EH

如果有旋转，则存下以下的情况，左边高，右旋转，左右旋转

1）右旋转

　　　　

         或者

 

或者

  　　　　　　　　　　　　　　　　　

 　　　　可以看到添加的节点的平衡因子最后还是0，要么变成了父节点，带两个子节点，要么还是作为叶子节点，但是之前的父节点65

　　的平衡因子变为了0，子节点50也变成了0，也就是问题节点和子节点都变成了0，

　　这里的插入节点往上是依次累加到问题节点，如果不是累加到问题节点，而是像下面

　　          

　　这样插入节点是经过两个LH的节点了才到问题节点，这样的可以扩展开