data structure

1. 二叉树的定义及其主要特性

1.1 二叉树的定义

二叉树是另一种树形结构,其特点是每个结点最多只有两个子树(结点的度<=2),并且二叉树的子树有左右之分,其次序不能任意颠倒。

与树相似,二叉树也以递归的形式定义。

  1. 或者为空二叉树,即 n = 0 。
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。

二叉树是有序树,若将其左、右子树颠倒,则成为另一颗不同的二叉树,即使树中结点只有一颗子树,也要区分它是左子树和右子树。二叉树有 5 中形态:空、根、根左、根右、根左右。

二叉树与度为2的有序树的区别

  1. 度为 2 的树至少有 3 个结点,而二叉树可以为空
  2. 度为 2 的有序树的孩子结点的左右次序是相对于另一个孩子结点而言的,若某个结点只有一个孩子结点,而这个孩子结点就无须区分其左右次序,而二叉树无论其孩子树是否为 2,均需要确定其左右次序,即二叉树的结点次序不是相对于另一个结点而言,而是确定的。

1.2 几个特殊的二叉树

  1. 满二叉树。一颗高度为 h ,且有 2^h-1 个结点的二叉树称为满二叉树,即树中的每层都含有最多的结点。除叶子结点外的每个结点度数均为 2 。

    可以对满二叉树按层序编号 :约定编号从根结点(根结点编号为 1)起,自上而下,自左向右。这样,每个结点对应一个编号,对于编号为 i 的结点,若有双亲,则其双亲为 i/2 ,若有左孩子,则左孩子为 2i;若有右孩子,则右孩子为 2i+1。

  2. 完全二叉树。设一个高度为 h、有 n 个结点的二叉树,当且仅当其每个结点都与高度为 h 的满二叉树中编号为 1~n 的结点一一对应时,称为完全满二叉树。这种树的特点有 :

    1. 若 i<=n/2 ,则结点 i 为分支结点,否则为叶子结点(堆排序用到)
    2. 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点,都一次排列在该层最左边的位置
    3. 若有度为 1 的结点,则只可能有一个,且该结点只有左孩子而无右孩子(重要特征)。
    4. 按层序编号后,一旦出现某结点(编号为 i)的叶子结点或只有左孩子,则编号大于 i 的结点均为叶子结点。
    5. 若 n 为奇数,则每个分支结点都有左子女和右子女;若 n 为偶数,则编号最大的分支结点(编号为 n/2)只有左子女,没有右子女,其余分支结点左、右子女都有。
  3. 二叉排序树。一棵二叉树或者是空二叉树,或者是具有如下性质的二叉树 :左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。

  4. 平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过 1

1.3 二叉树的性质

  1. 非空二叉树上的叶子结点树 = 度为 2 的结点数+1 ,即 n0=n2+1

    证 :n=n0+n1+n2 ,n=B+1 ,B是分支数 ,故 B=n1+2n2,得 n0+n1+n2=n1+2·n2+1 。

  2. 非空二叉树上第 k 层上至多有 2^k-1 个结点

  3. 高度为 h 的二叉树至多为 2^h-1 个结点

  4. 对完全二叉树按从上到下,从左到右的顺序依次编号 1,2,…,n,有

    1. 当 i>1 是,双亲结点编号为 i/2 ,i 为奇数左孩子,i 为偶数右孩子。
    2. 当 2i <= n 时,结点 i 的左孩子编号为 2i,否则无左孩子
    3. 当 2i+1 <= n 时,结点 i 的右孩子编号为 2i+1,否则无右孩子
    4. 结点 i 所在层次(深度)为 log2i + 1
  5. 具有 n 个(n>0)结点的完全二叉树的高度为 log2n +1

2. 二叉树的存储结构

2.1 顺序存储结构

利用数组自上而下、自左至右存储完全二叉树上的结点元素,即将完全二叉树上编号为 i 的结点元素存储在数组下标为 i 的分量中 ,然后通过规律确定结点在逻辑上的父子和兄弟关系。

依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适,树中结点的序号可以唯一地反映结点之间的逻辑关系,这样既能最大可能地节省存储空间,又能利用数组元素的下标值确定结点在二叉树中的位置,以及结点之间的关系。

但是对于一般的二叉树,为了让数组下标能反映二叉树中结点之间的逻辑关系,只能添加一些并不存在的空结点,让其每个结点与完全二叉树上的结点相对照,再存储到一维数组的相应分量中。然而,在最坏情况下,一个高度为 h 且只有 h 个结点的单支树却需要占据近 2^h-1 个存储单元。

2.2 链式存储结构

顺序存储的空间利用率较低,因此二叉树一般都采用链式存储结构。链式结构是指用一个链表来存储一棵二叉树,二叉树中的每个结点用链表的一个链结点来存储。在二叉树中,结点结构通常包括若干数据域和若干指针域。二叉链表至少包含 3 个域 :数据域 data 、左指针域 lchild 和右指针域 rchild 。

实际运用中还可以增加某些指针域,如增加指向父结点的指针。

使用不同的存储结构,实现二叉树操作的算法也会不同,随机应变吧。

含有 n 个结点的二叉链表中,含有 n+1 个空链域(常出现在选择题),后面我们会利用这个概念来组成另一种链表结构(线索链表)