二叉树的概念以及性质
2、二叉树及其基本性质
（1）什么是二叉树
二叉树是一种很有用的非线性结构,它具有以下两个特点：1）非空二叉树只有一个根结点；2）每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树.
*：根据二叉树的概念可知,二叉树的度可以为0（叶结点）、1（只有一棵子树）或2（有2棵子树）.
（2）二叉树的基本性质（学吧学吧独家稿件）
性质1 在二叉树的第k层上,最多有 个结点.
性质2 深度为m的二叉树最多有个 个结点.
性质3 在任意一棵二叉树中,度数为0的结点（即叶子结点）总比度为2的结点多一个.性质4 具有n个结点的二叉树,其深度至少为 ,其中 表示取 的整数部分.
3、满二叉树与完全二叉树
满二叉树：除最后一层外,每一层上的所有结点都有两个子结点.
完全二叉树：除最后一层外,每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点.
*：根据完全二叉树的定义可得出：度为1的结点的个数为0或1.
下图a表示的是满二叉树,下图b表示的是完全二叉树：
完全二叉树还具有如下两个特性：
性质5 具有n个结点的完全二叉树深度为 .
性质6 设完全二叉树共有n个结点,如果从根结点开始,按层序（每一层从左到右）用自然数1,2,…,n给结点进行编号,则对于编号为k（k=1,2,…,n）的结点有以下结论：
若k=1,则该结点为根结点,它没有父结点；若k>1,则该结点的父结点的编号为INT(k/2).