树的概念及通用树的实现（转载）

秒速五厘米 2022-10-22 10:54 94阅读 0赞

文章来源 请看：

参考 ：[https://blog.csdn.net/snailmann/article/details/88607659?utm\_medium=distribute.pc\_relevant.none-task-blog-baidujs\_title-5&spm=1001.2101.3001.4242][https_blog.csdn.net_snailmann_article_details_88607659_utm_medium_distribute.pc_relevant.none-task-blog-baidujs_title-5_spm_1001.2101.3001.4242]

参考：[https://blog.csdn.net/weixin\_43767015/article/details/105710620][https_blog.csdn.net_weixin_43767015_article_details_105710620]

参考：  [https://blog.51cto.com/11134889/2140088][https_blog.51cto.com_11134889_2140088]

1.树的定义与操作

## 1.1.树的相关定义 ##

### 1.树的定义 ###

树是一种非线性的数据结构，右n(n>=0)个结点组成的有限集合，如果n=0,称为空树，如果n>0,则：

*  有一个特定的结点被称之为跟结点(root)，根结点只有直接后继，没有前驱，
 *  除根结点外的其他结点划分为m(m>=0)个互不相交的有限集合T0,T1...Tm-1，每一个集合又是一颗子树，并称之为跟的子树。  
    树的示例如下：  
    ![数据结构（12）\_树的概念及通用树的实现][12]
    
    ### 2.树中度的概念 ###
    
    树的结点包含一个数据及若干指向子树的分支，结点拥有的子树数目称为结点的度(度为0的结点称为叶结点；度不为0称为分支结点)；  
    树的度定义为所有结点中度的最大值。  
    ![数据结构（12）\_树的概念及通用树的实现][12 1]
    
    ### 3.树的前驱和后继 ###
    
    结点的直接后继称为该结点的孩子，相应的，该结点称为孩子的双亲；  
    结点的孩子的孩子，称为该结点的子孙，相应 该结点称为子孙的祖先；  
    同一个双亲的孩子之间互称兄弟。  
    ![数据结构（12）\_树的概念及通用树的实现][12 2]
    
    ### 4.树中结点的层次 ###
    
    树中结点最大层次称为树的深度或高度。  
    ![数据结构（12）\_树的概念及通用树的实现][12 3]
    
    ### 5.树的有序性 ###
    
    如果树中结点的各个子树从左向右是有次序的，子树间不能互换位置，则称该树为有序树，否则为无序树。  
    ![数据结构（12）\_树的概念及通用树的实现][12 4]
    
    ### 6.森林的概念 ###
    
    ![数据结构（12）\_树的概念及通用树的实现][12 5]
    
    # #

[https_blog.csdn.net_snailmann_article_details_88607659_utm_medium_distribute.pc_relevant.none-task-blog-baidujs_title-5_spm_1001.2101.3001.4242]: https://blog.csdn.net/snailmann/article/details/88607659?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-5&spm=1001.2101.3001.4242
[https_blog.csdn.net_weixin_43767015_article_details_105710620]: https://blog.csdn.net/weixin_43767015/article/details/105710620
[https_blog.51cto.com_11134889_2140088]: https://blog.51cto.com/11134889/2140088
[12]: /images/20221022/e432927b459741a2aca083da1b040e3c.png
[12 1]: /images/20221022/edc3c18136ab4090a78c6ed7e248461f.png
[12 2]: /images/20221022/505ee12a4c764dc59a7b11d4ea8f3485.png
[12 3]: /images/20221022/ad9c080a05f94e029b9a85f31f661688.png
[12 4]: /images/20221022/6220a36999a841358a6f0b6860626e86.png
[12 5]: /images/20221022/06e87229e3b24afaa25fba43ad654085.png