计算机二级公共基础知识章节知识点：1.6树与二叉树

二叉树及其基本性质

　　1）二叉树的定义
　　二叉树的特点：
　　非空二叉树只有一个根结点
　　每一个结点最多只有两个子结点，且结点分左右。则一个结点最多可以有两棵子树，分别称为左子树和右子树
　　在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。
　　在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，则该结点为叶子结点。
　　2）二叉树的性质
　　性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。
　　性质2：深度为m的二叉树最多有2m-1个结点。
　　性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。
　　性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。
　　3）满二叉树与完全二叉树
　　（1）满二叉树
　　满二叉树的特点：
　　除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树上的第k层上有2k-1个结点。
　　（2）完全二叉树
　　特点：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干个结点。
　　即如果从根结点开始，对二叉树的结点自上而下、自左而右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，则是完全二叉树。
　　对于完全二叉树，叶子结点只能在层次最大的两层中出现；对于任何一个结点，若其右分支下的子树结点的最大层次为p，则其分支下的子孙结点的最大层次为p或p+1
　　树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。