第五章 二叉树

1.1 注意点

1. 不存在度大于2的结点
2. 子树有左右之分,次序不可任意颠倒
3. 以递归的形式定义:
   二叉树是n(n≥0)个结点的有限集合:
   1. 或者为空二叉树:n=0;
   2. 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成,左子树和右子树又分别是一棵二叉树
4. 二叉树是有序树,左右子树颠倒,就不是同一棵树了,五种形态
   空 只有根结点 只有左子树 只有右子树 左右子树都有
5. 与度为2的有序树的区别:
   • 度为2的树至少有3个结点,而二叉树可以为空
   • 度为2的有序树的孩子的左右次序是相对的,若某结点只有一个孩子,则不需区分左右次序;而二叉树无论是否俩孩子都要确定左右次序,因此是绝对的而不是相对的

1.2 几个特殊的二叉树

1. 满二叉树
   一棵高度为h，且含有2^h-1个结点的二叉树称为满二又树，即树中的每层都含有最多的结点，如图所示。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。
   可以对满二叉树按层序编号：约定编号从根结点（根结点编号为1）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为i的结点，若有双亲，则其双亲为Li/2，若有左孩子，则左孩子为2i；若有右孩子，则右孩子为2i+1。
   
2. 完全二叉树
   高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二又树，如图所示。就是相同高度的满二叉树缺失最下层最右边的一些连续的叶子结点其特点如下：
   ①若i≤n/2(向下取整)，则结点i为分支结点，否则为叶子结点。
   ②叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
   ③若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。
   ④按层序编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
   ⑤若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
3. 二叉排序树
   左子树所有结点关键字<根结点的关键字<右子树所有结点的关键字
   左子树和右子树又各是一棵二叉排序树
4. 平衡二叉树
   任意结点的左子树和右子树的深度之差不超过1

1.3 二叉树的性质

1. 非空二叉树上的叶子结点数等于度为2的结点数加1:n₀=n₂+1

证明:
上一节可知:总的度+1=各种结点数量之和
这里有1+0*n₀+1n₁+2n₂=n₀+n₁+n₂
得到:n₀=n₂+1

2. 非空二叉树上第k层至多有2^k-1个结点(不证了,显然)
3. 高度为h的二叉树至多有2^h-1个结点(h≥1):满二叉树前n项和
4. 对完全二叉树按从上到下、从左到右的顺序依次编号1，2…，n，则有以下关系：
   ①当i>1时，结点i的双亲的编号为i/2(下取整)，即当i为偶数时，其双亲的编号为i/2，它是双亲的左孩子；当i为奇数时，其双亲的编号为（i-1）/2，它是双亲的右孩子。
   ②当2i≤n时，结点i的左孩子编号为2i，否则无左孩子。
   ③当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子。
   ④结点i所在层次（深度）为log₂i(下取整)+1。
5. 具有n个（n>0）结点的完全二叉树的高度为log₂(n+1)(上取整)或log₂n(下取整)+1。
   设高度为h，根据性质3和完全二又树的定义有
   

1.4 二叉树的存储结构

1.4.1顺序存储结构

1. 定义:

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。

2. 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
3. 对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近2^h-1个存储单元。二叉树的顺序存储结构如图5.4所示，其中0表示并不存在的空结点。

注意：这种存储结构建议从数组下标1开始存储树中的结点，若从数组下标0开始存储，则不满足性质4的描述（比如结点A存储在0下标位置上时，无法根据性质4来计算出其孩子结点在数组中的位置），这是考生在书写程序时容易忽略的。

1.4.2链式存储结构

1. 由于顺序存储的空间利用率比较低,一般采用链式存储结构.
2. 结点结构通常包含若干数据域和若干指针域
   1. 至少包含3个域:数据域data,左指针域lchild,右指针域rchild
3. 在某些应用中还可加入指向父亲结点的指针,变成三叉链表的存储结构
   
   
4. 链式存储结构描述

typdef struct BiTNode{
    ElemType data;  //数据域
    struct BiTNode *lchild,*rchild;  //左右子树
}BiTNode,*BiTree;

5. 注意:含有n个结点的二叉链表中,含有n+1个空链域

n个结点可以带有2n个指针,除去根结点外,每个都消耗掉1个,故而:2n-(n-1)=n+1;

1.5 错题及重点整理

1. 4.设高度为h的二又树上只有度为0和度为2的结点，则此类二又树中所包含的结点数至少为（）。
   2h-1
   
   经常要注意这种特殊情况
2. 满二叉树和完全二叉树的几个层与结点个数的性质一定要记牢
3. 满k叉树的性质
   1. 各层的结点个数:k^i-1
   2. 编号为i的孩子结点
      
      可以观察到第i个结点的底下的最左边的结点为:k(i-1)+2
      最右边为:k(i-1)+2+k-1=ki+1
      第j个子女:k(i-1)+j+1
   3. 根据孩子结点反推双亲结点(若存在):j=k(i-1)+2 ==> i=(j-2)/k+1 ==> ((j-2)/k)下取整+1
   4. i有右兄弟的条件