【第四节】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++右移运算符的一个小坑及解决

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2