本文共 1137 字，大约阅读时间需要 3 分钟。

算法数据结构 思维导图学习系列（1）- 数据结构 8种数据结构 数组（Array）链表（Linked List） 队列（Queue） 栈（Stack） 树（Tree）散列表（Hash） 堆（Heap） 图（Graph）

 

---

树的高度和深度

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

总之在我看来：

有两种说法：

1. 高度就是深度
2. 看层数：
   如果根结点第0，层数=深度=高度-1
   如果根结点第1，层数=深度=高度

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

　

补充：

根节点在第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。

　

---

参考书籍和视频课：

1. 《数据结构（C++版） 》 第二版 清华大学出版社 王红梅
2. 《数据结构（C++语言版）》 第三版 清华大学出版社 邓俊辉
3. 《数据结构(用面向对象方法与C++语言描述) 》 第二版 清华大学出版社 殷人昆
4. 《数据结构高分笔记》2019版 机械工业出版社 天勤考研
5. 北京大学 数据结构与算法
6. 华南理工大学 数据结构与算法

 

转载地址：http://fwuii.baihongyu.com/