树结构类型一些总结

树：

树是一种层次数据结构，第一层只有一个结点，称为树根结点，其后每一层都是上一层相应结点的后继结点，每个结点可以有任意多个后继结点，叶子结点没有后继结点，或者说具有0个后继结点。一颗树中的树根结点没有前驱结点，其余每个结点有并且只能有一个前驱结点。树中结点的前驱结点称为该结点的父亲或双亲，后继结点称为该结点的孩子。

二叉 树：

1. 1. 二叉树是度为2的有序树，每个结点至多有两个孩子，其中一个称为左孩子，另一个称为右孩子。若一个结点不有左孩子或右孩子，也可以说孩子结点（子树）为空。
   2. 一颗深度为h的二叉树最少含有h个结点，最多含有2^h-1个结点；一棵具有n个结点的二叉树，其最小深度为?log₂(n+1)?，也等于?log₂n?+1。
   3. 二叉树具有顺序和链式两种存储结构，对于完全二叉树通常采用顺序存储结构，对于普通二叉树通常采用链式存储结构。二叉树链接存储的结点类型用BTreeNode表示，它包含有值域data，指向左孩子结点的指针域left和指向右孩子结点的指针域right。
   4. 遍历是二叉树的主要运算，包括先序、中序、后序和层序四种不同的遍历次序，前三种通过递归算法或使用栈的非递归算法实现，后一种通过使用队列的非递归算法实现。每一种遍历算法的时间算均为O(n)。
   5. 对二叉树的其它运算，通常也是在对二叉树递归扁历算法的基础上经适当修改后而得到的，大家了可以跟据实际需求编写对二叉树其它算法。

堆（优先队列）：

这里的堆就是用完全二叉树建立的优先队列，一般都用数组实现堆，堆又可以分最大堆和最小堆。主要用于某种带有优先排队问题。

哈夫曼树：

1. 哈夫曼树是由n个带权叶子结点构成的所有二叉树中，带权路径长度最短的二叉树。为了得到结构唯一的哈夫曼树，通常规定每个分支结点的左孩子的权要小于等于右孩子结点的权。
2. 一棵哈夫曼树是不断地由两棵子树构成一棵树而生成的，所以只存在双支结点，不存在单支结点，若利用n个带权叶子结点生成一棵哈夫曼树，则树中的结点总数为2n-1，因为双支结点的个数等于叶子结点的个数减1，单支结点的个数为0。