树--二叉树

二叉树：

性质1：在二叉树的第i层至多有个节点（i>=1)

eg第一层：=1；

第二层：=2；

第三层：=4；

（第i层上至少有一个节点）

性质2：深度为k的二叉树至多有个节点（k>=1)。

其实就相当于等比数列求和公式。

如上图，当高度等于1时，节点也为1，当高度为2时，节点为3，当高度为3时，节点为7。

（深度为k对的二叉树至少有k个节点）

性质3：对于任意一颗二叉树T，如果叶子数为，度为2的节点为，则。

依旧用上面那个图解释，叶子节点个数为4，度为2的个数为3，4=3+1，性质成立。

从上往下看：

总边数B=*2+*1（度为2有1两个孩子，所以有两条边，度为1只有一个孩子，只有一条边）

从下往上看：

总边数B=总结点数-1。（因为根节点没有父母，所以没有边）

总结点计算：

n=

n=

这两个式子可以推出性质三：

满二叉树：

一颗深度为k且有个节点的二叉树称为满二叉树。

特点：

1.每一层上面的结点树都是最大结点数的。

2.叶子节点在最底层。

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

完全二叉树：

是一种特殊的二叉树，它的定义是基于满二叉树的概念。在完全二叉树中，除了最后一层，其他各层的节点数都达到了最大个数，而最后一层的节点则都连续集中在最左边。这种结构的二叉树，其深度为h时，除了第h层外，其余各层（1~h-1）的节点数都是满的，第h层的节点从左到右连续排列，但不一定是满的。

（满二叉树是完全二叉树，完全二叉树不一定是满二叉树）

特点：

1.叶子只可能分布在层次最大的两层上。

2.对于任意结点，如果右子树最大层次为i，则左子树最大层次为i或i+1；

性质4：具有n个结点的完全二叉树的深度h等于⌊log_2n⌋ + 1；

性质5：如果对一棵有n个结点的完全二叉树按层序编号(从第1层到第[log2n+1层，每层从左到右)，则对任结点i(1≤n)，有:

(1)如果i=1，则结点i是二叉树的根，无双亲;如果i>1，则其双亲是结点⌊i/2⌋。

(2)如果2i>n，则结点i为叶子结点，无左孩子;否则，其左孩子是结点2i。

(3)如果2i+1>n，则结点i无右孩子;否则，其右孩子是结点2i+1。

（双亲结点和孩子编号之间的关系可以从性质5体现）