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

  • 开发
  • 9

目录

一、基本概念与术语

二、树的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                  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;
}

阅读全部

相关推荐

最近更新

  4. TCP协议是安全的吗?

    2024-06-07 21:42:05       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-06-07 21:42:05       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-06-07 21:42:05       19 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-06-07 21:42:05       20 阅读

热门阅读

  2. 数据结构：线索二叉树

    2024-06-07 21:42:05       10 阅读

  4. MFC：初步理解序列化与反序列化（含代码实现）

    2024-06-07 21:42:05       9 阅读

  8. yarn global add json-server报错（npm i json-server -g报错）

    2024-06-07 21:42:05       9 阅读

  10. Nutanix在.NEXT大会宣布AI战略升级：GPT-in-a-Box 2.0集成NVIDIA，强化企业级AI应用支持

    2024-06-07 21:42:05       8 阅读

  11. 大数据面试题第二期*6

    2024-06-07 21:42:05       11 阅读

  12. 查看Hive表的描述信息，包括在HDFS上的Location信息

    2024-06-07 21:42:05       10 阅读

  18. 东方博宜1760 - 整理抽屉

    2024-06-07 21:42:05       11 阅读

  23. 详解布隆过滤器，实现分布式布隆过滤器

    2024-06-07 21:42:05       8 阅读

  26. 【数据库系统概论】数据库设计过程

    2024-06-07 21:42:05       11 阅读

  27. Python 正则表达式：深入解析匹配多个模式

    2024-06-07 21:42:05       8 阅读

  28. (delphi11最新学习资料) Object Pascal 学习笔记---第14章泛型第2节（标准类的泛型方法）

    2024-06-07 21:42:05       10 阅读