一、基本概念
1、节点：根节点，叶子节点
节点的度：节点拥有子节点的数量（度为0的节点为叶子节点，不为0为分支节点）
深度：根节点自顶向下到该节点累加
高度：叶子节点自底向上到该节点累加
2、树的度：树中所有节点的度的最大值
3、树的高度：树节点最大层数
4、树的性质：
a:树的节点数等于所有节点度数+1
b:度为m的树第i层最多有m^(i-1)个节点 i>=1
c:高度为h的m叉树最多有（m^h-1）/(m-1)个节点
d:具有n个节点的m叉树的最小高度为logm(n(m-1)+1)
二、存储结构
1、顺序存储：所有节点存储在一个列表中，节点记录自己和自己的子节点在列表中的位置。
2、链式存储：所有节点的单链表头存储在一个列表中，每个节点用一个单链表存储子节点。
三、二叉树
1、二叉树每个节点最多有两个子节点
2、特殊二叉树：
斜树：每个节点只有左节点或右节点。
满二叉树：除了叶子节点每个节点上都有左右节点，节点数n=2^m-1(m为深度)。
完全二叉树：若设二叉树的深度为k,除第 k 层外,其它各层 (1～k-1) 的结点数都达到最大个数,第k 层所有的结点都连续集中在最左边。
3、二叉树性质：
a:非空二叉树的叶子节点数等于度为2的节点数加1.
b:非空二叉树的第k层最多有2^k-1个节点（k>=1）
c:高度为h的二叉树节点数最多有2^h-1个（h>=1）
d:具有n个节点的完全二叉树的高度为log2(N+1)或log2N+1
4、二叉树的遍历
a:中序遍历：左根右
b:前序遍历：根左右
c:后序遍历：左右根
5、哈夫曼树
构造哈弗曼树：构造新节点，从所有节点中选取最小权值的两个节点分别作为左右子树，新节点权值为两子节点权值的和，移除所有节点中选取的两个节点。