特殊二叉树

1.

斜树

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

2.

满二叉树

在一颗二叉树中，如果所有分支节点都存在左子树和右子树，而且所有叶子都在同一层上，称位满二叉树。

3.

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

完全二叉树的性质：

1.叶子节点只能出现在下两层

2.最下层的叶子一定出现在左部的连续位置。

3.倒数第二层的叶子节点出现在右部的连续位置。

4.完全二叉树度为1的点有且仅有一个，且仅有左孩子。

5.同样节点的二叉树，完全二叉树的深度最小。

6.具有n个节点的完全二叉树的高度为【logn].

7.若将一颗具有n个结点的完全二叉树按层次次序从1 开始编号，则对编号为i (1<=i<=n)的结点有： ① 若i≠1，则编号为i的结点的父结点的编号为 [i/2]  。

② 若2i<=n，则编号为i的结点的左孩子的编号为 2i， 否则 i 无左孩子。

③ 若 2i+1<= n ，则 i 结点的右孩子结点编号为 2i+1 ，否 则 i 无右孩子

二叉树的性质

1.二叉树的第i层最多有2^i个节点。

2.深度为k的二叉树最多有2^(k+1)-1个节点.

3.对于任意一棵二叉树，终端节点为n1,度为二的节点n2,则n2=n1+1。