C++数据结构之：树Tree

devtools/2024/10/11 9:25:24/

摘要：

   it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

   此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图，通过介绍概念以及提及一些可能适用的场景，并以C++代码简易实现，多方面认识数据结构，最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是树Tree。

（开发环境：VScode，C++17）

关键词： C++，数据结构，树，Tree

声明：本文作者原创，转载请附上文章出处与本文链接。

(文章目录：)

文章目录

      • 摘要：
      • 正文：
        • 介绍：
          • 特性：
          • 应用：
        • 代码实现：
        • 对应STL：
      • 推荐阅读

正文：

介绍：

   数据结构中的“树”是一种非常重要的非线性数据结构，由n（n≥0）个有限节点组成一个具有层次关系的集合。之所以被称为“树”，是因为它看起来像一棵倒挂的树，即根朝上，叶朝下。树的结构特点是：

  • 每个节点有零个或多个子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树。

其中红黑树和二叉树最为常用。

在这里插入图片描述

树的术语：

  • 节点：树中的每个元素。
  • 根节点：没有父节点的节点。
  • 子节点：一个节点含有的子树的根节点。
  • 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
  • 兄弟节点：具有相同父节点的节点。
  • 树的度：一棵树中，最大的节点的度。
  • 树的深度或高度：树中节点的最大层次。
  • 叶子节点或终端节点：度为0的节点。
  • 非叶子节点或分支节点：度不为0的节点。
  • 森林：由n棵互不相交的树的集合称为森林。
特性：

  • 层次结构：树具有清晰的层次结构，每个节点都位于一个特定的层次上。根节点位于第一层，其子节点位于第二层，依此类推。这种层次结构使得树能够表示具有层次关系的数据。

  • 无环性：在树中，从一个节点出发，沿着父节点-子节点的关系向下（或向上）遍历，不可能回到原点，除非整个遍历过程已经完成。换句话说，树中不存在环路或循环。

  • 根节点唯一：树中只有一个根节点，它是树的起点。所有的其他节点都直接或间接地连接到根节点。

  • 遍历性：树支持多种遍历方式，如先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。这些遍历方式对于实现各种算法和数据结构操作非常重要。

应用：
  • 利用树型结构可以求解集合的幂集问题，如集合{1，2，…，n}的幂集问题。
  • 在计算机科学中，树被广泛应用于各种算法和数据结构中，如二叉搜索树、AVL树、红黑树等，用于实现高效的查找、插入和删除操作。
  • 树被广泛应用于各种场景，如文件夹目录、公司组织关系、编译器设计、数据库索引、网络路由协议等。
