美丽乡村建设网站模板,国内高端医疗网站建设,北京云主机网站源码,济南网站建设xywlcn目录 一、前言
#x1f34e; 为什么要学习非线性结构 ---- 树#xff08;Tree#xff09;
#x1f4a6; 线性结构的优缺点 #x1f4a6; 优化方案 ----- 树#xff08;Tree#xff09;
#x1f4a6; 树的讲解流程 二、树的概念及结构
#x1f350; 树的概念 为什么要学习非线性结构 ---- 树Tree 线性结构的优缺点 优化方案 ----- 树Tree 树的讲解流程 二、树的概念及结构 树的概念 树的相关定义 树的表示方法 树在现实中的应用 树的性质超重要哦 性质1树中的节点数等于所有节点度数加 1 性质2度为 m 的树中第 i 层至多有 m^i-1 个节点i1 性质3高度为 h 的 m 叉树至多有 m^h-1/m-1 个节点 性质4具有n个结点的m叉树的最小高度为⌈logm(n*(m-1)1)⌉ 三、共勉 一、前言 在之前的几篇文章中已经详细的介绍了数据结构中的顺序表、链表、栈、队列、数组等都是一对一的线性关系。本文将开始介绍一种新的数据结构 --------- 树一对多的非线性关系。 那么肯定有 老铁 要发问啦有线性结构去存储数据为什么还要用非线性的结构去存储呢 它们之间有什么区别呢 接下里我将依次给大家解惑让大家真正的搞懂数据结构学习起来才有动力。 为什么要学习非线性结构 ---- 树Tree 线性结构的优缺点 在线性结构中无论是顺序存储还是链式存储线性表均有其优缺点 顺序表优点 1️⃣顺序存储可以在 O(1) 的时间内找到特定次序的元素下标的随机访问 2️⃣CPU 高速缓存命中率较高 顺序表缺点 1️⃣顺序存储在数据中间、头部 的插入和删除元素需要挪动大量元素需要时间O(n) 2️⃣: 顺序存储时会出现空间不足只能进行空间的扩容异地扩容代价比较大 链表优点 1️⃣在任意位置进行数据的插入和删除的效率高所需时间为O(1) 2️⃣: 按需申请空间和释放不存在扩容 链表的缺点 1️⃣在寻找特定次序的元素需要从链表头部向后查找需要时间O(n) 2️⃣: CPU高速缓存命中率低 ⭐ 其实链表和顺序表是一个互补的数据结构 ⭐ 链表详解 ⭐ 顺序表详解 优化方案 ----- 树Tree ⭐树形结构很好的结合了顺序表和链表的优点可以在O(logn)的时间内完成查找、更新、插入、删除等操作在实际的应用中很多算法可以借助于树形结构高效的实现很多功能。 树的讲解流程 此时此刻大家肯定很想了解什么是树在本篇博客中并不能把所有树的结构在此篇文章中进行详细的介绍我会通过步步延申的方式去讲解树。 树 ➡ 二叉树➡ 搜索二叉树 ➡ 平衡搜索二叉树 (AVL树和红黑树) ➡ M叉多叉平衡搜索树 (B树和B树) 二、树的概念及结构 树的概念 1️⃣树是一种非线性的数据结构它是由 n (n0) 个有限结点组成一个具有层次关系的集合。 2️⃣: 把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下。树根可以发出多个分支每个分支也可以继续发出分支树枝之间是不想交的。 3️⃣ 树有一个特殊的结点称为根结点根节点没有前驱结点 4️⃣除根节点外其余结点被分为 M (M0) 个互不相交的集合 T1、T2 … 、Tm其中每一个集合 Ti (1im) 又是一棵结构与树类似的子树每棵子树的根结点有且只有一个前驱可以有0个或多个后继 5️⃣因此树是递归定义的 ⚠ 注意树形结构中子树之间不能有交集否则就不是树形结构 ▶ 子树 是不相交的 ▶ 除了根节点外每个节点有且仅有一个父节点 ▶ 一棵 N 个节点的树有 N-1 条连 树的相关定义 1️⃣ 节点的度一个节点含有的子树的个数称为该节点的度 如上图A 的为6 2️⃣ 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 3️⃣ 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 4️⃣ 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A 是 B 的父节点 5️⃣ 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B 是 A 的孩子节点 6️⃣ 兄弟节点具有相同父节点的节点互称为兄弟节点 (这里指的是亲兄弟而非表堂兄弟) 如上图B、C 是兄弟节点 7️⃣ 树的度一棵树中最大的节点的度称为树的度 如上图树的度为 6 8️⃣ 节点的层次从根开始定义起根为第 1 层根的子节点为第 2 层 以此类推如上图树的层次为 4 9️⃣ 树的高度或深度树中节点的最大层次 (这里有 2 种说法其一根算 0其二根算 1) 如上图树的高度为 4 这里推荐理解其二因为 当要算空树的高度是多少时按其一的理解高度是 -1按其二的理解高度是 0 当要算只有一个根节点的树的高度是多少时按其一的理解高度是 0按其二的理解高度是 1 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I 互为兄弟节点 1️⃣1️⃣ 节点的祖先从根到该节点所经分支上的所有节点如上图A 是所有节点的祖先 1️⃣2️⃣ 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是 A 的子孙 1️⃣3️⃣ 森林由 m(m0) 棵互不相交的树的集合称为森林并查集就是一个森林 树的表示方法 1️⃣ 树结构相对线性表就比较复杂了要存储表示起来比较麻烦既要保存值域也要保存结点和结点之间的关系。 2️⃣ 实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 ⚠ 注意对于树的定义其实并不好定义因为其中有许多未知的因素 1️⃣明确说明树的度是多少比如树的度是 6 struct TreeNode
{int data;//这种结构其实是很浪费的因为最大的度是6,但往下可能并没有那么多struct TreeNode* subs[6];//指针数组
}⚠ 注意这种结构其实是很浪费的因为最大的度是6,但往下可能并没有那么多 2️⃣双亲表示法 struct TreeNode
{int data;struct TreeNode* parent;
}⚠ 注意这种结构主要应用在------并查集 3️⃣左孩子右兄弟表示法 (比较实用) typedef int DataTpye;
struct Node
{struct Node* _firstChild1;//第一个孩子节点(如有多个孩子那么只指向最左边的)struct Node* _pNextBrother;//指向下一个兄弟节点DataType _data;//节点中的数据域
}树在现实中的应用 ❗ 以下为 Linux 下的目录树 ❗ 由此可知在用树表示目录数据结构中从根目录到任何数据文件仅有唯一一条路径可以达到因为树的结构不是相交的。 树的性质超重要哦 性质1树中的节点数等于所有节点度数加 1 ✨从上图可知有 12 个节点 A的度为3 B的度为2 C 的度为1 D的度为2 E的度为1 F的度为0 G的度为2 H的度为0 I的度为0J的度为0K的度0L的度为0。 ✨由性质 1 可知 树的节点个数 每个节点的度数 1 所以上图 树的节点数 3212102000001 12 性质2度为 m 的树中第 i 层至多有 m^i-1 个节点i1 性质3高度为 h 的 m 叉树至多有 m^h-1/m-1 个节点 性质4具有n个结点的m叉树的最小高度为⌈logm(n*(m-1)1)⌉ 三、共勉
以下就是我对数据结构---树的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对数据结构-------二叉树请持续关注我哦
