树

普通表示法：


儿子-兄弟 表示法：(模拟二叉树)


B: {

​ this.data = data;

​ this.leftChild = E,

​ this.sibling = C（this.rightChild = E）

}

D : {

​ this.data = data;

​ this.leftChild = H,

​ this.sibling = Null（this.rightChild = Null）

}

树结构 vs 【数组】

- 优点：

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

- 缺点：

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

树结构 vs 【链表】

- 优点：

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

- 缺点

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

树结构 vs 【哈希表】

- 优点：

• 哈希表的==插入/查询/删除效率==都是非常==高==的。

- 缺点：

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

树结构

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

但是树确实也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构，比如效率一般情况下没有哈希表高)。

并且也弥补了上面数据结构的缺点。

树结构是非线性的，可以表示一对多的关系。

树的术语

n(n>=0)个节点构成的有限集合，当n = 0时，称为空树；

1.节点的度(Degree)：节点的子树个数。

2.树的度：树的所有节点中最大的度数。

3.叶节点(Leaf)：度为0的节点。(也称为叶子节点)

4.父节点(Parent)：有子树的节点是其子树的根节点的父节点。

5.子节点(Chid)：若A节点是B节点的父节点，则称B节点是A节点的子节点；子节点也称孩子节点。

6.兄弟节点(Sibling)：具有同一父节点的各节点彼此是兄弟节点。

7.路径和路径长度：从节点η1到nk的路径为一个节点序列n1,n2….,nk,ni是ni+1的父节点。路径所包含边的个数为路径的长度。

8.节点的层次(Level)：规定根节点在1层，其它任一节点的层数是其父节点的层数加1。

9.树的深度(Depth)：树中所有节点中的最大层次是这棵树的深度。