1、概念

• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 叶节点或终端节点：度为0的节点称为叶节点；
• 非终端节点或分支节点：度不为0的节点；
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 树的度：一棵树中，最大的节点的度称为树的度；
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次；
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；
• 树：非线性数据结构，是以分支关系定义的层次结构。每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树
• 二叉树：结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

2、二叉树

2.1 五种基本形态

每个节点有五种形态

• 空二叉树
• 无叶子节点；
• 只有左子树；
• 只有右子树；
• 含有左右子树

2.2 基本性质

• 非空二叉树中，第i层的结点总数不超过2^i-1, i>=1；

• 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

• 对于任意一棵二叉树，如果其叶结点数为N₀，而度数为2的结点总数为N₂，则N₀=N₂+1；

• 具有n个结点的完全二叉树的深度为[log₂n + 1]（注：[ ]表示向下取整）

• 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；
如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；
如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。

2.3 特殊二叉树

• 斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。
• 满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
• 完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同
• 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
• 红黑树：一种自平衡二叉树；红黑树确保没有一条路径会比其他路径长出两倍。这个树大致上是平衡的，因此，插入、删除和查找操作在最坏情况下都是高效的。需满足下面5个方面

1. 每个结点是红色或黑色
2. 根结点是黑色
3. 每个叶子结点是黑色
4. 每个红色结点的两个子结点是黑色
5. 从任意结点到其每个叶子结点的路径包含相同数目的黑色结点

• 二叉搜索树：是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
• AVL树：也叫平衡二叉搜索树，是一个平衡二叉树，也是二叉搜索树
• 哈夫曼树： 给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。

2.4 存储结构

• 数组存储：0为根节点，节点为i的左孩子索引为 2 * i + 1, 右孩子索引2 *( i + 1)， 父节点索引为(i - 1) / 2;满二叉树可以存满整个数据，其它数据不连续
• 链式存储： 二叉链表，即数据域+左孩子指针+有孩子指针

2.4 二叉树遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。

• 先序遍历
  首先访问根，再先序遍历左子树，最后先序遍历右子树
• 中序遍历
  首先中序遍历左子树，再访问根，最后中序遍历右子树
• 后序遍历
  首先后序遍历左子树，再后序遍历右子树，最后访问根
• 层次遍历
  即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）