C语言数据结构系列之树的概念结构和常见表示方法

0x00 树的概念

? 树是一种非线性的数据结构，它是由 n（n >= 0）个有限节点组成的一个具有层次关系的集合。

❓ 那么为什么叫 "树" 呢？

? 我们之所以把它成为 "树"，是因为它很像我们现实生活中的树。只是它是倒过来的，根朝上叶子朝下。

0x01 树的结构

① 有一个特殊的节点，成为根节点，根节点不存在前驱节点。

② 除根节点外，其余节点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，期中没一个集合 Ti(1 <= i <= m) 又是一颗结构于树类似的字数。每颗子树的节点有且只有一个前驱，可以有0个或多个后继。

③ 因此，树是递归定义的。因为任何树都会被分成根和子树。

?注意：树型结构中，子树之间不能有交集，否则就不是树形结构。

0x02 树的相关概念

?  节点的度：一个节点含有的子树的个数称为该节点的度。 比如上图中，A的度为6。

? 叶子结点：又称终端节点，度为0的节点称为叶子结点。 比如上图中，BCHIPQ等节点就是叶子结点，因为它们的度为0。

➰ 分支节点：又称非终端节点，度不为0的节点称为分支节点。 比如上图中，DEFG等节点就是分支节点，因为他们的度不为0。

? 父节点：又称双亲结点，若一个节点有子节点，则这个节点称作其子节点的父节点。 比如上图中，A是B的父节点。

? 子节点：又称孩子节点，若一个节点有根节点，则称为该节点的子节点。 如上图，B是A的子节点。

? 兄弟节点：具有相同父节点的节点互相称为兄弟节点。 同一个父亲生的才算。如上图，B和C是兄弟节点，它们的父节点都是A。

? 树的度：一棵树中最大的节点的度称为树的度。 如上图，最大的节点是A，有6个子树，故A的度为6，所以树的度为6。

? 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。 也有将根定义为第0层，根的子节点为第1层的。但是我们建议还是使用根为第1层来定义比较好。

? 树的高度：又称树的深度，树中节点的最大层次。 如上图，树的高度为 4。

?‍♂️ 堂兄弟节点：父节点在同一层的节点，它们互为堂兄弟。如上图，H 和 I 互为堂兄弟。

? 节点的祖先：从根到该节点所经分支上的所有节点。 如上图·，A是所有节点的祖先。

?‍?‍? 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 如上图，所有节点都是A的子孙。

? 森林：由 m(m > 0) 棵互不相交的树的集合称为森林。 比如并查集，多个树构成森林。

0x02 树的表示

❓ 以前学单链表时只有一个指针，双链表两个指针，但是树有多少个指针是不确定的，因为树没有规定一个节点最多有多少个孩子。那我们该如何定义结构呢？

? 方式一：假设说明了树的度为N，才能勉强用

struct Treenode {
    int data;
    struct TreeNode* sub[N]; // 指针数组
};

问题点：

① 可能会存在不少的空间浪费。 

② 万一没有限定树的度为多少呢？这个方式就废了。

? 方式二：vector

// 假设我们定义了一个顺序表
// typedef int STLDataType;  //顺序表的数据类型
 
// 顺序表中存节点的指针
typedef struct TreeNode* SLDataType; //SeqList
 
struct TreeNode {
    int data;
    SeqList s;  // s为SLDataType* array;
};

（c++中这里可以用 vector，但是C里没有）

即使你没有告诉我度是多少，我有多少个孩子我就存多少个孩子，所以这里不需要关心度的问题。但是这里 s 的结构相对复杂，s 里面有一个类型为SLDataType* 的数组，这个数组已经是二级指针了，SLDataType 展开后又是一个 struct TreeNode* 。

? 方式三：双亲表示法

利用结构数组存储（更加复杂）

struct TreeNode {
    int parenti;
    int data;
};

[ A -1] [ B0 ] [ C0 ] [ D0 ] ...... [ H 3 ]  

   ?  每一个元素中存的是结构体   struct TreeNode arr[10]

每个元素内只存自己的值和父亲的下标（A没有父亲是-1，B的父亲下标是0…… H的父亲是D下标为3），可以通过一个值找到自己父亲。

❓ 上列的方式各有优缺点，那么有没有最优的方法？

⚡ 当然有，它就是 —— 《左孩子右兄弟表示法》  有了这个方法，其他的都是渣渣！

typedef int DataType;
 
struct Node {
    struct Node* _firstChind1;   // 永远指向第一个孩子
    struct Node* _pNextBrother;  // 指向孩子右边的兄弟
    DataType _data;
};

? 解读：无论你有多少个孩子，它都只存两个指针。一个指针永远指向第一个孩子，另一个指针指向孩子右边的兄弟（亲兄弟）。这个树的度无论为多少，也不需要用顺序表存，但是你任何一个节点有多少个孩子都能给你表示出来，通过第一个孩子把所有孩子都找出来。不复杂也没有浪费，只用两个指针就把链接关系都表示出来了，不得不说设计这个的人真是太??了！

 0x03 树在实际中的运用

文件系统的目录树结构、网络拓扑，最短路径问题，搜索引擎、思维导图等

到此这篇关于C语言数据结构系列之树的常见表示方法的文章就介绍到这了,更多相关C语言 树的常见表示方法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！