代码实现：
#ctree.h
#ifndef CTREE_H
#define CTREE_H
#include<iostream>
using namespace std;// 树节点
template<class T>
class TreeNode
{
public:int index;                    // 坐标T data;                       // 数据TreeNode<T> *pLChild;         // 左节点TreeNode<T> *pRChild;         // 右节点TreeNode<T> *pParent;         // 父节点public:TreeNode():index(0),data('0'),pLChild(NULL),pRChild(NULL),pParent(NULL) {}TreeNode(int iNodeIndex, T val):index(iNodeIndex),data(val),pLChild(NULL),pRChild(NULL),pParent(NULL) {}~TreeNode(){}TreeNode<T>* SearchNode(int iNodeIndex);    // 通过序号坐标搜寻对应的节点void DeleteNode();                          // 删除此树节点void PreOrderTraversal();                   // 先序遍历 根左右void InOrderTraversal();                    // 中序遍历 左根右void PostOrderTraversal();                  // 后序遍历 左右根private:// 禁止拷贝、赋值TreeNode(const TreeNode<T>& node);TreeNode& operator=(const TreeNode<T>& node);
};template <class T>
inline TreeNode<T>* TreeNode<T>::SearchNode(int iNodeIndex)
{if (index == iNodeIndex){return this;}TreeNode<T> *temp = NULL;if (pLChild){if (pLChild->index == iNodeIndex){return pLChild;}else{temp = pLChild->SearchNode(iNodeIndex);if (temp){return temp;}}}if (pRChild){if (pRChild->index == iNodeIndex){return pRChild;}else{temp = pRChild->SearchNode(iNodeIndex);if (temp){return temp;}}}return NULL;
}template <class T>
inline void TreeNode<T>::DeleteNode()
{if (pLChild != NULL){pLChild->DeleteNode();}if (pRChild != NULL){pRChild->DeleteNode();}if (pParent != NULL){if (this == pParent->pLChild)pParent->pLChild = NULL;if (this == pParent->pRChild)pParent->pRChild = NULL;}delete this;
}template <class T>
inline void TreeNode<T>::PreOrderTraversal()
{cout << data << " ";if (pLChild){pLChild->PreOrderTraversal();}if (pRChild){pRChild->PreOrderTraversal();}
}template <class T>
inline void TreeNode<T>::InOrderTraversal()
{if (pLChild){pLChild->InOrderTraversal();}cout << data << " ";if (pRChild){pRChild->InOrderTraversal();}
}template <class T>
void TreeNode<T>::PostOrderTraversal()
{if (pLChild){pLChild->PostOrderTraversal();}if (pRChild){pRChild->PostOrderTraversal();}cout << data << " ";
}// 基于链表的二叉树基本实现和遍历
template <class T>
class CTree
{
public:CTree(TreeNode<T> *pNode = NULL);~CTree(){ m_pRoot->DeleteNode(); }TreeNode<T>* SearchNode(int index){ return m_pRoot->SearchNode(index); }bool AddNode(int index, int direction, TreeNode<T> *pNode);bool DeleteNode(int index, TreeNode<T> *pNode);// 先序遍历-递归void Recursive_PreOrderTraversal(){ m_pRoot->PreOrderTraversal(); }// 中序遍历-递归void Recursive_InOrderTraversal(){ m_pRoot->InOrderTraversal(); }// 后序遍历-递归void Recursive_PostOrderTraversal(){ m_pRoot->PostOrderTraversal(); }// 先序遍历-非递归void PreOrderTraversal();//中序遍历-非递归void InOrderTraversal();//后序遍历-非递归void PostOrderTraversal();private:TreeNode<T> *m_pRoot; //根节点
};template <class T>
inline CTree<T>::CTree(TreeNode<T> *pNode)
{// 创建树默认先创建根节点m_pRoot = new TreeNode<T>();if (!m_pRoot){throw "根节点申请内存失败";return;}if (pNode){m_pRoot->index = 0;m_pRoot->data = pNode->data;}else{m_pRoot->index = 0;m_pRoot->data = '0';}
}template <class T>
inline bool CTree<T>::AddNode(int index, int direction, TreeNode<T> *pNode)
{if (!pNode){cout << "插入失败！新增的节点值为空。" << endl;return false;}TreeNode<T> *temp = SearchNode(index);if (!temp){cout << pNode->data << "插入失败！找不到传入下标对应的父节点。" << endl;return false;}TreeNode<T> *node = new TreeNode<T>();if (!node){cout << pNode->data << "插入失败！新的节点申请内存失败。" << endl;return false;}node->index = pNode->index;node->data = pNode->data;node->pParent = temp;if (1 == direction){temp->pLChild = node;}else if (2 == direction){temp->pRChild = node;}else{cout << pNode->data << "插入失败！direction参数错误：1为左节点，2为右节点" << endl;}return true;
}template <class T>
inline bool CTree<T>::DeleteNode(int index, TreeNode<T> *pNode)
{TreeNode<T> *temp = SearchNode(index);if (!temp){cout << "删除失败！找不到传入下标对应的节点。" << endl;return false;}if (pNode){pNode->index = temp->index;pNode->data = temp->data;}temp->DeleteNode();return true;
}template <class T>
inline void CTree<T>::PreOrderTraversal()
{int stackTop = -1;TreeNode<T>* nodeStack[10];TreeNode<T>* pMove = m_pRoot;while (stackTop != -1 || pMove){while (pMove){cout << pMove->data << " ";nodeStack[++stackTop] = pMove;pMove = pMove->pLChild;}if (stackTop != -1){pMove = nodeStack[stackTop];stackTop--;pMove = pMove->pRChild;}}
}template <class T>
inline void CTree<T>::InOrderTraversal()
{int stackTop = -1;TreeNode<T>* nodeStack[10];TreeNode<T>* pMove = m_pRoot;while (stackTop != -1 || pMove){while (pMove){nodeStack[++stackTop] = pMove;pMove = pMove->pLChild;}if (stackTop != -1){pMove = nodeStack[stackTop--];cout << pMove->data << " ";pMove = pMove->pRChild;}}
}template <class T>
inline void CTree<T>::PostOrderTraversal()
{int stackTop = -1;TreeNode<T>* nodeStack[10];TreeNode<T>* pMove = m_pRoot;TreeNode<T>* pLastVisit = NULL;while (pMove){nodeStack[++stackTop] = pMove;pMove = pMove->pLChild;}while (stackTop != -1){pMove = nodeStack[stackTop--];if (pMove->pRChild == NULL || pMove->pRChild == pLastVisit){cout << pMove->data << " ";pLastVisit = pMove;}else{nodeStack[++stackTop] = pMove;pMove = pMove->pRChild;while (pMove){nodeStack[++stackTop] = pMove;pMove = pMove->pLChild;}}}
}#endif // !CTREE_H

