当年飞哥准备软考，弄了一个视频，一开始就给我讲“树”，让我那个懵逼哟……不明觉厉！

树（tree）

不像？倒过来看！

关键的关键，是和树一样有分叉。

基本概念

节点（node）

• 根（root）：没有其他节点指向
• 叶子（leaf）：不指向任何其他节点
• 枝（branch）：其他节点

叉：二叉/三叉/n叉……。为了教学方便，一般都使用二叉树：一个节点最大只有两个“分叉”

关系：父/子/兄弟/祖先/后代

• 祖先：包含父节点的节点，以及一直往上的所有父节点
  
• 父：直接包含自己的节点
  
• 自己：
  
• 兄弟：父节点下除自己以外的其他节点
  
• 子：自己的直接包含的节点
  
• 后代：子节点包含的节点，以及一直往下的所有子节点
  

深度：从根到叶子的层级数

子树：一个树有可以被分为多个子树

和链表的关系

树可以认为是一种链表，他们都是通过“指针”进行组织

• 链表：线性，没有分叉
• 树：非线性，节点的指针会形成“岔路”

现实映射

其实现实生活中，“树”无处不在，比如：企业/部队/政府/家族……，只要有分类、目录、层级关系存在的地方，就有“树”。

为什么需要树？@想一想@：为什么需要文件夹？

磁盘上有成千上万个文件，如何才能快速的找到其中某一个文件？（地址同理）

树的最大作用是便于查找。

添加约束

排序二叉树

特点/定义：

• 左子树上所有结点（的值）均小于它的根结点（的值）（若左子树不空）；
• 右子树上所有结点（的值）均大于它的根结点（的值）（若右子树不空）；
• 左、右子树也分别为二叉排序树；

@想一想@：为什么需要“排序”二叉树？便于查找。（演示）

平衡排序二叉树（AVL树）

在排序二叉树的基础上增加“平衡”：

任何一个子树，左右两边叶子节点的深度差距不大于1

为什么需要平衡？将算法时间复杂度始终控制在O(log(n))

对比二分查找

有些同学会瞬间联想到：这不就是二分查找么？为什么不直接顺序排列，然后用二分？

问题是：用什么装数据？尤其是当数据插入/更改/删除的时候：

• 数组：大小固定，位置固定，重新排序是不是很麻烦？
• 链表：如何快速定位到要插入的位置？

#体会#：数据结构是算法的基础，一定是先有数据结构，然后才有算法……

堆：完全二叉树

树的构建（选）

这里的树，专指排序平衡二叉树。

如何实现？常规方法是：在排序二叉树的基础上进行平衡调整。

排序

第一个节点为根节点。

第二个节点和第一个节点比较：

• 大于第一个节点，放右边
• 小于第一个节点，放左边

第三个节点，以此类推

PPT演示……

平衡

每一次排序完成，检查是否平衡。如果没有，利用左旋转/右旋转 及其 组合进行调整。

1. 一次旋转实现
   
   
2. 两次旋转实现，即先做成1的样子（会有切断/连接的过程），再按1进行处理

更复杂树仍然使用这个套路，先调整不平衡子树，再依次往上调整直到根节点，总之：

• 对树结构只有最小的影响，以提高性能
• 使用固定套路，方便分支/循环的代码编写

PPT演示：……

延伸：一个可以动画显示树操作的网站

图和其他

如果把树搞得再“乱”一点，就可以形成

图

其实也有点像（互联）“网”：

• 树是有层级结构的，图没有；
• 树总是从根节点出发的，图不一定，大多数时候都没有根节点这个概念
• 到达树的某一节点，路径是固定的；而图是不固定/单一的 —— 图的路径（最短最快）是研究的重点
  

图的应用以前还很神秘，现在烂大街了。@想一想@：百度/高德地图、滴滴打车，是不是都要用到图？

其他算法

我们所学的算法其实都是皮毛，^_^

有兴趣的同学可以继续学习：

• 最短路径/电梯调度/背包……问题
  
• 分支/动态规划/贪心……算法

但因为在实际的（企业级应用）开发中用不到，我们就不多讲了……

好吧，我承认，我也不会，ʅ(‾◡◝)ʃ

源栈学历

在当前系列 数据结构和算法 中继续学习：

多快好省！前端后端，线上线下，名师精讲

• 先学习，后付费；
• 不满意，不要钱。
• 编程培训班，我就选源栈

更多了解 加：