目录
一、基本概念与术语
树(Tree)是由一个或多个结点组成的有限集合T。其中:
1 有一个特定的结点，称为该树的根(root)结点；
2 每个树都有且仅有一个特定的，称为根(Root)的节点。
树的常用术语：
1 当n>1时，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)；
2 节点的子树称为该节点的子节点(Child)，相应的，该节点称为子节点的父节点(Parent )；
3 同一个父节点的子节点之间称为兄弟节点(Sibling)；
4 节点的层次(Level)从根节点开始定义，根为第一层，根的子节点为第二层，双亲在同一层的节点互为堂兄弟，树中节点最大的层次称为树的深度或高度；
5 如果将树中节点的各子树看成从左到右是有次序的，不能互换的，则称该树为有序R树，否则称为无序树；
6 如果有n颗互不相交的树组成一个集合，则这个集合被称之为森林。
二、树的ADT
数据及关系:
具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为：
T＝（D，R）
其中D为树T中结点的集合，R为树中结点之间关系的集合。
D＝{Root}∪DF
其中，Root为树T的根结点，DF为树T的根Root的子树集合。
R＝{<Root，ri>，i＝1，2，…，m}
其中，ri是树T的根结点Root的子树Ti的根结点。
操作:
Constructor：
前提：已知根结点的数据元素之值。
结果：创建一棵树。
Getroot:
前提：已知一棵树。.
结果：得到树的根结点。
FirstChild：
前提：已知树中的某一指定结点 p。
结果：得到结点 p 的第一个儿子结点。
NextChild：
前提：已知树中的某一指定结点 p 和它的一个儿子结点 u。
结果：得到结点 p 的儿子结点 u 的下一个兄弟结点 v。
基本操作：
初始化一棵空树;
创建一棵树;
判断空树，为空返回True，否则返回False;
按照某特定顺序遍历一棵树;
求树的深度;
在树中某特定位置插入结点;
在树中某特定位置删除结点;
求某结点的双亲结点；
销毁树;
等等;
三、二叉树的定义和术语
二叉树(Tree)是n个节点的有限集合，该集合为空集(或称为空二叉树)，或者由一个根节点和两颗互不相交的、分别称为根节点的左子树与右子树的二叉树组成。
A. 所有节点都只有左子树的二叉树叫左斜树，所有节点都只有右子树的二叉树叫右斜树，这两者统称为斜树；
B. 在一棵二叉树中，如果所有分支节点都存在左子树与右子树，并且所有叶子都在同一层次上，这样的二叉树称为满二叉树；
C. 对一颗具有n个结点的二叉树按层序编号，如果编号i(1<i<n)的节点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全叉树。
四、平衡二叉树
4.1 解释
平衡二叉树（Balanced Binary Tree），又称为AVL树（有别于AVL算法），是一种特殊的二叉搜索树（Binary Search Tree）结构12。它具有以下性质：
- 它可以是空树2。
- 它的左子树和右子树的高度差的绝对值不超过12。
- 它的左子树和右子树都是平衡二叉树12。
平衡二叉树的设计目的是为了解决普通二叉搜索树在插入、删除等操作时可能产生的不平衡问题，从而避免树的高度过高，确保搜索效率始终保持在相对优化的水平。在平衡二叉树中，查找、插入和删除操作的时间复杂度都可以维持在O(logN)2。
平衡二叉树在计算机科学中有广泛的应用，例如：
- 数据库索引：用于加速数据库的查询操作3。
- 查找和排序：可以快速查找和排序数据3。
- 模拟实际问题：如航班预定系统中的座位分配3。
- 实现字典或符号表：键是树中的节点，值是与该键相关联的数据，支持高效的查找、插入和删除操作3。
- 实现线性数据结构：如栈、队列和优先队列3。
- 网络路由：用于实现网络路由表，进行快速的路由查找3。
- 文件系统：用于实现文件系统的索引结构，支持快速的文件查找和访问3。
总之，平衡二叉树是一种高效的数据结构，它通过保持树的平衡来优化搜索性能，并在各种应用中发挥着重要作用。
4.2 相关经典操作
平衡二叉树（AVL树）在插入或删除节点后，可能会破坏其平衡性（即左右子树的高度差超过1）。为了重新恢复平衡，需要进行旋转操作。旋转操作包括四种：左单旋、右单旋、左右旋和右左旋。下面我会逐一解释这四种操作：
1. 左单旋：
当某个节点的左子树的左子树插入了一个新节点，导致该节点失去平衡时，需要进行左单旋。
步骤：
- 以失去平衡的节点为根的子树中，找到该节点左子树的根节点（记作A）。
- 将A节点提升为新的根节点。
- 将原根节点变为A的右子树。
- A的左子树保持不变。
左单旋的结果是将不平衡向右侧转移。
左单旋举例：
针对节点8，它的左子树的高度是1，右子树的高度是3，高度差超过1.并且出错的节点13和15均位于节点8的右子节点12的右边，则通过左旋便可修复。
其一左单旋的结果：
动图展示：
2. 右单旋：
与左单旋对称，当某个节点的右子树的右子树插入了一个新节点，导致该节点失去平衡时，需要进行右单旋。
步骤：
- 以失去平衡的节点为根的子树中，找到该节点右子树的根节点（记作A）。
- 将A节点提升为新的根节点。
- 将原根节点变为A的左子树。
- A的右子树保持不变。
右单旋的结果是将不平衡向左侧转移。
右单旋举例：
针对节点8，它的左子树的高度为3，右子树高度为1，高度差超过1。并且出错的节点1和3位于8节点的左子节点4的左边。针对这种类型的非平衡树，通过右旋便可以使其重新平衡。
具体做法： 将节点8作为节点4的右子节点，节点6作为节点8的左子节点
其一右单旋的结果：
用一个动图来表示 右旋
3. 左右旋：
当某个节点的左子树的右子树插入了一个新节点，导致该节点失去平衡时，需要进行左右旋。
步骤：
- 先对失去平衡的节点的左子树进行右单旋。
- 再对整棵树进行左单旋。
左右旋实际上是右单旋和左单旋的组合，它首先尝试将不平衡向右侧转移，然后再将不平衡向左侧转移。
左右旋举例：
针对节点8，左子树的高度是3，右子树高度是1，高度差超过1。并且出错的节点5和7均位于节点8的左节点4的右边。这种情况需要先左旋再右旋便可恢复。
针对节点4进行左旋，左旋后变成了需要右旋的情况，可参考上面的右旋进行旋转即可。
4. 右左旋：
与左右旋对称，当某个节点的右子树的左子树插入了一个新节点，导致该节点失去平衡时，需要进行右左旋。
步骤：
- 先对失去平衡的节点的右子树进行左单旋。
- 再对整棵树进行右单旋。
右左旋实际上是左单旋和右单旋的组合，它首先尝试将不平衡向左侧转移，然后再将不平衡向右侧转移。
这些旋转操作确保了AVL树在插入或删除节点后仍然保持平衡，从而保证了树的搜索效率。在进行旋转操作时，还需要更新相关节点的高度信息，以便在后续操作中继续检查平衡性。
右左旋举例：
类似的针对12节点先进行右旋，再整体左旋，原理类似 不再赘述
4.3 代码展示
平衡二叉树的左单旋，右单旋，左右旋，右左旋操作代码演示
#include "Tree.h"
CTree::CTree() :m_pRoot(0), m_nCount(0)
{
}
CTree::~CTree()
{
}
//************************************
// Method: AddData 添加数据
// FullName: CTree::AddData
// Access: private
// Returns: bool
// Parameter: int nData
//************************************
bool CTree::AddData(int nData)
{
return AddData(m_pRoot, nData);
}
//************************************
// Method: AddData
// FullName: CTree::AddData
// Access: private
// Returns: bool
// Parameter: PTREE_NODE & pTree 根节点
// Parameter: int nData
//************************************
bool CTree::AddData(TREE_NODE*& pTree, int nData)
{
//pTree是否为空,如果为空说明有空位可以添加
if (!pTree)
{
pTree = new TREE_NODE{};
pTree->nElement = nData;
m_nCount++;
return true;
}
//与根做对比，小的放在其左子树，否则放在右子树
if (nData > pTree->nElement)
{
AddData(pTree->pRChild, nData);
//判断是否平衡
if (GetDeep(pTree->pRChild) -
GetDeep(pTree->pLChild) == 2)
{
//判断如何旋转
if (pTree->pRChild->pRChild)
{
//左旋
LeftWhirl(pTree);
}
else if (pTree->pRChild->pLChild)
{
//右左旋
RightLeftWhirl(pTree);
}
}
}
if (nData < pTree->nElement)
{
AddData(pTree->pLChild, nData);
//判断是否平衡
if (GetDeep(pTree->pLChild) -
GetDeep(pTree->pRChild) == 2)
{
//判断如何旋转
if (pTree->pLChild->pLChild)
{
//右旋
RightWhirl(pTree);
}
else if (pTree->pLChild->pLChild)
{
//左右旋
LeftRightWhirl(pTree);
}
}
}
}
//************************************
// Method: DelData 删除元素
// FullName: CTree::DelData
// Access: private
// Returns: bool
// Parameter: int nData
//************************************
bool CTree::DelData(int nData)
{
return DelData(m_pRoot, nData);
}
//************************************
// Method: DelData
// FullName: CTree::DelData
// Access: private
// Returns: bool
// Parameter: PTREE_NODE & pTree 根节点
// Parameter: int nData
//************************************
bool CTree::DelData(PTREE_NODE& pTree, int nData)
{
bool bRet = false;
//判断是否为空树
if (empty())
{
return false;
}
//开始遍历要删除的数据
if (pTree->nElement == nData)
{
//判断是否为叶子节点，是就可以直接删除，
//不是则需要找代替
if (!pTree->pLChild && !pTree->pRChild)
{
delete pTree;
pTree = nullptr;
m_nCount--;
return true;
}
//根据左右子树的深度查找要替换的节点
if (GetDeep(pTree->pLChild) >=
GetDeep(pTree->pRChild))
{
PTREE_NODE pMax = GetMaxOfLeft(pTree->pLChild);
pTree->nElement = pMax->nElement;
DelData(pTree->pLChild, pMax->nElement);
}
else
{
PTREE_NODE pMin = GetMinOfRight(pTree->pRChild);
pTree->nElement = pMin->nElement;
DelData(pTree->pRChild, pMin->nElement);
}
}
else if (nData > pTree->nElement)
{
bRet = DelData(pTree->pRChild, nData);
//判断是否平衡
if (GetDeep(pTree->pLChild) -
GetDeep(pTree->pRChild) == 2)
{
//判断如何旋转
if (pTree->pLChild->pLChild)
{
//右旋
RightWhirl(pTree);
}
else if (pTree->pLChild->pLChild)
{
//左右旋
LeftRightWhirl(pTree);
}
}
}
else /*if (nData < pTree->nElement)*/
{
bRet = DelData(pTree->pLChild, nData);
//判断是否平衡
if (GetDeep(pTree->pRChild) -
GetDeep(pTree->pLChild) == 2)
{
//判断如何旋转
if (pTree->pRChild->pRChild)
{
//左旋
LeftWhirl(pTree);
}
else if (pTree->pRChild->pLChild)
{
//右左旋
RightLeftWhirl(pTree);
}
}
}
return bRet;
}
//************************************
// Method: ClearTree 清空元素
// FullName: CTree::ClearTree
// Access: private
// Returns: void
//************************************
void CTree::ClearTree()
{
ClearTree(m_pRoot);
m_nCount = 0;
}
//************************************
// Method: ClearTree
// FullName: CTree::ClearTree
// Access: private
// Returns: void
// Parameter: PTREE_NODE & pTree 根节点
//************************************
void CTree::ClearTree(PTREE_NODE& pTree)
{
//从叶子节点开始删除
//删除其左右子树后再删除根节点本身
//判断是否为空树
if (empty())
{
return;
}
//判断是否为叶子节点
if (!pTree->pLChild && !pTree->pRChild)
{
delete pTree;
pTree = nullptr;
return;
}
ClearTree(pTree->pLChild);
ClearTree(pTree->pRChild);
ClearTree(pTree);
}
//************************************
// Method: TravsoualPre 前序遍历
// FullName: CTree::TravsoualPre
// Access: private
// Returns: void
//************************************
void CTree::TravsoualPre()
{
TravsoualPre(m_pRoot);
}
//************************************
// Method: TravsoualPre
// FullName: CTree::TravsoualPre
// Access: private
// Returns: void
// Parameter: PTREE_NODE pTree 根节点
//************************************
void CTree::TravsoualPre(PTREE_NODE pTree)
{
//递归的返回条件
if (!pTree)
{
return;
}
//根左右
printf("%d ", pTree->nElement);
TravsoualPre(pTree->pLChild);
TravsoualPre(pTree->pRChild);
}
//************************************
// Method: TravsoualMid 中序遍历
// FullName: CTree::TravsoualMid
// Access: private
// Returns: void
//************************************
void CTree::TravsoualMid()
{
TravsoualMid(m_pRoot);
}
//************************************
// Method: TravsoualMid
// FullName: CTree::TravsoualMid
// Access: private
// Returns: void
// Parameter: PTREE_NODE pTree 根节点
//************************************
void CTree::TravsoualMid(PTREE_NODE pTree)
{
//递归的返回条件
if (!pTree)
{
return;
}
//左根右
TravsoualMid(pTree->pLChild);
printf("%d ", pTree->nElement);
TravsoualMid(pTree->pRChild);
}
//************************************
// Method: TravsoualBack 后序遍历
// FullName: CTree::TravsoualBack
// Access: private
// Returns: void
//************************************
void CTree::TravsoualBack()
{
TravsoualBack(m_pRoot);
}
//************************************
// Method: TravsoualBack
// FullName: CTree::TravsoualBack
// Access: private
// Returns: void
// Parameter: PTREE_NODE pTree 根节点
//************************************
void CTree::TravsoualBack(PTREE_NODE pTree)
{
//递归的返回条件
if (!pTree)
{
return;
}
//左右根
TravsoualBack(pTree->pLChild);
TravsoualBack(pTree->pRChild);
printf("%d ", pTree->nElement);
}
//************************************
// Method: 层序遍历
// FullName: CTree::LevelTravsoual
// Access: public
// Returns: void
//************************************
void CTree::LevelTravsoual()
{
vector<PTREE_NODE> vecRoot; //保存根节点
vector<PTREE_NODE> vecChild; //保存根节点的子节点
vecRoot.push_back(m_pRoot);
while (vecRoot.size())
{
for (int i = 0; i < vecRoot.size();i++)
{
printf("%d ", vecRoot[i]->nElement);
//判断其是否左右子节点
if (vecRoot[i]->pLChild)
{
vecChild.push_back(vecRoot[i]->pLChild);
}
if (vecRoot[i]->pRChild)
{
vecChild.push_back(vecRoot[i]->pRChild);
}
}
vecRoot.clear();
vecRoot = vecChild;
vecChild.clear();
printf("\n");
}
}
//************************************
// Method: GetCount 获取元素个数
// FullName: CTree::GetCount
// Access: public
// Returns: int
//************************************
int CTree::GetCount()
{
return m_nCount;
}
//************************************
// Method: GetDeep 获取节点深度
// FullName: CTree::GetDeep
// Access: private
// Returns: int
// Parameter: PTREE_NODE & pTree
//************************************
int CTree::GetDeep(PTREE_NODE pTree)
{
//判断pTree是否为空
if (!pTree)
{
return 0;
}
int nL = GetDeep(pTree->pLChild);
int nR = GetDeep(pTree->pRChild);
//比较左右子树的深度，取最大值加 1 返回
return (nL >= nR ? nL : nR) + 1;
}
//************************************
// Method: GetMaxOfLeft 获取左子树中的最大值
// FullName: CTree::GetMaxOfLeft
// Access: private
// Returns: PTREE_NODE
// Parameter: PTREE_NODE pTree
//************************************
PTREE_NODE CTree::GetMaxOfLeft(PTREE_NODE pTree)
{
//只要存在右子树就有更大的值
//是否空
if (!pTree)
{
return 0;
}
//判断是否有右子树
while (pTree->pRChild)
{
pTree = pTree->pRChild;
}
//返回最大值节点
return pTree;
}
//************************************
// Method: GetMinOfRight 获取右子树中的最小值
// FullName: CTree::GetMinOfRight
// Access: private
// Returns: PTREE_NODE
// Parameter: PTREE_NODE pTree
//************************************
PTREE_NODE CTree::GetMinOfRight(PTREE_NODE pTree)
{
//只要存在左子树就有更小的值
//是否空
if (!pTree)
{
return 0;
}
//判断是否有右子树
while (pTree->pLChild)
{
pTree = pTree->pLChild;
}
return pTree;
}
//************************************
// Method: LeftWhirl 左旋
// FullName: CTree::LeftWhirl
// Access: private
// Returns: void
// Parameter: PTREE_NODE & pTree
//************************************
void CTree::LeftWhirl(PTREE_NODE& pK2)
{
/*
k2 k1
k1 ==> k2 N
X N X
*/
//保存k1
PTREE_NODE pK1 = pK2->pRChild;
//保存X
pK2->pRChild = pK1->pLChild;
//k2变成k1的左子树
pK1->pLChild = pK2;
//k1变成k2
pK2 = pK1;
}
//************************************
// Method: RightWhirl 右旋
// FullName: CTree::RightWhirl
// Access: private
// Returns: void
// Parameter: PTREE_NODE & pTree
//************************************
void CTree::RightWhirl(PTREE_NODE& pK2)
{
/*
k2 k1
k1 ==> N k2
N X X
*/
//保存k1
PTREE_NODE pK1 = pK2->pLChild;
//保存X
pK2->pLChild = pK1->pRChild;
//k1的右子树为k2
pK1->pRChild = pK2;
//k2为k1
pK2 = pK1;
}
//************************************
// Method: LeftRightWhirl 左右旋
// FullName: CTree::LeftRightWhirl
// Access: private
// Returns: void
// Parameter: PTREE_NODE & pTree
//************************************
void CTree::LeftRightWhirl(PTREE_NODE& pK2)
{
/*
k2 k2 N
k1 左旋 N 右旋 K1 K2
N k1 [x] [x]
[x]
*/
LeftWhirl(pK2->pLChild);
RightWhirl(pK2);
}
//************************************
// Method: RightLeftWhirl 右左旋
// FullName: CTree::RightLeftWhirl
// Access: private
// Returns: void
// Parameter: PTREE_NODE & pTree
//************************************
void CTree::RightLeftWhirl(PTREE_NODE& pK2)
{
/*
k2 k2 N
k1 右旋 N 左旋 k2 K1
N [x] k1 [x]
[x]
*/
RightWhirl(pK2->pRChild);
LeftWhirl(pK2);
}
bool CTree::empty()
{
return m_pRoot == 0;
}
调用代码：
#include "Tree.h"
int main()
{
CTree tree;
tree.AddData(1);
tree.AddData(2);
tree.AddData(3);
tree.AddData(4);
tree.AddData(5);
tree.AddData(6);
tree.AddData(7);
tree.AddData(8);
tree.AddData(9);
tree.AddData(10);
tree.LevelTravsoual();
tree.DelData(4);
tree.LevelTravsoual();
return 0;
}