#ctree.cpp
#include "ctree.h"
using namespace std;int main(int argc, char**argv)
{TreeNode<char> nodeA(0, 'A');TreeNode<char> nodeB(1, 'B');TreeNode<char> nodeC(2, 'C');TreeNode<char> nodeD(3, 'D');TreeNode<char> nodeE(4, 'E');TreeNode<char> nodeF(6, 'F');TreeNode<char> nodeG(9, 'G');CTree<char> *tree = new CTree<char>(&nodeA);tree->AddNode(0, 1, &nodeB);tree->AddNode(0, 2, &nodeC);tree->AddNode(1, 1, &nodeD);tree->AddNode(1, 2, &nodeE);tree->AddNode(2, 2, &nodeF);tree->AddNode(4, 1, &nodeG);cout << "recursive traversal:" << endl;tree->Recursive_PreOrderTraversal();cout << endl;tree->Recursive_InOrderTraversal();cout << endl;tree->Recursive_PostOrderTraversal();cout << endl;cout << "non recursive traversal:" << endl;tree->PreOrderTraversal();cout << endl;tree->InOrderTraversal();cout << endl;tree->PostOrderTraversal();cout << endl;delete tree;return 0;
}

在这里插入图片描述

对应STL：

   set，multiset，map，multimap这四种容器的共同点是：底层使用了平衡搜索树（即红黑树），容器中的元素是一个有序的序列。

   网络上有对 map VS unordered_map 效率对比的测试，通常 map 增删元素的效率更高，unordered_map 访问元素的效率更高，另外，unordered_map 内存占用更高，因为底层的哈希表需要预分配足量的空间。其它 xxx 和 unordered_xxx 区别也一样。

基于红黑树的集合

  • set：

    set 是一个关联型容器，它的底层结构是红黑树，set 是直接保存 value 的，或者说，set 中的 value 就是 key。set 中的元素必须是唯一的，不允许出现重复的元素，且元素不可更改，但可以自由插入或者删除。

  • multiset：

    multiset 和 set 底层都是红黑树，multiset 相比于 set 支持保存多个相同的元素；

基于红黑树的映射

  • map：

    map 是一个关联型容器，其元素类型是由 key 和 value 组成的 std::pair，实际上 map 中元素的数据类型正是 typedef pair<const Key, T> value_type;

  • multimap：

    multimap 和 map 底层都是红黑树，multimap 相比于 map 支持保存多个key相同的元素。

推荐阅读

