文档详情

计算机2级公共基础知识1.ppt

发布:2018-02-27约7.23千字共43页下载文档
文本预览下载声明
第*页 二叉树的概念 定义:二叉树是一种有序的树形结构。它与一般树形结构的区别是: 每个结点最多有两棵子树; 子树有左右之分,次序不能任意颠倒。称左子树和右子树 二叉树的5种基本形态 第*页 ★树与二叉树的区别 A.树和二叉树的结点个数最少都可为0。 B.树中结点的最大度数没有限制,二叉树结点最大度数为2。 C.树的结点无左、右之分,二叉树的结点子树有明确的左、右之分。 3个结点的树 3个结点的 二叉树 第*页 二叉树的性质 【性质1】 在二叉树的第i层上最多有2i-1个结点(i≥1) A B C D F E H G 12 13 14 15 8 9 10 11 4 5 6 7 1 2 3 第*页 【性质2】深度为h的二叉树最多有2h -1个结点(h ≥1) A B C D F E H G 12 13 14 15 8 9 10 11 4 5 6 7 1 2 3 第*页 【性质3】二叉树上叶子结点数比度为2的结点数多1 A B C D F E H G 度为2的结点 叶子结点 第*页 满二叉树和完全二叉树 满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。最后一层的结点均为0度。 完全二叉树:除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。则称这棵二叉树为完全二叉树。完全二叉树中度数为1的结点的个数为0或1。 第*页 12 13 14 15 8 9 10 11 4 5 6 7 1 2 3 满二叉树 完全二叉树 12 13 8 9 10 11 4 5 6 7 1 2 3 第*页 12 13 8 9 10 11 4 5 6 1 2 3 非完全二叉树 深度为4的完全二叉树 8 4 5 6 7 1 2 3 第*页 【性质4】具有n个结点的完全二叉树的深度为 ?log2 (n+1) ?其中,?log2n? 的结果是不大于log2n的最大整数 12 13 14 15 8 9 10 11 4 5 6 7 1 2 3 深度为4的满二叉树 深度为4的完全二叉树 8 4 5 6 7 1 2 3 ?log2(8+1) ? = ln9/In2=4 ?log2 (15+ 1)? =In16/In2=4 第*页 性质5:具有n个结点的完全二叉树的深度为 11 2 3 4 5 6 7 8 9 10 12 1 例:n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=4 第*页 1:在深度为7的满二叉树中,叶子结点的个数为(2006年4月) ?? A)32???? B)31? ???C)64?? ??D)63 2:在深度为7的满二叉树中,度为2的结点个数为【 】 。(07年4月) 3:一棵二叉树中共有70个叶子结点与80个度为1的结点,则该二叉树中的总结点数为 (07年9月) A)219 B)221 C)229 D)231 1.满二叉树的定义和【性质1】 在二叉树的第i层上最多有2i-1个结点。 2.【性质3】二叉树上叶子结点数比度为2的结点数多1。 3. “【性质3】二叉树上叶子结点数比度为2的结点数多1”和二叉树的定义。70+80+69(度为2的结点数) 树型结构方面的考题 1答案:C。 3答案:A。 2答案:63。 答案 第*页 4: 某二叉树中度为2的结点有18个,则该二叉树中有 【 】个叶子结点。(2005年4月) 5:一棵二叉树第六层(根结点为第一层)的结点数最多为【 】个。(2005年9月) 4.【性质3】二叉树上叶子结点数比度为2的结点数多1。 5.【性质1】在二叉树的第i层上最多有2i-1个结点 5答案:32。 4答案:19。 答案 第*页 二叉树的遍历 遍历指不重复地访问二叉树中的所有结点。 二叉树的遍历的次序与树型结构上的大多数运算有联系。 遍历的方式有三种 (1)先(前)序遍历 (2)中序遍历 (3)后序遍历 A B C D F E H G 第*页 二叉树的遍历 (1)先(前)序遍历(DLR)根左右 若二叉树为空,则结束遍历操作;否则 访问根结点; 先序遍历左子树; 先序遍历右子树。 A B C D F E H G 先序遍历的结果: A B E C F G H D 第*页 (2)中序遍历(LDR)左根右 若二叉树为空,则结束遍历操作;否则 中序遍历左子树; 访问根结点; 中序遍历右子树。 中序遍历的结果: E B A F H G C D (3)后序遍历(LRD)左右根 若二叉树为空,则结束遍历操作;否则 后序遍历左子树; 后序遍历右子树; 访问根结点。
显示全部
相似文档