树
这一节是个大章节,让我们做好准备.
1 定义:
树是n >= 0 个结点的有限集.n = 0 是为空树.
在任意一颗非空树中:
- 有且只有一个根结点.
- 当n > i 时,其余结点可分为m(m > 0)个互不相交的有限集,其中每一个集合本身也是一棵树,成为根结点的子树.
1.1 结点的分类:
定义:包含一个数据元素及若干指向子树的分支.
结点拥有的子树的个数称为结点的度.
叶结点(终端结点):度为0.其他成为非终端结点或分支结点(内部结点).
1.2 结点间的关系
结点的子树的根称为该结点的孩子(Child),对应该结点为孩子的双亲(Parent).
同一个双亲的孩子之间互为兄弟(Sibling).结点的祖先是从根结点到该结点所经分支上所有的结点.以某结点为根的子树中的任一结点都称为该结点的子孙.
类比小时候的家族亲戚关系之间的图或者中学学习遗传疾病分析图.
1.3 树的其他相关概念:
结点的层次从根结点开始定义,根为第一层 根的孩子为第二层.根的孙子为第三层.
树的深度或高度:树中结点的最大层次称为树的深度或高度.
如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则为无序树.
森林:是m( m >= 0)棵互不相交的树的集合.
目前为止,关于数据结构学了2种.
| 线性结构 | 树结构 |
|---|---|
| 第一个数据元素:无前驱;最后一个数据元素:无后继;中间元素:一个前驱一个后继 | 根节点:无双亲,唯一;叶节点:无孩子,可以多个;中间结点:一个双亲 多个孩子 |
2 树的存储结构
类比线性结构的学习过程,接下里肯定要研究其存储特点.显然顺序存储无法直接反映逻辑关系,比如谁是谁的双亲,谁是谁的孩子.
这里只介绍三种不同的表示方法:双亲表示法,孩子表示法,孩子兄弟表示法
2.1 双亲表示法
3 二叉树
3.1 定义:
是n ( >= 0)个 结点的有限集合.n = 0时,称为空集合或空二叉树.
n > 0时,由一个根结点和2棵互不相交的分别称为根结点的左子树和右子树的二叉树组成.
特点:
- 每个结点最多有2棵子树.
- 左右子树是有顺序的,跟人的左右手 左右脚一样.
- 即是某一结点只有一棵子树也分左右,同理残疾人.
二叉树的五种基本形态:
- 空二叉树
- 只有一个根结点
- 只有一个左子树
- 只有一个右子树
- 根结点既有左子树又有右子树.
特殊二叉树的种类:
- 斜树: 所有结点只有左子树或者右子树.
- 满二叉树:所有分支结点都存在左右子树,并且所有叶子都在用一层.
- 完全二叉树: 对一颗具有n个结点的二叉树按层序编号,如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同.
完全二叉树的特点:
- 叶子结点只能出现在最下两层.
- 最下层的叶子一定集中在左部连续的位置.
- 倒数二层,若有叶子结点,一定都在右边连续位置
- 如果结点度为1,则该结点只有左子树.
- 同样结点数的二叉树,完全二叉树的深度最小.
3.2 二叉树的性质
- 性质1:在二叉树的第i层上至多有2^(i-1)个结点.(i>=1)
- 性质2:深度为k的二叉树至多有 2^k - 1个节点.(k>=1)
- 还有很多性质,均可以通过推到推导出来.