C/C++专栏：https://blog.csdn.net/weixin_45068267/category_12268204.html
（内含其它数据结构及对应STL容器使用）


http://www.ppmy.cn/devtools/46352.html

相关文章

无障碍环境：科技融入日常，无障碍无处不在

无障碍环境：科技融入日常，无障碍无处不在

在当今社会&#xff0c;推动无障碍环境的建设已经成为提升全民福祉、实现社会包容性发展的重要议程。尤其对于盲人群体&#xff0c;一个精心设计的无障碍环境不仅意味着物理上的可达性&#xff0c;更是精神上的尊重与关怀&#xff0c;为他们打开了一扇通往独立生活与平等参与的…
阅读更多...
Linux 防火墙 firewalld 常用命令

Linux 防火墙 firewalld 常用命令

1 防火墙 - firewalld 1.1 开启防火墙 # 临时性开启&#xff0c;服务器重启后会恢复为原来的状态 systemctl start firewalld # 永久性开启&#xff08;即开机启动&#xff09;&#xff0c;重启服务器后生效 systemctl enable firewalld1.2 关闭防火墙 # 临时性关闭&#xf…
阅读更多...
RK3588+FPGA+算能BM1684X：高性能AI边缘计算盒子，应用于视频分析、图像视觉等

RK3588+FPGA+算能BM1684X：高性能AI边缘计算盒子，应用于视频分析、图像视觉等

搭载RK3588&#xff08;四核 A76四核 A55&#xff09;&#xff0c;CPU主频高达 2.4GHz &#xff0c;提供1MB L2 Cache 和 3MB L3 &#xff0c;Cache提供更强的 CPU运算能力&#xff0c;具备6T AI算力&#xff0c;可扩展至38T算力。 产品规格 系统主控CPURK3588&#xff0c;四核…
阅读更多...
Node.js和npm常用命令

Node.js和npm常用命令

一、Node.js简介 Node.js是一个免费、开源、跨平台的JavaScript运行时环境&#xff0c;允许开发人员创建服务器、web应用程序、命令行工具和脚本。 点击查看node.js中文官网 点击查看node.js英文官网 二、npm简介 npm(Node Package Manager)是Node.js的软件包管理器&#xff0…
阅读更多...
【CSS】object-fit 和 object-position 属性详解

【CSS】object-fit 和 object-position 属性详解

目录 object-fit属性属性值&#xff1a;使用场景&#xff1a; object-position 属性语法&#xff1a;例如&#xff1a;使用场景&#xff1a; object-fit和object-position是CSS属性&#xff0c;用于控制图像或视频在其容器中的适应和定位方式。 object-fit属性 属性值&#xf…
阅读更多...
[数据分享]人口密度数据

[数据分享]人口密度数据

数据是GIS的重要组成部分&#xff0c;也是我们进行研究分析的基础。在日常工作中&#xff0c;我们时常因数据问题而犯难&#xff0c;今天就进行一波有关人口密度数据的分享。 补充一点&#xff1a;排名不分先后&#xff0c;数据类型各异&#xff0c;请根据个人需要仔细甄别。 …
阅读更多...
C++ Thread多线程并发记录（3）线程创建总结

C++ Thread多线程并发记录（3）线程创建总结

1.启动线程传递全局函数 #include <iostream> #include <thread>void Th1(int id){std::cout << "Create global fun. id " << id << std::endl; } void TH1(const int &id){std::cout << "Create global fun. id &…
阅读更多...
【UE5 刺客信条动态地面复刻】实现无界地面01：动态生成

【UE5 刺客信条动态地面复刻】实现无界地面01：动态生成

2024.6.4更新 昨天半夜意识到生成Cube的方案不合适&#xff0c;又开始到处找动态地面的方法&#xff0c;发现了我想要的效果直接可以用nigara实现&#xff01;&#xff01;&#xff01;&#xff01; 于是这个部分就暂时告一段落&#xff0c;今季开始新的方向的学习。 为了快速…
阅读更多...
最新文章

Copyright @ 2022~2023