二叉树的简介以及ADT实现

1.树是n个结点的优先集合T，满足一下的性质:

1）有一个被称之为root的结点

2）有其余的结点可以分为m个互不相交的集合T1，T2，T3，，，这些集合本身也是一棵树，每颗子树也有自己的根结点。

2.一些名词介绍

度：树中每个结点具有的子树的数目称为该结点的度

度为0的结点称为叶子或者终端节点。不为0的称之为非终端结点或者分支结点。

结点的子树的根称为该结点的孩子，在（完全）二叉树中，左边的称为左孩子，右边的称为右孩子。相应的，该结点称为孩子的双亲。同一个双亲的孩子互相称为兄弟。

深度：树中结点的最大层次称为书的深度或者高度。

有序树：将树中结点的各子树看成是从左到右的有次序的。

森林：是m棵互不相交的树的集合

3.二叉树的一些性质

性质1：一棵非空二叉树的第i层上最多有2^i-1个结点。

证明：利用数学归纳法进行证明。

第一步：当i为1时，成立有1个结点 满足此式

第二步：假设当i=k时，假设此式成立则在第k层上有2^k-1个结点

第三步：当i=k+1时，k+1层上结点最多为k层的2倍 则2*2^k-1 = 2^k

此时满足关系式。

性质2：一棵高度为i的二叉树，最多由2^k-1个结点

证明：当结点最多的时候，此时一定为满二叉树，此时结点的计算为：num=2⁰+2¹+2²+2³+……+2^i-1此时根据等比数列的计算公式可得num=2^k-1.

性质3：对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有n0 = n2+1成立（最大度数为2）

证明：假设度数为1的结点的数目为n1, 则此时二叉树中所有num = n1 + n1+ n2;

设置分支总数为num1，  num = num1+1,(分支简单说就是连的线的条数)，而num1=n1+2*n2，所以 n1+n2+n3 = n1+2*n2+1-------》n0=n2+1成立

性质4