树的高度和深度

转载：树的高度和深度以及结点的高度和深度

有个缺点，看到什么东西不管是不是重点只要说不通总是爱钻牛角尖。 对于 树的高度和深度（以及结点的高度和深度） 看了几本不同的书，都有各自的说法，多方查证吧，花了很多时间，最后归纳一下。(´｡• ᵕ •｡`) ♡

1. 树的高度和深度

2021-04-03-5KrokW

深度定义是从上往下的，高度定义是从下往上的。（其实不用在意这个，反正树的深度高度怎么数都一样的）。 深度和高度涉及到结点的层数，有的教材规定根结点在第0层，有的则规定根结点在第1层。原理都是一样的，因教材而异。 树从根结点开始往下数，叶子结点所在的最大层数称为树的深度。 有的教材对于树的高度定义是高度就是深度（层数是0123，深度=高度=3；层数是1234，深度=高度=4）；而有的教材树的高度则是看一共有几层。也就是说不论根节点在第几层，树的深度都是和最大层的叶子节点一样。而树的高度只要看有几层就行了（0123是四层，1234也是四层）。

总之在我看来，有两种说法：

1. 高度就是深度

2. 看层数：

   • 如果根结点第0，层数=深度=高度-1

   • 如果根结点第1，层数=深度=高度

举个栗子_(:3 」∠ )_：

2021-04-03-KbxbGc

图	左	右
层数	从第0层开始	从第1层开始
最大层数	4	5
深度	4	5
高度（高度=深度）	4	5
高度（数层数）	5	5

1.1 补充

根节点在第0层时候，按照北大数据结构视频的说法就是高度数结点数，深度数路径。从A到G，节点是5层，中间有4段路径，所以深度4，高度5。 其实也可以理解为数高度时候叶子结点从1开始数。因此空数高度0，只有一个根节点高度1。

但是在清华大学 邓俊辉数据结构书中如下：

2021-04-03-4FGGk1

这本书中可以看出数高度时候叶子结点是从0开始的，因此空数高度-1，只有一个根节点高度0。

2. 结点的高度和深度

2021-04-03-4YLKjk

结点的深度也是从根结点开始数，是第几层也决定于根结点在第0层还是第1层。

根结点的高度则取决于它的子树，该节点子树中最远的那个叶子结点作为1开始数。

例如对于BCD三个点：

B的子树是C和D，数B的高度时候，B的子树中离B最远的叶子节点是G，所以G高度为1，B高度4，D高度3。但是C是叶子节点，C没有真子树，C高度就是1。

2021-04-03-5mGEog

图	左	右
BCD高度（叶子节点>=0）	4 1 3	4 1 3
BCD高度（叶子节点>0）	3 0 2	3 0 2
BCD深度	1 2 2	2 3 3

3. 参考书籍和视频课

1. 《数据结构（C++版） 》 第二版 清华大学出版社 王红梅

2. 《数据结构（C++语言版）》 第三版 清华大学出版社 邓俊辉

3. 《数据结构(用面向对象方法与C++语言描述) 》 第二版 清华大学出版社 殷人昆

4. 《数据结构高分笔记》2019版 机械工业出版社 天勤考研

5. 北京大学 数据结构与算法

6. 华南理工大学 数据结构与算法