文章目录
- 一. 前言
- 二. 大话高度与深度
- 三. OJ题中使用的版本
- 四. 考研中使用的版本
- 五. 总结
一. 前言
数据结构-----树的学习过程中，我们会遇见一些摸棱两可的概念，比如树的度，子树的高度，子树的的深度等。我们时不时的会产生这样的困惑：“我参考学习的书籍明明是这样定义的，但有时又发现和别人讲的不同，在做一些OJ题的时候又不一样，孰是孰非，让大家变得很纠结。当然我也纠结过，纠结到底该学习哪一个版本。所以写一篇博客整理一下，让自己不再纠结。
二. 大话高度与深度
结点的度： 结点所拥有的子树（后继元、后继结点）个数
树的度：一棵树中结点的度的最大值
对于这两者的定义全网还是比较统一的，我们不必深究，直接看例子:
根据定义，A结点的度为4（它有四棵子树）；B结点的度为0（它没有子树），叶子结点的度都是0；D结点的度为3（它有三棵子树）；F结点的度为1（它有一棵子树）······整棵树的度为最大结点的度，即A结点的度4，所以这棵树的度为4。
对于结点深度和高度的定义，根据教材书籍的不同，总的概括为两个版本，这两个版本的核心区别是:将树的根结点所在的位置定义为第0层，还是定义为第1层。
如下：
《数据结构C语言版第二版》中国工信出版集团 人民邮电出版社出版 严蔚敏 编著 。该书将根结点所在的位置定义为第1层。
《数据结构与算法分析C语言描述》—典藏版 计算机科学丛书 机械工业出版社出版 【美】马克·艾伦·维斯（Mark Allen Weiss）编著 。该书将根结点所在的位置定义为第0层。
就是以以上这两个版本为主，这些书的共同点是： 将深度的定义为从上至下，将高度的定义为从下之上，而树的高度和深度是相同的（记住此处是树而并不是结点）。
如下图：
此处只作解释什么是从上至下,从下至上（对于整棵树而言）：
D结点的深度：从根结点到D结点之间叫深度（从上至下）；
D结点的高度：从以D结点为根结点的最远叶子结点到D结点之间叫高度（从下至上）。
深度和高度的值与结点所在的层数有关，从而定义层数的方式不同，它们的值也是不同的，我们一起看看。
版本一：将根结点所在的位置定义为第一层
如下图：
结点的度： 结点所拥有的子树个数
结点的高度： 以该结点为根结点的树的最大层数（或者是以该结点为根结点的最远叶子结点到该结点唯一路径上的结点个数）
结点的深度： 结点所在的层数（或者是该结点到根结点的唯一路径上的结点个数）
树的度：整棵树中，结点的度的最大值
树的高度（深度）：就等于树的层数（或者是叶子结点的深度；根结点的高度）
树的层数： 以根结点所在的位置为第一层，依次向下递增
叶子结点的高度为1,根结点的深度为1
如上图：
D结点的度：3（有三棵子树）
D结点的高度：3（以D为根结点的树有三层，或者者以D为根结点的最远叶子结点到D结点的路径上有3个结点)
D结点的深度：2（D结点所在的层数，或者D到根结点A的路径上有两个结点）
树的度：4（结点的度的最大值，该结点是A）
树的高度：4（等于层数，或者根结点的高度）
树的深度：4（等于高度=层数，或者最远叶子结点的深度）
版本二：将根结点所在的位置定义为第0层
如下图：
结点的度： 结点所拥有的子树个数
结点的高度： 以该结点为根结点的树的最大层数（或者是以该结点为根结点的最远叶子结点到该结点唯一路径上的结点个数-1）
结点的深度： 结点所在的层数（或者是该结点到根结点的唯一路径上的结点个数-1）
树的度：整棵树中，结点的度的最大值
树的高度（深度）：就等于树的层数（或者是叶子结点的深度；根结点的高度）
树的层数： 以根结点所在的位置为第0层，依次向下递增
叶子结点的高度为0,根结点的深度为0
如上图：
D结点的度：3（有三棵子树）
D结点的高度：2（以D为根结点的树有2层，或者以D为根结点的最远叶子结点到D结点的路径上的结点个数-1（3-1=2）)
D结点的深度：1（D结点所在的层数，或者D到根结点A的路径上的结点个数-1（2-1=1））
树的度：4（结点的度的最大值，该结点是A）
树的高度：3（等于层数，或者根结点的高度）
树的深度：3（等于高度=层数，或者最远叶子的深度）
注意：
度和深度以及高度都是不同的概念，用的人认为结点的度就是结点的高度或者深度，这是一个错误（曾经参考别人资料学习的时候碰见过）
三. OJ题中使用的版本
来看看OJ题中使用的版本，上图，发挥图的强大。
根据提供的例子，属于版本一，将根结点所在的位置定义为第一层。
根据提供的例子，属于版本一。
根据提供的例子，属于版本一。
根据OJ题可以看出，在OJ题中将根结点所在的位置定义为第一层。属于版本一。
四. 考研中使用的版本
对于这一块，关键还是得看所报考的院校。我看了一些学校的真题，学校不同，参考书籍也不一样。而考研数据结构又不是统考，是招生单位自主命题。所以如果有考研意向的同学一定要了解你所报考院校的情况。
五. 总结
其实在很多时候我们碰见的都是版本一，即将根结点所在的位置定义为第1层。不管是刷OJ题也好，还是平时B站学习也好，包括计算二叉查找树的高度都是如此。在我学习的道路上，除了我手中的教材是将根结点所在的位置定义为第0层外（当时因为也不了解把我弄得够呛），其余碰见相关的都是将根结点所在的位置定义为第1层。所以我推荐重点还是看版本一。
❤️ ❤️ 我是“老胡”，感谢阅读 ❤️ ❤️
