认识
一、认识
树是一种非线性结构
二、特点
- 仅有唯一一个根节点，没有节点则为空树
- 除根节点外，每个节点都有并仅有唯一一个父节点
- 节点间不能形成闭环
三、术语
-
节点的度(
degree)：节点的子树个数 -
树的度：树的所有节点度中的最大值
-
叶子节点(
leaf)：度为0的节点 -
非叶子节点:度不为0的节点
-
层数：根节点在第一层（或者第0层），依次类推
-
节点的深度(
depth)：从根节点到当前节点的唯一路径上的节点总数 -
节点的高度(
height)：从当前节点到最远叶子节点的路径上的节点总数 -
树的深度:所有节点深度中的最大值
-
树的高度:所有节点高度中的最大值
-
路径和路径长度：从节点 n1 到 nk 的路径为一个节点序列 n1,n2,……,nk，ni 是 ni + 1 的父节点。路径所包含边的个数为路径的长度
-
有序树：
-
无序树：
四、问题
4.1 有很多种数据结构可以保存数据，为什么要用树结构来保存数据呢?
-
数组存储数据：
-
优点：根据下标值访问效率很高
-
缺点：对数组进行插入和删除数据时，需要有大量的位移操作，效率很低
-
-
链表存储数据:
-
优点：链表的插入和删除操作效率都很高
-
缺点：查找效率很低，需要从头开始依次访问链表中的每个数据项，直到找到
-
-
哈希表存储数据:
-
哈希表的插入/查询/删除效率很高
-
缺点：哈希表空间利用率不高，底层使用的是数组，并且某些单元是没有被利用的。哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素，也不能快速的查找出哈希表中的最大值和最少值
-
-
树结构：
优点：插入、删除效率很高。空间利用率高，元素有序