二叉树的定义

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

二叉树的性质

二叉树有以下几个性质：

1. 二叉树第i层上的结点数目最多为 2^(i-1) (i≥1)。

2. 深度为k的二叉树至多有2^k-1个结点(k≥1)。

3. 包含n个结点的二叉树的高度至少为log2 (n+1)。

4. 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)

证明：下面用”数学归纳法”进行证明。

当i=1时，第i层的节点数目为2{i-1}=2{0}=1。因为第1层上只有一个根结点，所以命题成立。

假设当i>1，第i层的节点数目为2{i-1}。这个是根据(01)推断出来的！ 下面根据这个假设，推断出”第(i+1)层的节点数目为2{i}”即可。 由于二叉树的每个结点至多有两个孩子，故”第(i+1)层上的结点数目” 最多是 “第i层的结点数目的2倍”。即，第(i+1)层上的结点数目最大值=2×2{i-1}=2{i}。 故假设成立，原命题得证！

性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)

证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用”性质1”可知，深度为k的二叉树的结点数至多为：20+21+…+2k-1=2k-1故原命题得证！

性质3：包含n个结点的二叉树的高度至少为log2 (n+1)

证明：根据”性质2”可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

证明：

因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=”0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此，得到等式一。

(等式一) n=n0+n1+n2

另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。

(等式二) n=n1+2n2+1

由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！

满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

完全二叉树

一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

平衡二叉树

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

二叉搜索树

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树.

从1到n所有节点构成的二叉查找树可以看作二分查找，每个节点都是二分查找的mid值。

红黑树

平衡二叉搜索树

哈弗曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。