树
基本定义和概念
- 树是一个由n个节点的有限集合
-
每个树只有一个根节点
-
如果一个数的节点数>1,则除了根节点外的每个其余节点本身就又是另一个集合,这些集合可以看作新的树
这棵树,A是根节点,其余三个节点分为不同的子集,每一个子集也是一棵树
-
一般说来,分等级的分类方案都可用层次结构来表示,也就是说,都可导致一个树结构。
基本术语
- 结点:树的结点包含一个数据元素及若干指向其子树的分支。
- 度:结点拥有的子树的数量称之为度,比如上面的树,A结点的度为3
- 终端结点/叶子结点:度为0的结点就被称为终端结点或叶子节点
- 非终端结点/分支节点:度不为0的结点
- 树的度:各结点中度的最大值
- 孩子/双亲:结点的子树的根被称为该结点的孩子,反过来,该结点就被称为这个孩子的双亲。
- 兄弟:同一个双亲的孩子之间成为兄弟,如H、I、J可视为兄弟
- 层次:从根开始定义起,根为第一层,根的孩子为第二层。
- 深度:树中结点的最大层次,被称为深度
- 有序树/无序树:如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。
- 森林:森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。由此,也可以森林和树相互递归的定义来描述树。
1.二叉树
基本定义
- 每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)
- 二叉树的子树有左右之分,其次序不能任意颠倒。
基本性质
- 在二叉树的第i层上至多有2i-1个结点(i≥1)。
- 在深度为k的二叉树上,至多由2k-1个结点
- 叶子树 = 度为2的结点数+1
完全二叉树与满二叉树
满二叉树:一棵深度为k且有2k-1个结点的二叉树称为满二叉树。如图6.4(a)所示是一棵深度为4的满二叉树,这种树的特点是每一层上的结点数都是最大结点数。
完全二叉树:深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。(一棵从左往由排列的二叉树就是完全二叉树)
- 如果完全二叉树的i结点等于1,则i结点无双亲,如果i>1则其双亲是[i/2]
- 如果2i>n,则i结点没有左孩子(i结点为叶子结点),否则其左孩子是结点2i
- 如果2i+1>n,则结点i无右孩子,否则其右孩子为2i+1
Comments | NOTHING