数据结构——树——树的表示

朱雀 2022-04-16 03:50 276阅读 0赞

## 树的定义： ##

树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：  
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；  
![在这里插入图片描述][20181116150432748.png]![在这里插入图片描述][20181116150504340.png]

## 树的一些基本术语 ##

**1. 结点的度（Degree）：结点的子树个数  
2. 树的度：树的所有结点中最大的度数**  
**3. 叶结点（Leaf）：度为0的结点  
4. 父结点（Parent）：有子树的结点是其子树 的根结点的父结点  
5. 子结点（Child）：若A结点是B结点的父结 点，则称B结点是A结点的子结点；子结点也 称孩子结点。  
6. 兄弟结点（Sibling）：具有同一父结点的各 结点彼此是兄弟结点。  
7. 路径和路径长度：从结点n1到nk的路径为一 个结点序列n1 , n2 ,… , nk , ni是 ni+1的父结 点。路径所包含边的个数为路径的长度。  
8. 祖先结点(Ancestor)：沿树根到某一结点路 径上的所有结点都是这个结点的祖先结点。  
9. 子孙结点(Descendant)：某一结点的子树 中的所有结点是这个结点的子孙。  
10. 结点的层次（Level）：规定根结点在1层， 其它任一结点的层数是其父结点的层数加1。  
11. 结点的层次（Level）：规定根结点在1层， 其它任一结点的层数是其父结点的层数加1。  
12. 树的深度（Depth）：树中所有结点中的最 大层次是这棵树的深度。**  
![在这里插入图片描述][20181116151130467.png]![在这里插入图片描述][20181116151205930.png]

[20181116150432748.png]: https://img-blog.csdnimg.cn/20181116150432748.png
[20181116150504340.png]: /images/20220416/5b490c843b714194a045c9fa9e2c65d4.png
[20181116151130467.png]: https://img-blog.csdnimg.cn/20181116151130467.png
[20181116151205930.png]: /images/20220416/71308d144ff04b6fa3e18a3208736f6c.png