数据结构之树

树

基本定义和概念

• 树是一个由n个节点的有限集合

• 每个树只有一个根节点

• 如果一个数的节点数>1,则除了根节点外的每个其余节点本身就又是另一个集合，这些集合可以看作新的树

  • 举例：

  这棵树，A是根节点，其余三个节点分为不同的子集，每一个子集也是一棵树

• 一般说来,分等级的分类方案都可用层次结构来表示，也就是说,都可导致一个树结构。

基本术语

1. 结点：树的结点包含一个数据元素及若干指向其子树的分支。
2. 度：结点拥有的子树的数量称之为度，比如上面的树，A结点的度为3
3. 终端结点/叶子结点：度为0的结点就被称为终端结点或叶子节点
4. 非终端结点/分支节点：度不为0的结点
5. 树的度：各结点中度的最大值
6. 孩子/双亲：结点的子树的根被称为该结点的孩子，反过来，该结点就被称为这个孩子的双亲。
7. 兄弟：同一个双亲的孩子之间成为兄弟，如H、I、J可视为兄弟
8. 层次：从根开始定义起，根为第一层,根的孩子为第二层。
9. 深度：树中结点的最大层次，被称为深度
10. 有序树/无序树：如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。
11. 森林：森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。由此,也可以森林和树相互递归的定义来描述树。

1.二叉树

基本定义

• 每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)
• 二叉树的子树有左右之分,其次序不能任意颠倒。

基本性质

1. 在二叉树的第i层上至多有2^i-1个结点(i≥1)。
2. 在深度为k的二叉树上，至多由2^k-1个结点
3. 叶子树 = 度为2的结点数+1

完全二叉树与满二叉树

满二叉树：一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。如图6.4(a)所示是一棵深度为4的满二叉树,这种树的特点是每一层上的结点数都是最大结点数。

完全二叉树：深度为k的,有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。（一棵从左往由排列的二叉树就是完全二叉树）

1. 如果完全二叉树的i结点等于1，则i结点无双亲，如果i>1则其双亲是[i/2]
2. 如果2i>n，则i结点没有左孩子（i结点为叶子结点），否则其左孩子是结点2i
   1. 如果2i+1>n，则结点i无右孩子，否则其右孩子为2i+1

存储结构

• 顺序存储结构

  按照顺序存储结构的定义,在此约定,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为i的结点元素存储在如.上定义的一维数组中下标为i-1的分量中。

  顺序储存结构只适用于完全二叉树，因为其他的数会导致大量的内存浪费

• 链式存储结构
  二叉树的链表中的结点至少包含3个域:数据域和左、右指针域
  二叉树的存储结构分别称之为二叉链表和三叉链表