前端编程应该了解的数据结构——树

树的概念

 我们在计算机程序中，经常用到一种数据结构——树。这里的树并不是我们现实生活中的树，但是，我们可以通过我们对生活中树的认知来理解数据结构中的树。

生活中树的特点：

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

2、树干到上面之后会进行分叉成树枝, 树枝还会分叉成更小的树枝；

3、在树枝的最后是叶子。

将其特点总结起来进行抽象，就得到了我们在数据结构的树。

简单来说就是一个根节点，发散出许多的分支节点，停留在叶子节点。

为什么要使用树结构？

那么我们不得不说说它的优点。

对比于数组和链表。

数组

优点：数组的主要优点是根据下标值访问效率会很高；

缺点：根据元素来查找对应的位置时，需要先对数组进行排序, 生成有序数组, 才能提高查找效率；

另外数组在插入和删除数据时, 需要有大量的位移操作(插入到首位或者中间位置的时候), 效率很低。

链表

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

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

树

综合了上述两种数据结构的优点(当然优点不足于盖过其他数据结构) ，而且也弥补了上面数据结构的缺点；

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

树的术语

树的定义：树(tree)， n（n≥0）个结点构成的有限集合。

当n=0时，称为空树；

当n>0时，为非空树，对任何一颗非空树，都有以下特点：

1、只有一个根节点 

 2、其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）

3、一颗n个节点的树有n-1条边

举一个树的结构图：

 

术语

结点的度：结点的子树个数；

树的度：树的所有结点（例如上图的A、B、C、...、Q）中最大的节点度，即A的度最大为6，所以树的度为6。

叶结点（Leaf）：度为0的结点. (也称为叶子结点)

父结点（Parent）：有子树的结点

子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点

兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。

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

结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1

树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度，上图中P、Q的层次最大为4，即树的深度为4。

二叉树

树也是一种非常常用的数据结构, 特别是二叉树。

二叉树的定义：树中每个节点最多不能超过两个子节点，这样的树即称为二叉树。

二叉树有五种形态：1、二叉树为空，即0个节点   2、只有根节点   3、只有根节点和左子树TL  4、只有根节点和右子树TR  5、同时包含根节点、TL、TR

二叉树的特性

1、一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1

2、深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;

3、对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1

特殊的二叉树

完美二叉树(Perfect Binary Tree) , 也称为满二叉树(Full Binary Tree），特点： 除了最下一层的叶结点外, 每层节点都有2个子结点。

如：

 

完全二叉树(Complete Binary Tree)，特点：

除二叉树最后一层外, 其他各层的节点数都达到最大个数；

且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点；

完美二叉树是特殊的完全二叉树.

如：

 
二叉树的存储

通常用链表存储，每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用。

Node结构图：初始左右节点的引用为空。