2.二叉树的概念

定义及其主要特性

• 二叉树是有序树，即使树中结点只有一棵子树,也要区分它是左子树还是右子树
• 二叉树的 5种基本形态：
  1. 空二叉树
  2. 只有根结点
  3. 只有左子树
  4. 左右子树都有
  5. 只有右子树

特殊的二叉树

两种特殊形态的二叉树

满二叉树

一棵高度为h,且含有$2^h-1$ 个结点的二叉树称为满二叉树,即,树中的每层都含有最多的结点

约定编号从根结点(根结点编号为 1)起,自上而下,自左向右。这样,每个结点对应一个编号,对于编号为i的结点,若有双亲,则其双亲为$\lfloor \displaystyle\frac{i}{2}\rfloor$, 若有左孩子,则左孩子为2i;若有右孩子,则右孩子为 2i+1。

完全二叉树

高度为$h$,有$n$个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中编号为 1~n 的结点一一对应时,称为完全二叉树

1. 若$i\leq \displaystyle\lfloor \frac{n}{2}\rfloor$，则结点$i$为分支结点，否则为叶结点
2. 叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该
   层最左边的位置上
3. 若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征)。
4. 按层序编号后，一旦出现某结点（编号为$i$ ）为叶结点或只有左孩子^[1]，则编号大于i
   的结点均为叶结点
5. 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支
   结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有

例题

已知叶子结点，求最多的结点数

二叉排序树

• 左子树上所有结点的关键字均小于根结点的关键宇;右子树上的所有结点的关键字均大于根结点的关键宇;
• 左子树和右子树叉各是一棵二叉排序树

平衡二叉树

树上任意一个结点的左子树和右子树的深度之差不超过 1的二叉排序树

二叉树的性质

1. 非空二叉树上的叶结点数等于度为2的结点数加 1,即$n_{0}=n_{2}+1$
2. 非空二叉树上第$k$层上至多有$2^{k-1}$个结点($k\geq 1$)
3. 高度为$h$的二叉树至多有$2^h-1$个结点($h\geq1$)
4. 对完全二叉树按从上到下、从左到右的顺序依次编号 1,2,…,n,则有以下关系:
   1. 当$i>1$时,结点$i$的双亲的编号为$\left\lfloor \displaystyle\frac{i}{2} \right\rfloor$,即当$i$为偶数时,其双亲的编号为 $\displaystyle\frac{i}{2}$,它是双亲的左孩子;当$i$为奇数时,其双亲的编号为$\displaystyle\frac{i-1}{2}$,它是双亲的右孩子
   2. 当$2i\leq n$时,结点$i$的左孩子编号为$2i$, 否则无左孩子
   3. 当$2i+ 1\leq n$时,结点$i$的右孩子编号为$2i+1$,否则无右孩子
   4. 结点$i$所在层次(深度)为$\left\lfloor \log_{2}i \right\rfloor+1$
5. 具有$n$个($n\text{>}0$)结点的完全二叉树的高度为$\left\lceil \log_{2}(n+1) \right\rceil$或$\left\lfloor \log_{2}n \right\rfloor$+1
6. 完全二叉树假设度为0、1、2的结点数为$n_{0},n_{1},n_{2}$，则完全二叉树所以度为1的结点只能是0或1个，所以$n_{1}=0 \text{或}1$，又由1可知$n_{0}+n_{2}$应该是奇数

相关证明

1. 设度为0,1和2的结,点个数分别为$n_{0},n_{1}$和$n_{2}$,结点总数

$$n=n_{0}+n_{1}+n_{2}$$

再看二叉树中的分支数,除根结点外,其余结点都有一个分支进入,设$B$为分支总数, 则

$$n=B+1$$

由于这些分支是由度为 1 或2的结点射出的,所以又有

$$B=n_{1}+2n_{2}$$

于是得

$$n_{0}+n_{1}+n_{2}=n_{1}+2n_{2}+1$$

则

$$n=n_{2}+1$$

3. $2^{k-1}$求和
4. 设高度为h,根据性质3和完全二叉树的定义有

$$2^{h-1}-1\text{<}n\leq 2^h-1$$

得

$$h-1<\log_{2}(n+1)\leq h$$

且$h$为正整数

存储结构

1.顺序存储结构

完全二叉树和满二叉树采用顺序存储比较合适^[2]

image.png

完全二叉树顺序存储

1. 可以让第一个位置空缺，保证数组下标和编号^[3]一致
2. $i$的左孩子--$2i$
3. $i$的右孩子--$2i+1$
4. $i$的父节点--$\left\lfloor \displaystyle\frac{i}{2} \right\rfloor$
5. $i$所在的层次--$\left\lceil \log_{2}(n+1) \right\rceil$或$\left\lfloor \log_{2}n \right\rfloor$+1
6. 是否有左孩子，$n\geq2i?$
7. 是否有右孩子，$n\geq2i+1?$
8. 是否是叶子结点，$i> \displaystyle\lfloor \frac{n}{2}\rfloor$
9. 非完全二叉树也可以这样当完全二叉树存储，只是会有很多浪费的空间，而且判断是否有左右孩子的时候是通过isEmpty来的

2.链式存储结构

结点结构

lchild	data	rchild

typedef struct BiTNode{
	ElemType data;
	struct BitNode *lchild,*rchild;
}BiTNode,*BiTree

提示

🤔在含有n个结点的二叉链表中,含有$2n-(n-1)=n+1$个空链域(每个结点都有从父节点指向自己的指针，除了根节点)

---

1. 相当于前面所给图中编号为6的结点 ↩︎

2. 建议从数组下标1开始 ↩︎

3. 从1开始，下面的结论也是针对从1开始的编号 ↩︎