计算机二级C
有结点中最大的度称为树的度。树的最大层次称为树的深度。
2、二叉树及其基本性质
(1)什么是二叉树
二叉树是一种很有用的非线性结构,它具有以下两个特点:1)非空二叉树只有一个根结点;2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
*:根据二叉树的概念可知,二叉树的度可以为0(叶结点)、1(只有一棵子树)或2(有2棵子树)。
(2)二叉树的基本性质
性质1 在二叉树的第k层上,最多有 个结点。
性质2 深度为m的二叉树最多有个 个结点。
性质3 在任意一棵二叉树中,度数为0的结点(即叶子结点)总比度为2的结点多一个。性质4 具有n个结点的二叉树,其深度至少为 ,其中 表示取 的整数部分。
3、满二叉树与完全二叉树
满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。
完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
*:根据完全二叉树的定义可得出:度为1的结点的个数为0或1。
下图a表示的是满二叉树,下图b表示的是完全二叉树:
完全二叉树还具有如下两个特性:
性质5 具有n个结点的完全二叉树深度为 。
性质6 设完全二叉树共有n个结点,如果从根结点开始,按层序(每一层从左到右)用自然数1,2,…,n给结点进行编号,则对于编号为k(k=1,2,…,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点的编号为INT(k/2)。
②若2k≤n,则编号为k的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的右子结点编号为2k+1;否则该结点无右子结点。
4、二叉树的存储结构
在计算机中,二叉树通常采用链式存储结构。
与线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成:数据域和指针域。但在二叉树中,由于每一个元素可以有两个后件(即两个子结点),因此,用于存储二叉树的存储结点的指针域有两个:一个用于指向该结点的左子结点的存储地址,称为左指针域;另一个用于指向该结点的右子结点的存储地址,称为右指针域。
*:一般二叉树通常采用链式存储结构,对于满二叉树与完全二叉树来说,可以按层序进行顺序存储。
5、二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种:
(1)前序遍历(DLR):若二叉树为空,则结束返回。否则:首先访问根结点,然后遍历左子树,最后遍历右子树;并且,在遍
计算机二级二级公共基础知识辅导讲义1 隐藏>> 全国计算机等级考试 二级公共基础知识 (0) 2003.11. 基本要求 1. 掌握算法的基本概念。 2. 掌握基本数据结构及其...
29 I VFP 二级公共基础知识培训讲义 第一章 1.1 算法 数据结构与算法( )(选择 , 数据结构与算法(30 分)(选择 20,填空 10) ) 1、算法是指解题方案的...
二级公共基础知识辅导讲义... 6页 1财富值喜欢此文档的还喜欢 国二公共基础知识)考试考点... 25页 免费 全国计算机等级考试二级VF... 48页 1财富值 历年...
全国计算机等级考试——二级公共基础知识辅导讲义 全国计算机等级考试——二级公共基础知识辅导讲义 ——二级公共基础知识公共基础知识 基本要求 1. 掌握算法的基本概念...
二级公共基础知识辅导讲义2 计算机二级C计算机二级C隐藏>> 第二章 程序设计基础 2.1 程序设计风格程序设计的风格主要强调:“清晰第一,效率第二”。主要应注重和...
二级公共基础知识辅导讲义4 计算机二级C计算机二级C隐藏>> 第四章 数据库设计基础 4.1 数据库系统的基本概念 1、数据、数据库、数据管理系统(1)数据:实际上就...
二级公共基础知识辅导讲义3 计算机二级考试必知问题计算机二级考试必知问题隐藏>> 模拟题 第一套 模拟题(1)栈和队列的共同特点是 A)都是先进先出 B)都是先进...
全国计算机等级考试——二级公共基础知识辅导讲义 第一章 数据结构与算法 11算法...1 、线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的...
全国计算机等级考试——二级公共基础知识辅导讲义 全国计算机等级考试——二级公共基础知识辅导讲义 ——二级公共基础知识 第一章 数据结构与算法 1.1 算法 1、算法...
热门文档