二叉树

1、基本概念

二叉树（Binary Tree）是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的特点：

二叉树不存在度大于2的结点。

二叉树的子树有左右之分，次序不能颠倒。

如下图中，树1和树2是同一棵树，但它们是不同的二叉树。

二叉树

1）、斜树

所有的结点都只有左子树的二叉树叫左斜树。所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。

斜树每一层只有一个结点，结点的个数与二叉树的深度相同。其实斜树就是线性表结构。

2）、满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树具有如下特点：

叶子只能出现在最下一层

非叶子结点的度一定是2

同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3）、完全二叉树

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

完全二叉树的特点：

叶子结点只能出现在最下两层

最下层叶子在左部并且连续

同样结点数的二叉树，完全二叉树的深度最小

4）、平衡二叉树

平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

2、二叉树的性质

在二叉树的第i层上至多有2^i-1^个结点（i>=1）。

深度为k的二叉树至多有2^k^-1个结点（k>=1）。

对任何一棵二叉树T，如果其终端结点个数为n~0~，度为2的结点数为n~2~，则n~0~ = n~2~ + 1。

具有n个结点的完全二叉树的深度为「log~2~n」+ 1（「x」表示不大于x的最大整数）。

如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到第「log~2~n」+ 1层，每层从左到右），对任一结点i（1≤i≤n）有：

若i=1，则结点i是二叉树的根，无双亲；如i>1，则其双亲是结点「i/2」。

如2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。

若2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

3、二叉树的存储结构和遍历

二叉树是一种特殊的树，它的存储结构相对于前面谈到的一般树的存储结构要简单一些。

①顺序存储结构

②链式存储结构