GESP 六级考点 : 树 相关 第一篇
包括 : 树的定义 , 构造 , 遍历
正文:
树的定义 : 一棵树是由n(n>=0)个元素组成的有限集合.
树的构造 : 其中,每个元素都称为节点(Node) ; 有一个特定的节点,称为根节点/树根(Root).
除根结点外,其余节点能分成m(m>=0)个互不相交的有限集合T(0),T(1),T(2),......,T(m-1).
其中的每一个子集都是一棵子树,这些结合称为这棵树的子树.
补充知识:
树的概念:
(1)根节点:树有唯一的根节点,它没有前驱节点
*前驱节点:(ROOT是N1的前驱节点,也是N2的前驱节点)
(2)度:一个节点的子树个数,称为这个节点的度.度为0的节点称为叶节点,树中各结点的度的最大值称为这颗树的度
(3)子节点:节点的子树的根,称为该节点的子节点,该节点是子节点的父亲节点,同一个父亲节点的多个子节点互为兄弟节点.
(4)层次:定义一颗树的根节点的层次为1,其他节点的层次等于它的父亲节点层次加1
(5)深度:一棵树所有节点的层次的最大值为树的深度
(6)路径:对于树中任意两个不同的节点.如果从一个节点出发,自上而下沿着书中连着节点的便能到达另一节点,称它们之间存在着一条路径
如图: 称ROOT和N2之间存在一条路径:
可用路径所经过的节点序列表示路径,路径的长度等于路径上的节点个数减1
树的遍历:
按照某种次序访问树的全部节点叫做树的遍历.常见的遍历方法有4种(一般用于二叉树)
1.先序遍历:先访问根节点,再访问左子树,最后访问右子树.(根节点最先遍历)
如上图:先访问节点1(根节点),进入其左子树
继续按照根节点->左子树->右子树的顺序遍历:
先访问这颗子树的根节点2,然后进入其左子树
先访问这颗子树的根节点4,然后发现其没有左子树,没有右子树,这颗子树遍历完毕.
开始返回:
*前情回顾:1->2->4->×
返回到2号节点,其左子树已经遍历完毕,然后发现其没有右子树,继续返回.
返回到1号节点(根节点),其左子树已经遍历完毕,然后进入其右子树
先访问这颗子树的根节点3,然后进入其左子树
先访问这颗子树的根节点5,然后发现其没有左子树,直接进入其右子树
先访问这颗子树的根节点6,然后发现其没有左子树,也没有右子树
开始返回:
*前情回顾:1->2->4->3->5->6->×
返回到5号节点,无左子树,右子树已经遍历到了,继续返回
返回到3号节点,其左子树已经遍历完成,无右子树,继续返回
返回到1号节点(根节点),其左子树已经遍历完成,右子树已遍历完成.
整棵树遍历完成.
先序遍历结果为:1->2->4->3->5->6.
2.中序遍历:访问顺序:左子树->根节点->右子树(根节点在中间遍历)
遍历方法同上
中序遍历结果为:4->2->1->5->6->3
3.后序遍历:访问顺序:左子树->右子树->根节点(根节点在最后遍历)
后序遍历结果为:4->2->6->5->3->1
4.层序遍历:按层次大小逐个访问,同一层次按照从左到右的次序
层序遍历结果为:1->2->3->4->5->6
参考书目:1.全国青少年CSP-J编程竞赛真题解析
2.小码王C++课堂笔记
第一次做学习讨论帖,若有出错,请多多海涵
