小编所收集到的相关计算机二级考试公共基础知识冲刺复习笔记：二叉树的资料 大家要认真阅读哦！
1、树
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后
-62-件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
2、二叉树：度为2的树就是二叉树。
(1)二叉树的特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
3、二叉树的性质
(1)在二叉树中，第i层的结点总数不超过2i-1(i≥1)。
(2)深度为h的二叉树总计最多有2h-1个结点(h≥1)，最少有h个结点。
(3)对于任意一棵二叉树，如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1，即叶子数总比度为2的节点数多1。
(4)具有n个结点的完全二叉树的深度为int(log2n)+1。
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若k为结点编号，则如果k<>1，则其父结点的编号为k/2；
如果2xk<=N，则其左孩子(即左子树的根结点)的编号为2k；若2xk>N，则无左孩子;如果2xk+1<=N，则其右孩子的结点编号为2k+1；若2k+1>N，则无右孩子。
4、完全二叉树和满二叉树
(1)完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树：除了叶子结点外每一个结点都有左右子女且叶子结点都处在最低层的二叉树。
5、遍历是对树的一种最基本的运算。所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR(称为先根次序遍历，简称前序遍历)，LDR(称为中根次序遍历，简称中序遍历)，LRD(称为后根次序遍历，简称后序遍历)。
(1)前序遍历：访问根；按先序遍历左子树；按先序遍历右子树。
(2)中序遍历：按中序遍历左予树；访问根；按中序遍历右子树。
(3)后序遍历：按后序遍历左予树；按后序遍历右子树；访问根。
真题分析
【真题1】某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是________。（2009年3月）
A)6
B)4
C)10
D)8
解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。
答案：A
【真题2】深度为5的满二叉树有__【2】__个叶子节点。（2008年4月）
解析：在二叉树中，深度为N的满二叉树的叶子结点数目为：2(N-1)。
答案：16
【真题3】一棵二叉树中共有70个叶子节点与80个度为1的结点，则该二叉树总结点数为________。（2007年9月）
A)229
B)231
C)219
D)221
解析：在二叉树中，叶子结点个数为N0，则度为2的结点数N2=N0-1。
本题中叶子结点的个数为70，所以度为2的结点个数为69，因而总结点数=叶子结点数+度为1的结点数+度为2的结点数=70+80+69=219。
答案：C
【真题4】某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为________。（2007年3月）
A)2n
B)n/2
C)n+l
D)n-1
解析：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以该二叉树的叶子结点数等于n+1。
答案：C
文字很枯燥，但内容却很丰富，小编在此祝大家都能考出让自己满意的成绩哦！
继续了解公共基础知识？点击下方链接，进入考无忧官方网站，更多精彩等你来！
小编特别推荐二级ms office可以了解一下噢！ 毕竟这项科目着实相比其他科目比较容易啦！
文章推荐：
温馨提示：
想要了解更多试题请点击查看>>>计算机二级考试题库
考试想拿高分吗？更多二级ms office试题请点击查看>>>二级ms office
想知道更多关于计算机等级考试的最新资讯吗？点击进入>>>计算机等级考试
