1. 树型结构
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树(它是根朝上,而叶朝下的),其物理结构如下图所示:
其中树形结构具有以下的特点:
1、有一个特殊的结点,称为根结点,根结点没有前驱结点
2、除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm,其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继(除了根节点之外,其余的节点有且仅只有一个父节点)
3、树是递归定义的
4、树形结构中,子树之间不能有交集,否则就不是树形结构
5、一个有n个节点的树,它有n-1条边;
1.1 关于树的关键词
下面的一些列重要关键词汇的介绍是针对下图树来讲解的:
一级词汇(重点理解):
1、结点的度(节点的分支):一个结点含有子树的个数称为该结点的度; 如上图:A的度为6
2、树的度(分支最多的那个节点的分支数):一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6
3、叶子结点或终端结点(没有分支的节点):度为0的结点称为叶结点; 如上图:B、C、H、I...等节点为叶结点
4、双亲结点或父结点(有分支的节点):若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点
5、孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点
6、根结点(最顶头的节点):一棵树中,没有双亲结点的结点;如上图:A
7、结点的层次(从上到下数,该节点在第几行):从根开始定义起,根为第1层,根的子结点为第2层,以此类推
二级词汇(了解即可)
1、非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G...等节点为分支结点
2、兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点
3、兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点
4、堂兄弟结点 :双亲在同一层的结点互为堂兄弟;如上图: H 、 I 互为兄弟结点
5、结点的祖先 :从根到该结点所经分支上的所有结点;如上图: A 是所有结点的祖先
6、子孙 :以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是 A 的子孙
7、森林 :由 m ( m>=0 )棵互不相交的树组成的集合称为森林
1.2 树的表示形式
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦,实际中树有很多种表示方式,如:双亲表示法, 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。
这里通过代码简单的了解其中最常用的孩子兄弟表示法;
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
下图是孩子兄弟表示法的树结构图解:
如上图所示,孩子兄弟表示法主要通过child域(存放该节点的子节点的地址)和brother域(存放该节点兄弟节点的地址)来完成整个树构成;
2. 二叉树
一棵二叉树是关于结点的一个有限集合,该集合的特点:
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
如上图就是将一个二叉树分解成概念中的节点的有限集合的形式(左子树<--根节点-->右子树),从上图可以看出:
1. 二叉树不中结点的分支最多就是2个分支;
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
2.1 特殊的二叉树
1. 满二叉树(除了叶子节点,其余的节点都有两个分支) : 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树 。也就是说,如果一棵二叉树的层数为 K,且结点总数是(2^K)-1 ,则它就是满二叉树 ,如下图就是满二叉树;
2. 完全二叉树 : 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于所有的节点按照二叉树的规则,依据从上到下,从左到右,依次排序的准则排序的二叉树, 要注意的是满二叉树是一种特殊的完全二叉树,如下图就是完全二叉树;
2.2 二叉树的性质
1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (2^i-1) (i>0)个结点
//已知第几层------> 计算该层节点个数
2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是(2^K)-1 (k>=0)
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1
推导过程如下所示:
4. 具有n个结点的完全二叉树的深度k为 上取整
5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i 的结点有:
若 i>0 , 双亲序号: (i-1)/2 ; i=0 , i 为根结点编号 ,无双亲结点
若 2i+1<n ,左孩子序号: 2i+1 ,否则无左孩子
若 2i+2<n ,右孩子序号: 2i+2 ,否则无右孩子5.1重要的两个小结论:
3.二叉树例题讲解
1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树
B 200
C 198
D 199
由性质3可得: 对任何一棵二叉树 , 如果其叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有n0=n2+1------->399=n0+n2-------->399=n0+n0-1----->n0=200
或者---->
n0=199+1为200;------>B
2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )
A n
B n+1
C n-1
D n/2
考虑是否存在最后一个节点只有一个分支的节点,图解如下图所示:
由n0 = n2 +1可得:
左图:2n = n0 + 1 +n0-1------------->n0 = n---------->A;
右图:2n = n0 +n0-1------------------->n0=(2n+1)/2;
3.一个具有767个节点的完全二叉树,其叶子节点个数为()
A 383
B 384
C 385
D 386
由n=n0+n1+n0-1--------->768=2n0+n1------>因为n1只能为1------>不满足题意,令n1 =0----->n0=768/2 =384;
4.一棵完全二叉树的节点数为531个,那么这棵树的高度为( )
A 11
B 10
C 8
D 12
性质4:具有n个结点的完全二叉树的深度k为:
注意:向上取整
512=2^9<2^10;
故令h =10;