14 树结构

树结构长这个样子：

一棵真实树的特点：

• 有一个根，根连接着树干。
  
• 树干到上面之后会进行分叉成树枝，树枝还会分叉成更小的树枝。
  
• 在树枝的最后是叶子。
  

树的抽象：

• 专家们对树的结构进行了抽象，发现树可以模拟生活中的很多场景。
  

公司组织的架构：

红楼梦家谱：

树结构的抽象：

树的优点：

• 我们之前学习了多种数据结构来保存数据，为什么要使用树结构来保存数据呢？
  
• 树结构和数组/链表/哈希表的对比有什么优点？
  

数组：
优点：

• 数组的主要优点是根据下标值访问效率会很高。
  
• 但是如果我们希望根据元素来查找对应的位置那？
  
• 比较好的方式是先对数组进行排序，在进行二分查找。
  

缺点：

• 需要先对数组进行排序，生成有序数组，才能提高查找效率。
  
• 另外数组在插入和删除数据时，需要有大量的位移操作（插入到首位或者中间位置的时候），效率很低。
  

链表：
优点：

• 链表的插入和删除操作效率都很高。
  

缺点：

• 查找效率很低，需要从头开始依次访问链表中的每个数据项，知道找到。
  
• 而且即使插入和删除操作效率很高，但是如果要插入和删除中间位置的数据，还是需要重头先找到对应的数据。
  

哈希表:
优点：

• 学过哈希表之后会发现，哈希表的插入/查询/删除效率都是非常高的。
  
• 但是哈希表也有很多缺点。
  

缺点：

• 空间利用率不高，底层使用的是数组，平且某些单元是没有被利用的。
  
• 哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素。
  
• 不能快速的找出哈希表中的最大值或者最小值这些特殊的值。
  

树结构：

• 不能说树结构一定比其它结构都要好，为啥那，因为每种数据结构都是自己特定的应用场景。
  
• 但是树确实也综合了上面的数据结构的优点（当然优点不足与盖过其它数据结构，比如效率一般情况下没有哈希表高）。
  
• 并且也弥补了上面数据结构的缺点。
  

而且为了模拟某些场景，我们使用树结构会更加方便

• 因为数结构的非线性，可以表示一对多的关系。
  
• 比如文件的目录结构。
  

树结构的术语：
在描述树的各个部分的时候有很多术语：
大部分术语都与真实世界的树相关，或者和家庭关系相关（如父节点和子节点），所以它们比较容易理解。

• 树（Tree）：n（n>=0）个节点构成的有限集合。
  
  • 当n=0时，称为空树；
    
• 对于任意一颗非空树（n>0），它具备以下性质：
  
  • 树中有一个称为“根（Root）”的特殊节点，用r表示；
    
  • 其余节点可分为m（m>0）个互不相交的有限集T1，T2, …，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
    

树的术语：

1. 节点的度（Degree）：节点的子树个数。
   
2. 树的度：树的所有节点中最大的度数（上面的示图度数就是2，二叉树）。
   
3. 叶节点（Leaf）：度为0的节点（也成为叶子节点）。
   
4. 父节点（Parent）：有子树的节点是其子树的根节点的父节点。
   
5. 子节点（Child）：若A节点是B节点的父节点，则称之为B节点是A节点的子节点；子节点也称为孩子节点。
   
6. 兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点。
   
7. 路径和路径长度：从节点n1到nk的路径为一个节点序列n1 , n2 , …. nk , ni是ni+1的父节点。路径所包含边的个数为路径的长度（图中A到H就是三条边）。
   
8. 节点的层次（Level）：规定根节点在1层，其它任意节点的层数是其父节点的层数+1（B节点的层次就是2）。
   
9. 树的深度（Depth）：树中所有节点中的最大层次是这棵的深度。
   

最普通的表示方式

直接就是一个节点包含了所有子节点的指向。

儿子-兄弟表示法

由节点自身，存放一个指向自己同级兄弟的指向，没有兄弟节点则指向（N）null。

儿子-兄弟表示法旋转

有规律的：**

• 其实所有的树本质上都可以使用二叉树模拟出来。
  
• 所以在学习树的过程中，二叉树非常重要