什么是树 ​

示例 ​

分析 ​

启示 ​

客观的世界中许多事物存在层次关系：

👉人类社会家谱；

👉社会组织结构；

👉图书信息管理；

这些其实都是树结构。分层次组织在管理上具有更高的效率。

那么我们能不能把数据不存放在数组里面呢？我们就按照层次化结构来存数据，是不是也能达到我们想要的效果呢？按照层次化结构来存数据，这就是我们查找树的概念。

• 查找树和二分查找在效率上可以达到相同效果。
• 查找树还可以解决我们另一个问题，动态查找的问题。

树 ​

树的定义 ​

树（Tree）：n (n >= 0)个节点构成的有限集合。

当n = 0时，称为空树。

当n > 0时，对于一颗非空树，它具备一下性质：

1. 树中有一个特殊结点称为“根（Root）”，用 r表示。

2. 其余结点可分为m（m 0 ）个互不相交的有限集T₁,T₂...T_m，其中每个集合本身又是一颗树，称为原来树的“子树（SubTree）”

3. 子树不相交。

4. 每个结点仅且仅有一个父结点（除根结点外）。

5. 一颗N个结点的树有N-1条边（根结点没有）。

树的术语 ​

1. 结点的度（Degree）：结点的子树个数。
2. 树的度：树的所有结点中最大的度数。
3. 路径：从A到K的路径为一个结点序列A，B，F，K（从上往下）。
4. 路径长度：路径所包含边的个数，为路径长度。
5. 叶节点（Leaf）：度为0的结点。
6. 父结点：直接的上下关系结点。
7. 子结点：直接的上下关系结点。
8. 兄弟结点：拥有同一个父结点。
9. 祖先结点：沿着根结点到某一个结点的路径上的所有结点，都是这个结点的祖先结点。
10. 子孙结点：某一个结点的子树所有结点，都是这个结点子孙结点。
11. 结点的层次（Level）：规定根结点在第1层，其他结点是父结点+1。
12. 树的深度（Depth）：树中所有结点中的最大层次是这颗树的深度。

树的表示 ​

【数组】表示：如果使用数组实现，有些情况会非常麻烦，且对程序设计也不友好。

【链表】表示：如果用链表实现，当结点结构不一致，对后续的程序设计造成负担。

如果使用3n个指针域，我们实际上只有n-1个边。也就是说会有，3n - (n -1)个空指针域，会造成空间浪费。

【儿子-兄弟】表示：在链表的表示基础上做了优化，将每个结点设置成为统一的结构（包含两个指针的结构）。 二叉树结构，减少了空间的浪费，同时保证每个结点结构的统一，度为2。

二叉树（T） ​

二叉树的定义：

一个有穷的结点集合。这个集合可以为空，若不为空，则它由根结点和称为其左子树T_L和右子树T_R的两个不相交的二叉树组成。

二叉树基本形态：

特殊二叉树：

二叉树的几个重要性质：

🟥 一个二叉树第 i 层的最大结点数据为：2^i-1，i >= 1。

完美二叉树

🟥 深度为 K 的二叉树的最大结点总数为：2^k-1，k >= 1。

1 + 2¹ + 2² + ... + 2^k-1 = 2^k - 1

🟥 任何非空二叉树T

若n⁰表示叶节点，n¹表示度为1的结点数，n²表示度为2的结点数。

一定存在 n₀ = n₂ + 1

二叉树的抽象数据类型描述 ​

二叉树的遍历 ​

二叉树的遍历非常重要，很多算法设计都是建立在二叉树遍历的基础上的。

二叉树的存储 ​

二叉树【题】 ​

1. 给定一个二叉树，输出二叉树的中叶子结点。
2. 给定一个二叉树，求二叉树的深度。
3. 由两种遍历序列确定二叉树。
4. 判断同构树。

....

二叉搜索树 ​

二叉搜索树，也称二叉排序树或二叉查找树。可以为空，当不空有以下性质：

🔴 非空左子树的所有键值小于其根结点的键值。

🔴 非空右子树的所有键值大于其根结点的键值。

🔴 左、右子树都是二叉搜索树。

平衡二叉树 ​

平衡二叉树（Balanced Binary Tree）也叫AVL树，在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。

• 为空时，叫空树。
• 不为空时，任一结点左、右子树高度差的绝对值不超过1，|BF(T)| <= 1。

BF(T) = h_L - h_R: 平衡因子(Balance Factor，简称BF)，其中h_L、h_R分别为T的左、右子树的高度。

平衡二叉树的高度能达到 log₂n 吗？我们所希望的树能够平衡一点，树越平衡高度越低。

平衡二叉树调整 ​

平衡二叉树调整有四个基本操作

所有的平衡操作都依据被破坏结点（|BF(T)| <= 1 这个不成立时）