【第四节】C/C++数据结构之树与二叉树

2024-06-07 21:44
文章标签 二叉树 c++ 数据结构 之树 第四节

本文主要是介绍【第四节】C/C++数据结构之树与二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、基本概念与术语

二、树的ADT

三、二叉树的定义和术语

四、平衡二叉树

4.1 解释

4.2 相关经典操作

4.3 代码展示

一、基本概念与术语

树(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。它具有以下性质：

  1. 它可以是空树2。
  2. 它的左子树和右子树的高度差的绝对值不超过12。
  3. 它的左子树和右子树都是平衡二叉树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                  k1k1   ==>       k2    NX  N              X
*///保存k1PTREE_NODE pK1 = pK2->pRChild;//保存XpK2->pRChild = pK1->pLChild;//k2变成k1的左子树pK1->pLChild = pK2;//k1变成k2pK2 = pK1;
}//************************************
// Method:    RightWhirl  右旋
// FullName:  CTree::RightWhirl
// Access:    private 
// Returns:   void
// Parameter: PTREE_NODE & pTree
//************************************
void CTree::RightWhirl(PTREE_NODE& pK2)
{
/*k2            k1k1     ==>    N    k2N  X               X
*///保存k1PTREE_NODE pK1 = pK2->pLChild;//保存XpK2->pLChild = pK1->pRChild;//k1的右子树为k2pK1->pRChild = pK2;//k2为k1pK2 = pK1;
}//************************************
// Method:    LeftRightWhirl 左右旋
// FullName:  CTree::LeftRightWhirl
// Access:    private 
// Returns:   void
// Parameter: PTREE_NODE & pTree
//************************************
void CTree::LeftRightWhirl(PTREE_NODE& pK2)
{
/*k2               k2              Nk1     左旋       N       右旋  K1   K2N             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                   Nk1    右旋       N     左旋    k2     K1N               [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;
}

这篇关于【第四节】C/C++数据结构之树与二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1040381。

相关文章

从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
C++11委托构造函数和继承构造函数的实现

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函
阅读更多...
C++11作用域枚举(Scoped Enums)的实现示例

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C
阅读更多...
C++链表的虚拟头节点实现细节及注意事项

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,：本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点（Dummy Head）一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二
阅读更多...
C++ 检测文件大小和文件传输的方法示例详解

C++ 检测文件大小和文件传输的方法示例详解

《C++检测文件大小和文件传输的方法示例详解》文章介绍了在C/C++中获取文件大小的三种方法,推荐使用stat()函数,并详细说明了如何设计一次性发送压缩包的结构体及传输流程,包含CRC校验和自动解... 目录检测文件的大小✅ 方法一：使用 stat() 函数（推荐）✅ 用法示例：✅ 方法二：使用 fsee
阅读更多...
Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2