计算机公共基础.doc

顶1242561底61队尾21队头1. 树l 基本术语 根结点：没有前件的结点，只有一个。如结点A 叶子结点：没有后件的结点。如结点C、D、E、F 结点的度：一个结点所拥有的后件个数。如结点B的度为3，叶子结点D的度为0 树的度：所有结点中的最大的度。如下图所示的树的度为3 树的深度：树的最大层次。如下图所示的树的深度为3FEDCBA前序ABDECF 中序 DBEAFC 后序 DEBFCA2. 二叉树l 特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。l 基本性质：（1）在二叉树的第k层上，最多有2k-1(k1)个结点；（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)3 B)4 C)6 D)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=nl 满二叉树：指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。l 完全二叉树：指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树的深度为log2n+1。l 二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。3. 二叉树的遍历l 前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树l 中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树l 后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点例1：（2011-3-02）一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 DEBFCA 。DCBAFE【解析】根据前序遍历结果可知：A为根节点，B为A的左子树，根据中序遍历结果可知：D为B的左子树，E是B的右子树，F、C是A的右子树，结合前序遍历结果可知，C是A的右子树，F是C的左子树。故后序遍历为DEBFCA。4E-R图表示实体、属性和实体之间的联系。SnoSsexCnoCnameSnameSCstudentcourse 用矩形表示实体集，如实体集学生（student）、课程（course）。用椭圆形