树的基本定义和分类

树的定义

无论是链表，栈还是队列，它们都是线性结构的，每个节点的左边最多一个节点，右边也最多一个节点，对于大量的输入数据，线性表的访问时间太慢，不宜使用。这里我要说一种非线性的数据结构，其大部分操作的运行时间平均为O(logn)。

我们涉及到的这种数据结构叫做树。在计算机科学中，树是非常有用的抽象概念。我们形象的去描述一棵树，一个家族的老祖可能有两个儿子，这两个儿子一个有一个儿子，一个有三个儿子，像这样发展下去的一个族谱，就是一个树。

• 节点的度：一个节点含有的子树的个数称为该节点的度。
• 树的度：一棵树中，最大的节点的度称为树的度。
• 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0。
• 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林。

二叉树的遍历

二叉树的遍历分为深度优先遍历和广度优先遍历。

深度优先遍历

深度优先遍历即将树的所有结点都访问且仅访问一次。按照根结点访问次序的不同，可以分为前序遍历，中序遍历，后序遍历。

• 前序遍历：根结点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根结点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根结点

举例：

image

前序遍历：a b d e f g c

中序遍历：d e b g f a c

后序遍历：e d g f b c a

层次遍历：a b c d f e g

广度优先遍历

广度优先遍历也叫层序遍历

树的分类

1. 无序树
   树中任意节点的子节点之间没有顺序关系。它就是一个无回路的连通图，没有确定根，在自由树中选定一顶点做根，则成为一棵通常的树。

2. 有序树
   树中任意节点的子节点之间有顺序关系。常见的有序树有：二叉树、完全二叉树、满二叉树、平衡二叉树（AVL树）、二叉查找树、霍夫曼树、B树、字典树。

表达式树

举个栗子，表达式：(a+b×(c-d))-e/f。将数字放在叶子节点，将操作符放在分支节点，就构成了一个二叉树，由于存储的是一个表达式，称之为“表达式二叉树”。

image

完全二叉树&&满二叉树

• 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列。
• 满二叉树：每一个层的结点数都达到最大值。
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

image

平衡二叉树（Balanced Binary Tree）

• 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
• 最小二叉平衡树的节点总数的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

二叉堆

二叉堆本质上是一个完全二叉树，又分为两个类型：

1. 最大堆（最大堆的任何一个父节点的值都大于或等于他的左孩子和右孩子）
2. 最小堆（最大堆的任何一个父节点的值都小于或等于他的左孩子和右孩子）

二叉堆是实现堆排序和优先队列的基础

二叉查找树

二叉查找树又叫二叉排序树或二叉搜索树。是一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的节点。

二叉查找树的性质：对二叉查找树进行中序遍历，即可得到有序的数列。

霍夫曼树

带权路径最短的二叉树。是一个一般化的二叉查找树，可以拥有多于2个子节点。

这里多提几个概念：

路径和路径长度:

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第L层结点的路径长哈夫曼树度为 L-1。

结点的权及带权路径长度:

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度:

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。即设二叉树有 n 个叶子结点，每个叶子结点带有权值 wk，从根结点到每个叶子的长度为 lk,则每个叶子结点的带权路径长度之和：WPL = ∑wi*li (i = 0,1,2...n)

哈夫曼树(也称为最优二叉树)就是使 WPL 达到最小的二叉树, 哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

B树

树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。

字典树

Tire树称为字典树，又称单词查找树，Trie树用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。　
Tire树的三个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。