最佳答案 - 由投票者3个月前选出

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树的定义

1.二叉树的递归定义
　二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

2．二叉树的五种基本形态
　二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
二叉树的五种基本形态如下图所示。
　
3．二叉树不是树的特例
（1）二叉树与无序树不同
二叉树中，每个结点最多只能有两棵子树，并且有左右之分。
　二叉树并非是树的特殊情形，它们是两种不同的数据结构。

（2）二叉树与度数为2的有序树不同
在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。　　　　　
　二叉树并非是树的特殊情形，它们是两种不同的数据结构。
二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
　 归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
　归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
　归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no+n1+n2 (式子1)
　 另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
　　树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
　　由式子1和式子2得到：
no=n2+1

满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree)
　一棵深度为k且有2k-1个结点的二又树称为满二叉树。
　满二叉树的特点：
　　（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
　　（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
顺序存储结构

　该方法是把二叉树的所有结点按照一定的线性次序存储到一片连续的存储单元中。结点在这个序列中的相互位置还能反映出结点之间的逻辑关系。

1．完全二叉树结点编号
（1） 编号办法
　在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列。
（2） 编号特点
　 完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号
http://student.zjzk.cn/course_ware/data_structure/web/shu/sh