树结构

树结构的特点

树通常有一个根，连接着根的是树干

树干到上面之后会进行分叉成树枝，在树枝的最后是叶子

树结构的抽象：

树的优点

树结构和数组、链表、哈希表对比有什么优点呢？

数组：

优点：

• 根据下标值访问效率高
• 如果希望根据元素来查找对应位置，比较好的方法是先对数组进行排序，在进行二分查找

缺点：

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

链表：

优点：

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

缺点：

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

哈希表：

优点：

• 插入、查询、删除效率都非常高

缺点：

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

数结构：

不能说树结构比其他结构都要好，因为每种数据结构都有自己的特定的应用场景

数结构综合了上面的数据结构的优点（但是优点不足以盖过其他数据结构，比如效率一般情况下没有哈希表高），也弥补了上面数据结构的缺点。

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

数结构术语

树（Tree）: n (n ≥ 0) 个节点构成的有限集合

当 n = 0 时，称为空树

对于任一棵非空树（n > 0）,他具备以下性质：

• 树中有一个称为**根（root）**的特殊节点，用 r 表示
• 其余节点可分为m (m > 0) 个互不相交的有限集T1、T2...., Tm ，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）
• 节点的度（Degree）: 节点的子树个数
• 树的度: 树的所有节点中最大的度数
• 叶节点（Leaf）: 度数为 0 的节点
• 父节点（Parent）: 有子树的节点是其子树的根节点的父节点
• 子节点（Child）: 若A节点是B节点的父节点，则称B节点是A节点的子节点
• 兄弟节点（Sibling）: 具有同一父节点的各节点彼此是兄弟节点
• 路径和路径长度：从节点 n1 到 nk 的路径为一个节点序列n1, n2, ...., nk, ni 是 ni + 1的父节点，路径所包含边的个数为路径长度。
• 节点的层次（Level）: 规定根节点在1层，其他任一节点的层数是其父节点的层数加1
• 树的深度（Depth）: 树中所有节点中最大层次是这棵树的深度

树的表示方式

最普通的表达方式：

儿子-兄弟表示法：

将儿子-兄弟表示法旋转

其实所有的树本质上都可以使用二叉树模拟出来