树的概念及结构(一篇足以让你认识树)(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

相关文章
|
6月前
|
存储 算法
树(Tree) - 概念与基础
树(Tree) - 概念与基础
112 2
树和二叉树的概念以及结构
树和二叉树的概念以及结构
|
5月前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
51 0
|
1月前
|
存储
二叉树的概念和结构
二叉树的概念和结构
34 0
|
5月前
|
机器学习/深度学习 存储 算法
数据结构和算法学习记录——树(基本介绍、树的定义、树的特点、树的一些基本术语、树的表示、儿子-兄弟表示法)
数据结构和算法学习记录——树(基本介绍、树的定义、树的特点、树的一些基本术语、树的表示、儿子-兄弟表示法)
95 0
|
6月前
|
存储
数据结构-树的介绍、树的定义和基本术语
树是一种非线性的数据结构,是以分支关系定义的层次结构,比如人类社会中的族谱、及各种机制、组织的关系都可以用树形象的表示。重点学习二叉树的存储和相关操作,还要讨论树、森林、二叉树的转换关系。
85 0
|
存储 JavaScript
50 # 树的概念
50 # 树的概念
50 0
|
存储 数据可视化 关系型数据库
|
C语言 C++
【哈夫曼树】基本概念、构建过程及C++代码
【哈夫曼树】基本概念、构建过程及C++代码
263 0
|
存储 算法 数据可视化
关于B+树的介绍、用途和c++代码实现
关于B+树的介绍、用途和c++代码实现