平衡二叉树旋转操作，插入，删除，合并，分裂，凹入表打印

一个详细的课程设计，包含了旋转操作，插入，删除，合并，分裂，凹入表打印等重点操作。验证所有非法操作，分享给大家学习。

#include “AVL.h“

/**
 * 节点的右旋
 * @param T AVL树根节点
 */
void R_Rotate（BBSTree *T） {
    BBSTree lc = （*T）->lchild;
    （*T）->lchild = lc->rchild;
    lc->rchild = *T;
    *T = lc;
}

/**
 * 节点的左旋
 * @param T AVL树根节点
 */
void L_Rotate（BBSTree *T） {
    BBSTree rc = （*T）->rchild;
    （*T）->rchild = rc->lchild;
    rc->lchild = *T;
    *T = rc;
}

/**
 * 左平衡
 * @param T AVL树根节点
 */
void LeftBalance（BBSTree *T） {
    BBSTree lc = NULL;
    BBSTree rd = NULL;
    lc = （*T）->lchild;
    switch （lc->bf） {
        case LH: {
            // LL型，直接右旋转T
            （*T）->bf = lc->bf = EH;
            R_Rotate（T）;
            break;
        }
            // 删除结点时有该可能性
        case EH: {
            （*T）->bf = LH;
            （*T）->lchild->bf = RH;
            R_Rotate（T）;
            break;
        }
        case RH: {
            // LR型，分为三种情况
            rd = lc->rchild;
            switch （rd->bf） {
                case LH: {
                    // 左子树的右子树存在左孩子
                    （*T）->bf = RH;
                    lc->bf = EH;
                    break;
                }
                case EH: {
                    // 左子树的右子树不存在孩子
                    （*T）->bf = lc->bf = EH;
                    break;
                }
                case RH: {
                    // 左子树的右子树存在右孩子
                    （*T）->bf = EH;
                    lc->bf = LH;
                    break;
                }
                default:
                    break;
            }
            // 先左旋后右旋
            rd->bf = EH;
            L_Rotate（&（*T）->lchild）;
            R_Rotate（T）;
        }
        default: {
            break;
        }
    }
}

/**
 * 右平衡
 * @param T AVL树根节点
 */
void RightBalance（BBSTree *T） {
    BBSTree rc = NULL;
    BBSTree rd = NULL;
    rc = （*T）->rchild;
    switch （rc->bf） {
        case RH: {
            // RR型，直接左旋转T
            （*T）->bf = rc->bf = EH;
            L_Rotate（T）;
            break;
        }
        case EH: {
            （*T）->bf = RH;
            （*T）->rchild->bf = LH;
            L_Rotate（T）;
            break;
        }
        case LH: {
            // RL型，分为三种情况
            rd = rc->lchild;
            switch （rd->bf） {
                case LH: {
                    // 右子树的左子树存在左孩子
                    （*T）->bf = EH;
                    rc->bf = RH;
                    break;
                }
                case EH: {
                    // 右子树的左子树不存在孩子
                    （*T）->bf = rc->bf = EH;
                    break;
                }
                case RH: {
                    // 右子树的左子树存在右孩子
                    （*T）->bf = LH;
                    rc->bf = EH;
                    break;
                }
                default:
                    break;
            }
            // 先右旋再左旋
            rd->bf = EH;
            R_Rotate（&（*T）->rchild）;
            L_Rotate（T）;
            break;
        }
        default:
            break;
    }
}

/**
 * e插入到二叉树
 * @param T AVL树根节点
 * @param e 插入数值
 * @param tall

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         98  2018-12-12 01:01  AVL\.idea\AVL.iml

     文件        153  2018-12-12 01:02  AVL\.idea\codestyles\codestyleConfig.xml

     文件       1803  2018-12-12 01:01  AVL\.idea\codestyles\Project.xml

     文件        376  2019-01-10 01:20  AVL\.idea\encodings.xml

     文件        246  2018-12-12 01:01  AVL\.idea\misc.xml

     文件        265  2018-12-12 00:59  AVL\.idea\modules.xml

     文件      18926  2019-01-12 17:52  AVL\.idea\workspace.xml

     文件      22227  2019-01-11 20:46  AVL\AVL.c

     文件       5869  2019-01-11 20:15  AVL\AVL.h

     文件       6262  2019-01-11 19:22  AVL\cmake-build-debug\AVL.cbp

     文件      77257  2019-01-12 17:51  AVL\cmake-build-debug\AVL.exe

     文件      38501  2019-01-10 01:20  AVL\cmake-build-debug\CMakeCache.txt

     文件       2492  2018-12-12 00:59  AVL\cmake-build-debug\CMakeFiles\3.12.2\CMakeCCompiler.cmake

     文件       5209  2019-01-06 20:06  AVL\cmake-build-debug\CMakeFiles\3.12.2\CMakeCXXCompiler.cmake

     文件      48314  2018-12-12 00:59  AVL\cmake-build-debug\CMakeFiles\3.12.2\CMakeDetermineCompilerABI_C.bin

     文件      49343  2019-01-06 20:06  AVL\cmake-build-debug\CMakeFiles\3.12.2\CMakeDetermineCompilerABI_CXX.bin

     文件        244  2018-12-12 00:59  AVL\cmake-build-debug\CMakeFiles\3.12.2\CMakeRCCompiler.cmake

     文件        395  2018-12-12 00:59  AVL\cmake-build-debug\CMakeFiles\3.12.2\CMakeSystem.cmake

     文件      48434  2018-12-12 00:59  AVL\cmake-build-debug\CMakeFiles\3.12.2\CompilerIdC\a.exe

     文件      19611  2018-12-12 00:59  AVL\cmake-build-debug\CMakeFiles\3.12.2\CompilerIdC\CMakeCCompilerId.c

     文件      49482  2019-01-06 20:06  AVL\cmake-build-debug\CMakeFiles\3.12.2\CompilerIdCXX\a.exe

     文件      19126  2019-01-06 20:06  AVL\cmake-build-debug\CMakeFiles\3.12.2\CompilerIdCXX\CMakeCXXCompilerId.cpp

     文件      17981  2019-01-11 20:46  AVL\cmake-build-debug\CMakeFiles\AVL.dir\AVL.obj

     文件       4988  2019-01-10 00:34  AVL\cmake-build-debug\CMakeFiles\AVL.dir\build.make

     文件        364  2019-01-12 17:51  AVL\cmake-build-debug\CMakeFiles\AVL.dir\C.includecache

     文件        308  2019-01-11 19:22  AVL\cmake-build-debug\CMakeFiles\AVL.dir\cmake_clean.cmake

     文件         38  2018-12-12 11:39  AVL\cmake-build-debug\CMakeFiles\AVL.dir\cmake_clean_target.cmake

     文件        298  2019-01-12 17:51  AVL\cmake-build-debug\CMakeFiles\AVL.dir\depend.internal

     文件        303  2019-01-12 17:51  AVL\cmake-build-debug\CMakeFiles\AVL.dir\depend.make

     文件        676  2019-01-10 00:34  AVL\cmake-build-debug\CMakeFiles\AVL.dir\DependInfo.cmake

............此处省略59个文件信息