当前位置：首页 > news >正文

【数据结构】前言概况 - 树

news 2025/7/12 8:46:59

🚩纸上得来终觉浅，绝知此事要躬行。
🌟主页：June-Frost
🚀专栏：数据结构

🔥该文章针对树形结构作出前言，以保证可以对树初步认知。

🌍前言:

线性结构是一种相对简单的数据结构，元素之间按照一定的顺序排列，每个元素最多有两个接口：前驱和后继。这种结构相对直观，易于理解和管理，类似一种一对一的关系。相比之下，树形结构则更为复杂，变为了一对多的关系。元素之间的关系不再是简单的线性排列，而是以一个或多个根节点为起点，通过多个分支来连接不同的元素。每个节点可以拥有多个子节点，而且每个子节点可以有任意多的兄弟节点。这种结构需要更多的内存空间来存储元素之间的关系，同时也需要更高级的算法来操作和管理。从复杂性的角度来看，树形结构比线性结构更加复杂。
此外，树的应用广泛，如二叉树、红黑树、B树、哈夫曼树等。在计算机科学中，树的数据结构常常被用于对数据进行组织和存储，以便于高效地实现各种算法和操作。

🌎树

树是一种非线性的数据结构，它是由n(n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
①

注意：树是递归定义的，在树的定义中，一个树是由一个根节点和若干个子节点组成的，这些子节点本身也是一棵棵树。因此，树的结构和定义是相互嵌套的。通过递归定义，我们可以将一个树的结构描述为一个递归的过程，即每棵子树又包含着一个根节点和若干个子节点，直到叶节点为止。
⚠树形结构中，子树之间不能有交集，否则会成为图。
例如：

✉️相关概念

以上图①为例：

节点的度：一个节点含有的子树的个数称为该节点的度，如上图：A的为6。
叶节点或终端节点：度为0的节点称为叶节点，如上图：B、C、H、I…等节点为叶节点。
非终端节点或分支节点：度不为0的节点，如上图：D、E、F、G…等节点为分支节点。
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点，如上图：A是B的父节点。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点，如上图：B是A的孩子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点，如上图：B、C是兄弟节点。
树的度：一棵树中，最大的节点的度称为树的度，如上图：树的度为6。
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
树的高度或深度：树中节点的最大层次，如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟，如上图：H、I互为兄弟节点。
节点的祖先：从根到该节点所经分支上的所有节点，如上图：A是所有节点的祖先。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙，如上图：所有节点都是A的子孙。
森林：由m（m>0）棵互不相交的树的集合称为森林。

✉️ 树的存储

树的存储中既要保存值域，也要保存结点和结点之间的关系，有很多存储结构。例如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等

🌟孩子兄弟表示法（LCRS）

🌟双亲表示法

在每一个节点中，存储其父节点的下标。这样就可以将树中各节点的结构关系表示出来，也可以快速地对父节点进行访问。

✉️ 树的应用

树形结构的应用非常广泛。如：

数据库中的索引：数据库系统使用树形结构来实现索引，以提高数据访问效率。
电子邮件系统：电子邮件系统中的邮件通常是通过树形结构进行组织和管理的，每个邮件可以有多个回复或转发，形成一个树形结构。
编译器中的语法树：编译器将源代码解析为语法树，其中每个节点表示特定的语法结构，如一个函数、一个循环或一个条件语句。
文件系统的目录树结构。

在实践当中，用的最多的树是二叉树。

🌏 二叉树

一棵二叉树是结点的一个有限集合，该集合可以为空，也可以由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

对于任意的二叉树都是由以下几种情况复合而成的：

例如：

注意：

二叉树不存在度大于2的结点
由于二叉树最多有2个孩子，为了区分概念，就定义了左孩子和右孩子，所以二叉树的子树有左右之分，次序不能颠倒 —— 二叉树是有序树。

✉️ 特殊二叉树

🌟满二叉树
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。如果一个满二叉树的层数为K，结点总数就是2^h-1，同样的，如果一个满二叉树的节点总数为N，则层数为log₂(N+1)。
🌟满二叉树
假设有h层，前h-1层都是满的，最后一层不一定满，节点从左到右连续。要注意的是满二叉树是一种特殊的完全二叉树。假设有h层，则完全二叉树的节点范围为 [ 2^(h-1) , 2^h - 1] 。
🌟一些性质：

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
对任何一棵二叉树, 如果度为0的其叶结点个数为n₀, 度为2的分支结点个数为n₂ ,则有 n₀＝ n₂＋1

✉️ 二叉树的存储

二叉树的存储结构通常可以采用顺序存储和链式存储两种。

链式存储：对于一般的二叉树，通常采用链式存储方式。每个节点包含三个字段：数据域、左孩子指针和右孩子指针。数据域用于存储节点的值，左孩子指针指向该节点的左子节点，右孩子指针指向该节点的右子节点。如果某个节点没有子节点，对应的指针就为空（NULL）。
顺序存储：对于完全二叉树，可以直接使用数组进行存储，将根节点存储在索引为1的位置，然后按照层次顺序从左到右，从上到下，对每个节点赋予一个唯一的索引。这种存储方式对于完全二叉树来说，可以节省存储空间，并且可以通过索引快速访问节点。

📚顺序存储结构和链式存储结构各有优劣，需要根据实际应用场景和需求来选择使用哪种存储方式。如果需要频繁查找且表的长度变化不大，可以使用顺序存储结构；如果需要频繁插入和删除操作且表的长度变化较大，使用链式存储结构可能会更好。