【第四节】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++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
使用C++将处理后的信号保存为PNG和TIFF格式

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...
使用C/C++调用libcurl调试消息的方式

使用C/C++调用libcurl调试消息的方式

《使用C/C++调用libcurl调试消息的方式》在使用C/C++调用libcurl进行HTTP请求时,有时我们需要查看请求的/应答消息的内容（包括请求头和请求体）以方便调试,libcurl提供了多种... 目录1. libcurl 调试工具简介2. 输出请求消息使用 CURLOPT_VERBOSE使用 C
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2