基本定义和概念

  • 树是一个由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层上至多有2i-1个结点(i≥1)。
  2. 在深度为k的二叉树上,至多由2k-1个结点
  3. 叶子树 = 度为2的结点数+1

完全二叉树与满二叉树

满二叉树:一棵深度为k且有2k-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个域:数据域和左、右指针域
    二叉树的存储结构分别称之为二叉链表和三叉链表


醉后不知天在水,满船清梦压星河