【谈谈】树的定义和基本概念

骑猪看日落 2021-12-18 12:51 303阅读 0赞

**定义**  
树(Tree)是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。并且当n＞0时满足下列条件：  
（1）有且仅有一个特定的称为根(Root)的结点；  
（2）当n＞1时，其余结点可以划分为m(m＞0)个互不相交的有限集T1、T2 、…、Tm，每个集Ti(1≤i≤m)均为树，且称为树T的子树(SubTree)。  
特别地，不含任何结点(即n＝0)的树，称为空树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]  
如上图，结点A是根root。节点F有一个父亲A并且由三个child。每一个节点可以有任意多个儿子，当然也可以没有儿子（此时这个节点称为leaf例如上图的B）。具有相同父亲的节点互称兄弟（siblings）节点。  
从节点n1到nk的路径（path）定义为n1,n2,…nk的一个序列，此时对于i∈\[1,k\]节点ni是ni+1的父亲。这条path的length是为此path上边的条数，即k-1。（从每个节点到它自己有一条长为0的路径）  
对任意节点ni,ni的depth为从root到ni的唯一路径的长。因而，root的depth=0。  
ni的height是从ni到一片树叶的最长路径的长（length）。因此，leaf的height=0。  
一棵树的height=root的height，一棵树的depth=它最深的树叶的depth;该深度总等于这棵树的高。  
**基本结构及常用术语**图片转自https://www.cnblogs.com/ysocean/p/8032642.html  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]: /images/20211218/cdabe47d0037450184f7b1e01faf4454.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 1]: /images/20211218/20c67a1b9100468f98b5b85196ece3c6.png