k层上，最多有2k1k≥1个结点；
（2）深度为m的二叉树最多有2m1个结点；
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）具有
个结点的二叉树，其深度至少为log2
1其中log2
表示取log2
的整数部分；
（5）具有
个结点的完全二叉树的深度为log2
1；
（6）设完全二叉树共有
个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…
给结点进行编号（k12…
），有以下结论：
f①若k1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INTk2；
②若2k≤
，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
③若2k1≤
，则编号为k的结点的右子结点编号为2k1；否则该结点无右子结点。
满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k1个结点深度为m的满二叉树有2m1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历：
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
1．7查找技术
顺序查找的使用情况：
（1）线性表为无序表；
（2）表采用链式存储结构。
二分法查找只适用于顺序存储的有序表，对于长度为
的有序线性表，最坏情况只需比较log2
次。
1．8排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法：（1）冒泡排序法，需要比较的次数为
12；（2）快速排序法。
插入类排序法：（1）简单插入排序法，最坏情况需要
12次比较；（2）希尔排序法，最坏情况需要O
15次比较。
选择类排序法：（1）简单选择排序法最坏情况需要
12次比较；（2）堆排序法，最坏情况需要O
log2
次比较。
第二章程序设计基础
f2．1程序设计设计方法和风格如何形成良好的程序设计风格1、源程序文档化；2、数据说明的方法；3、语句的结构；4、输入和输出。注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。
2．2结构化程序设计结构化程序设计方法的四条原则是：1自顶向下；2逐步求精；3模块化；
4限制使用goto语句。结构化程序的基本结构和特点：
（1）顺序结构：r