树的高度和深度
最后更新于
有个缺点，看到什么东西不管是不是重点只要说不通总是爱钻牛角尖。 对于 树的高度和深度（以及结点的高度和深度） 看了几本不同的书，都有各自的说法，多方查证吧，花了很多时间，最后归纳一下。(´｡• ᵕ •｡`) ♡
深度定义是从上往下的，高度定义是从下往上的。（其实不用在意这个，反正树的深度高度怎么数都一样的）。 深度和高度涉及到结点的层数，有的教材规定根结点在第0层，有的则规定根结点在第1层。原理都是一样的，因教材而异。 树从根结点开始往下数，叶子结点所在的最大层数称为树的深度。 有的教材对于树的高度定义是高度就是深度（层数是0123，深度=高度=3；层数是1234，深度=高度=4）；而有的教材树的高度则是看一共有几层。也就是说不论根节点在第几层，树的深度都是和最大层的叶子节点一样。而树的高度只要看有几层就行了（0123是四层，1234也是四层）。
总之在我看来，有两种说法：
高度就是深度
看层数：
如果根结点第0，层数=深度=高度-1
如果根结点第1，层数=深度=高度
举个栗子_(:3 」∠ )_：
| 图 | 左 | 右 |
|---|---|---|
层数 | 从第0层开始 | 从第1层开始 |
最大层数 | 4 | 5 |
深度 | 4 | 5 |
高度（高度=深度） | 4 | 5 |
高度（数层数） | 5 | 5 |
根节点在第0层时候，按照北大数据结构视频的说法就是高度数结点数，深度数路径。从A到G，节点是5层，中间有4段路径，所以深度4，高度5。 其实也可以理解为数高度时候叶子结点从1开始数。因此空数高度0，只有一个根节点高度1。
但是在清华大学 邓俊辉数据结构书中如下：
这本书中可以看出数高度时候叶子结点是从0开始的，因此空数高度-1，只有一个根节点高度0。
结点的深度也是从根结点开始数，是第几层也决定于根结点在第0层还是第1层。
根结点的高度则取决于它的子树，该节点子树中最远的那个叶子结点作为1开始数。
例如对于BCD三个点：
B的子树是C和D，数B的高度时候，B的子树中离B最远的叶子节点是G，所以G高度为1，B高度4，D高度3。但是C是叶子节点，C没有真子树，C高度就是1。
| 图 | 左 | 右 |
|---|---|---|
BCD高度（叶子节点>=0） | 4 1 3 | 4 1 3 |
BCD高度（叶子节点>0） | 3 0 2 | 3 0 2 |
BCD深度 | 1 2 2 | 2 3 3 |
《数据结构（C++版） 》 第二版 清华大学出版社 王红梅
《数据结构（C++语言版）》 第三版 清华大学出版社 邓俊辉
《数据结构(用面向对象方法与C++语言描述) 》 第二版 清华大学出版社 殷人昆
《数据结构高分笔记》2019版 机械工业出版社 天勤考研
北京大学 数据结构与算法
华南理工大学 数据结构与算法
