当前位置:首页 > 国家二级C语言公共基础知识要点及历年真题
c.树具有明显的层次关系,即树是一种层次结构。 d.数的最大层次称为树的深度。
第5页,共 26 页
f.在树中,叶子结点没有子树。
A E B F C G H D I K L J 如左图中, 1、A 为根结点; 2、E、F、J、H、K、L、 M 为叶子结点。 3、树中A、I 都有 3 个子 结点,故树的度为 3。 M 4、 整个树中, 总共分为4 层,故树的深度为 4。 树形表示法 二叉树 6.2 二叉树及其基本性质
1.什么是二叉树:
二叉树是一种很有用的非线性结构。 二叉树具有以下两个特点: a.非空二叉树只有一个根结点;
b.每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
由以上特点可以看出,在二叉树中,每一个结点的度最大为2。 2.二叉树的基本性质:(重要)
a.在二叉树的第 k 层上,最多有 2k-1(k>=1)个结点。
b.深度为 m 的二叉树最多有 2m-1 个结点。深度为 m 的二叉树是指二叉树共有 m 层。 c.在任意一棵二叉树中,度为 0 的结点(即叶子结点)总是比深度为 2 的结点多一个。
d.具有 n 个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取 log2n 的整数部分。
A、 第四层中,最多有 24-1=23=8 个结点。 B、树的深度为 4,最多有 24-1=16-1=15 个
结点。 C、度为 0 的结点有 8 个, 度为2 的结点有7
个。
3.满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
a.满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。这就是说,在满二叉树中,每一层上的 结点数都达到最大值,即在满二叉树的第k 层上有 2k-1 个结点,且深度为 m 的满二叉树有 2m-1 个结点。
b.完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。 注意:满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。 完全二叉树还具有以下性质:
a.具有 n 个结点的完全二叉树的深度为log2n] +1。 完全二叉树
满二叉树 非满二叉树 6.3 二叉树的存储结构
在计算机中,二叉树通常采用链式存储结构。 6.4 二叉树的遍历:(重要)
在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、中序遍历、后序遍
第6页,共 26 页
历。
a.前序遍历:首先访问根结点,然后遍历左子树,最后遍历右子树。 b.中序遍历:首先遍历左子树,然后访问根结点,最后遍历右子树。 c.后序遍历:首先遍历左子树,然后遍历右子树,最后访问根结点。
F 1 5 F C 2 E 6 2 C G 7 6 E F 9 C 4 8 G E 8 A 3 D 4 1 A 4 D A 1 D 3 G 7 H 5 B 5 H 8 P 9 3 B 7 H 9 P B 2 P 6 前序:FCADBEGHP 中序:ACBDFEHGP 后序:ABDCHPGEF
注意:在树结构中,每一个结点都代表一棵子树。前序遍历中一定以根结点开头,后序遍历一定以根结点结尾, 而中序遍历中,根结点前面的为树的左子树,而其后面的为树的右子树。
历届的考题:
1、在深度为 7 的满二叉树中,叶子结点的个数为()[2006.4]
A)32 B)31 C)64 D)63 2、对下图 1 所示二叉树
图 1 图 2 进行中序遍历的结果是________。[2006.9]
A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG
3、对如下图 2 所示二叉树,进行后序遍历的结果为()[2006.4]
A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA
4、某二叉树中,度为 2 的结点有 18 个,则该二叉树中有___个叶子结点。[2005.4] 5、一棵二叉树第六层(根结点为第一层)的结点数最多为____个。[2005.9]
1.7 查找技术
7.1 顺序查找:
顺序查找的方法是:用被查元素与线性表中的元素逐一比较, 直到找出相等的元素, 则查找成功;或者找遍
所有元素都不相等,则查找失败。
顺序查找的优点: 对线性表的元素的逻辑次序无要求 (不必对元素进行排序) , 对线性表的存储结构无要求(顺
序存储、链接存储皆可)。
顺序查找的效率很低,但在以下情况下,只能采用顺序查找:
a.如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。 b.即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。 7.2 二分法查找:
第7页,共 26 页
共分享92篇相关文档