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)
#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;
}
代码中的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的节点了才到问题节点，这样的可以扩展开