顶1242561底61队尾21队头树基本术语根结点：没有前件的结点，只有一个。如结点A叶子结点：没有后件的结点。如结点C、D、E、F结点的度：一个结点所拥有的后件个数。如结点B的度为3，叶子结点D的度为0树的度：所有结点中的最大的度。如下图所示的树的度为3树的深度：树的最大层次。如下图所示的树的深度为3FEDCBA前序ABDECF中序DBEAFC后序DEBFCA二叉树特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。基本性质：（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；（2）深度为m的二叉树最多有2m-1个结点；1+2+4+8+-----+2m-11(1-2m)/(1-2)=（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；n0+n1+n2=0*n0+1*n1+2*n2+1n0=n2+1例1：（2011-3-03）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层)（Ｄ）A)3B)4C)6D)7【解析】二叉树性质3：度为0的结点个数总比度为2的结点多一个。叶子结点只有1个，所以度为2的结点没有，即度为1的结点6个，深度为7，所以选D。例2：（2010-9-03）一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有25个结点。【解析】该二叉树中的叶子结点数为7+1=8个，度为1、2、0的结点数分别为10、7、8，则结点总数为10+7+8=25。（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；2m-1=n满二叉树：指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树：指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树的深度为[log2n]+1。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点例1：（2011-3-02）一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为DEBFCA。DCBAFE【解析】根据前序遍历结果可知：A为根节点，B为A的左子树，根据中序遍历结果可知：D为B的左子树，E是B的右子树，F、C是A的右子树，结合前序遍历结果可知，C是A的右子树，F是C的左子树。故后序遍历为DEBFCA。4．E-R图表示实体、属性和实体之间的联系。SnoSsexCnoCnameSnameSCstudentcourse用矩形表示实体集，如实体集学生（student）、课程（course）。用椭圆形表示属性，如学生有属性：学号（Sno）、姓名（Sname）、性别(Ssex)。用菱形表示联系，如学生与课程间的联系SC。5.关系运算