当前位置:首页 » 《随便一记》 » 正文

【数据结构】树的概念与结构 | 树的几种常见表示方法_#define _CRT_SECURE_NO_WARNINGS 1

18 人参与  2022年04月25日 09:44  分类 : 《随便一记》  评论

点击全文阅读


前言:

本章将正式开启数据结构中 “树” 部分的讲解,本章将介绍树的概念和结构,以及树的表示方法。


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 树在实际中的运用

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



点击全文阅读


本文链接:http://zhangshiyu.com/post/38892.html

节点  子树  指针  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1