树的概念及结构(一篇足以让你认识树)(2)

简介: 树的概念及结构(一篇足以让你认识树)


节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6


叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点


非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点


双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B 的父节点


孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节 点


兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点  


树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6


节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;


树的高度或深度:树中节点的最大层次; 如上图:树的高度为4


节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先


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


森林:由m(m>0)棵互不相交的多颗树的集合称为森林;(数据结构中的学习并查集本质就是 一个森林)



树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式, 如:双亲表示法,孩子兄弟表示法、孩子表示法等等。


我们这里了解一下孩子兄弟表示法、双亲表示法


①孩子兄弟表示法:


typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一个孩子结点
    struct Node* _pNextBrother;   // 指向其下一个兄弟结点
    DataType _data;               // 结点中的数据域
};

②双亲表示法

w2.png

 

树在实际中的运用(表示文件系统的目录树结构) 

w3.png

相关文章
|
程序员
程序员必知:原码、反码、补码和移码详解
程序员必知:原码、反码、补码和移码详解
1041 0
|
机器学习/深度学习 存储
数据的表示:原码、反码、补码、移码以及浮点数的运算
数据的表示:原码、反码、补码、移码以及浮点数的运算
734 0
数据的表示:原码、反码、补码、移码以及浮点数的运算
|
搜索推荐 算法 编译器
【C语言】qsort()函数详解:能给万物排序的神奇函数
【C语言】qsort()函数详解:能给万物排序的神奇函数
782 0
|
算法 Java
数据结构(13)最小生成树JAVA版:prim算法、kruskal算法
13.1.概述 最小生成树,包含图的所有顶点的一棵树,树的边采用包含在图中的原有边中权重和最小的边。翻译成人话就是遍历一遍全图所有顶点的最短路径,这条路径就叫最小生成树。 最小生成树存在和图是连通图互为充要条件,顶点都不连通,肯定不可能有路能遍历一遍全图。 求解最小生成树有两种常用算法:
510 0
|
存储 算法 搜索推荐
【算法系列篇】分治-归并
【算法系列篇】分治-归并
|
搜索推荐 C语言
【c语言】快速排序
【c语言】快速排序
153 0
|
5天前
|
云安全 人工智能 安全
AI被攻击怎么办?
阿里云提供 AI 全栈安全能力,其中对网络攻击的主动识别、智能阻断与快速响应构成其核心防线,依托原生安全防护为客户筑牢免疫屏障。
|
15天前
|
域名解析 人工智能
【实操攻略】手把手教学,免费领取.CN域名
即日起至2025年12月31日,购买万小智AI建站或云·企业官网,每单可免费领1个.CN域名首年!跟我了解领取攻略吧~